2021年全国大学生数学建模竞赛题

1998年全国大学生数学建模竞赛题目B题灾情巡视路线下图为某县乡（镇）、村公路网示意图，公路边数字为该路段公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领关于部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地路线。(1)若分三组（路）巡视，试设计总路程最短且各组尽量均衡巡视路线。(2)假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完毕巡视，至少应分几组；给出这种分组下你以为最佳巡视路线。(3)在上述关于T，t和V假定下，如果巡视人员足够多，完毕巡视最短时间是多少；给出在这种最短时间完毕巡视规定下，你以为最佳巡视路线。(4)若巡视组数已定(如三组），规定尽快完毕巡视，讨论T，t和V变化对最佳巡视路线影响。

灾情巡视路线模型摘要本文将求最佳巡视路线间题转化为图论中求最佳推销员回路（哈米尔顿回路）问题,并用近似算法去谋求近似最优解。对赋权图半途径分组问题定义了均衡度用以衡量分组均衡性。对问题1和问题2先定出几种分准则进行初步分组,并用近似算法求每一组近似最佳推销员回路,再依照均衡度进行微调,得到较优均衡分组和每组近似最佳推销员回路。对问题1，运用求任意两点间最短路Floyd算法,得出总路程较短且各组尽量均衡路线,各组巡视路程分别为216.4公里,191.1公里,192.3公里,总路程599.8公里。对问题2,证明了应至少分为4组,并求出了分为4组时各组较优巡视路线,各组巡视时间分别为22.74小时,22.59小时,21.69小时,22.54小时。对问题3,求出完毕巡视最短时间为6.43小时,并用较为合理分组准则,提成22个组对问题4，研究了在不影响分组均衡条件下，T,t,V容许变化范畴,并得出了这三个变量关系式,并由此对分三个组状况进行了详细讨论。 核心词：最佳推销员回路问题哈米尔顿回路赋权图近似算法均衡度 一、问题重述1998年夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领关于部门负责人到全县各17个乡（镇）、35个村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地路线。(1)若分三组（路）巡视，试设计总路程最短且各组尽量均衡巡视路线。(2)假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完毕巡视，至少应分几组；给出这种分组下你以为最佳巡视路线。(3)在上述关于T，t和V假定下，如果巡视人员足够多，完毕巡视最短时间是多少；给出在这种最短时间完毕巡视规定下，你以为最佳巡视路线。(4)若巡视组数已定(如三组），规定尽快完毕巡视，讨论T，t和V变化对最佳巡视路线影响。二、问题分析 本题给出了某县公路网络图，规定是在不同条件下，灾情巡视最分组方案和路线.将每个乡（镇）或村看作一种图顶点，各乡镇、村之间公路看作此图相应顶点间边，各条公路长度（或行驶时间）看作相应边上权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权（路程或时间）最小.本题是旅行售货员问题延伸－多旅行售货员问题.本题所求分组巡视最佳路线，也就是m条通过同一点并覆盖所有其她顶点又使边权之和达到最小闭链（闭迹）.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.显然本问题更应属于NP完全问题.有鉴于此，一定要针对问题实际特点寻找简便办法，想找到解决此类问题普通办法是不现实，对于规模较大问题可使用近似算法来求得近似最优解.三、模型假设1．汽车在路上速度总是一定，不会浮现抛锚等现象；忽视天气、故障等因素影响。2．巡视当中，在每个乡镇、村停留时间一定，不会浮现特殊状况而延误时间；3．每个小组汽车行驶速度完全同样；4．分组后，各小组只能走自己区内路，不能走其她小组路，除公共路外。四、符号阐明……..任意两点，间间距。……..各点停留时间，即点权。………汽车行驶速度。………………从任意点至点时间，则。五、模型建立与求解公路网图中，每个乡（镇）或村看作图中一种节点，各乡（镇）、村之间公路看作图中相应节点间边，各条公路长度（或行驶时间）看作相应边上权，所给公路网就转化为加权网络图，问题就转化为在给定加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到O点，使得总权（路程或时间）最小，此即最佳推销员回路问题。在加权图G中求最佳推销员回路问题是NP—完全问题，咱们采用一种近似算法求出该问题一种近似最优解，来代替最优解，算法如下：算法一求加权图G（V，E）最佳推销员回路近似算法：用图论软件包求出G中任意两个顶点间最短路，构造出完备图，，；输入图一种初始H圈；用对角线完全算法（见[23]）产生一种初始H圈；随机搜索出中若干个H圈，例如个；对第2、3、4步所得每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈；在第5步求出所有H圈中，找出权最小一种，此即要找最佳H圈近似解.由于二边逐次修正法成果与初始圈关于，故本算法第2、3、4步分别用三种办法产生初始圈，以保证能得到较优计算成果。问题一：此问题是各种推销员最佳推销员回路问题.即在加权图G中求顶点集V划分，将G提成n个生成子图，使得（1）顶点i=1，2，3……n（2）（3），其中为导出子图中最佳推销员回路，为权，i，j=1，2，3……n（4）定义称为该分组实际均衡度。为最大容许均衡度。显然，越小，阐明分组均衡性越好.取定一种后，与满足条件（3）分组是一种均衡分组.条件（4）表达总巡视路线最短。此问题包括两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路，即为单个推销员最佳推销员问题。由于单个推销员最佳推销员回路问题不存在多项式时间内精准算法，故各种推销员问题也不存在多项式时间内精准算法.而图中节点数较多，为53个，咱们只能去谋求一种较合理划分准则，对图１1－9进行粗步划分后，求出各某些近似最佳推销员回路权，再进一步进行调节，使得各某些满足均衡性条件（3）。图11-10O点到任意点最短路图（单位：公里）从O点出发去其他点，要使路程较小应尽量走O点到该点最短路.故用图论软件包求出O点到别的顶点最短路，这些最短路构成一棵O为树根树，将从O点出发树枝称为干枝，见图１１－１0，从图中可以看出，从O点出发到其他点共有6条干枝，它们名称分别为①，②，③，④，⑤，⑥。图11-10O点到任意点最短路图（单位：公里）依照实际工作经验及上述分析，在分组时应遵从如下准则：准则一：尽量使同一干枝上及其分枝上点分在同一组；准则二：应将相邻干枝上点分在同一组；准则三：尽量将长干枝与短干枝分在同一组.由上述分组准则，咱们找到两种分组形式如下：分组一：（⑥，①），（②，③），（⑤，④）分组二：（①，②），（③，④），（⑤，⑥）显然分组一办法极不均衡，故考虑分组二。对分组二中每组顶点生成子图，用算法一求出近似最优解及相应巡视路线.使用算法一时，在每个子图所构造完备图中，取一种尽量包括图11-10中树上边H圈作为其第2步输入初始圈。分组二近似解见表1。表1（单位：公里）小组名称路线总路线长度路线总长度=1\*ROMANIO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O191.1558.5=2\*ROMANIIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-7-E-8-4-D-3-C241.9=3\*ROMANIIIO-R-29-Q-30-32-31-33-35-34-A-B-1-O125.5由于该分组均衡度=54.2%因此此分法均衡性很差。为改进均衡性，将第Ⅱ组中顶点C，2，3，D，4分给第Ⅲ组（顶点2为这两组公共点），重新分组后近似最优解见表2。表2（单位：公里）编号路线路线长度路线总长度=1\*ROMANIO—P—28—27—26—N—24—23—22—17—16—I—15—I—18—K—21—20—25—M—O191.1599.8=2\*ROMANIIO—2—5—6—7—E—8—E—9—F—10—F—12—H—14—13—G—11—J—19—L—6—5—2—O216.4=3\*ROMANIIIO—R—29—Q—30—32—31—33—35—34—A—1—B—C—3—D—4—D—3—2—O192.3因该分组均衡度11.69%因此这种分法均衡性较好。问题二由于T=2小时，t=1小时，V=35公里/小时，需访问乡镇共有17个，村共有35个.计算出在乡（镇）及村总停留时间为172+35=69小时，要在24小时内完毕巡回，若不考虑行走时间，有：(i为分组数).得i最小为4，故至少要分4组。由于该网络乡（镇）、村分布较为均匀，故有也许找出停留时间尽量均衡分组，当分4组时各组停留时间大概为小时，则每组分派在路途上时间大概为24-17.25=6.75小时.而前面讨论过，分三组时有个总路程599.8公里巡视路线，分4组时总路程不会比599.8公里大太多，不妨以599.8公里来计算.路上时间约为小时，若平均分派给4个组，每个组约需=4.25小时〈6.75小时，故提成4组是也许办到。当前尝试将顶点分为4组.分组原则：除遵从前面准则一、二、三外，还应遵从如下准则：准则四：尽量使各组停留时间相等。用上述原则在图11-10上将图分为4组，同步计算各组停留时间,然后用算法一算出各组近似最佳推销员巡回，得出路线长度及行走时间，从而得出完毕巡视近似最佳时间.用算法一计算时，初始圈输入与分三组时同样解决。这4组近似最优解见表3：表3（路程单位：公里；时间单位：小时）组名路线路线总长度停留时间行走时间完毕巡视总时间=1\*ROMANIO—2—5—6—7—E—8—E—11—G—12—H—12—F—10—F—9—E—7—6—5—2—O195.8175.5922.59=2\*ROMANIIO—R—29—Q—30—Q—28—27—26—N—24—23—22—17—16—17—K—22—23—N—26—P—O199.2165.6921.69=3\*ROMANIIIO—M—25—20—21—K—18—I—15—14—13—J—19—L—6—M—O159.1184.5422.54=4\*ROMANIVO—R—A—33—31—32—35—34—B—1—C—3—D—4—D—3—2—O166184.7422.74上表中符号阐明：加有底纹表达前面通过并停留过，本次只通过不需停留；加框表达此点只通过不断留。该分组实际均衡度=4.62%可以看出，表3分组均衡度较好，且完全满足24小时完毕巡视规定。问题三咱们发现从O点巡视H点最短时间是所有最短时间中最长，其距离为77.5公里。其时间为因而，T=2小时，t=1小时，V=35公里/小时。若巡视人员足够多，完毕巡视最短时间为6.43小时。在最短时间内限定一下，完毕巡视最优路线应满足如下条件：每个组巡视总时间不能超过最短时间；所有点都必要访问到，不能漏点；所需巡视组数要尽量少；在谋求最优路线时，从距离O点较远某些点（如点12、10、15、22）开始搜索比较容易，由于到这些点路线比较少。详细办法如下：第一步：根据图1算出从O点到每一种点最短距离;第二步：找出其中最大一种，算出从O点沿最短路巡视时间，并求出;第三步：若则这一组只能访问这一点；若则在余下点找到距离O点最远点，依照条件看这一组能否巡视这一点；第四步：若能巡视，则算出，转到第三步；第五步：若不能则依次判断次远点、第三远点……,满足总巡视时间不超过，就让这组巡视到这一点，直到然后再从第二步开始。通过以上办法，最后咱们找到最优解是22个组，如下表所示：编号巡视途径停留地点所需时间时间差1O-H-OH6.4302O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-013,146.150.283O-M-25-21-K-18-I-15-I-16-17-K-21-25-M-O15,166.310.124O-2-5-6-7-E-9-F-12-G-11-E-7-6-5-2-O12,115.940.495O-2-5-6-7-E-8-E-9-F-10-F-9-E-7-6-5-2-O8,106.220.216O-2-5-6-7-E-11-G-11-E-7-6-5-2-OG5.580.857O-2-5-6-7-E-9-F-9-E-7-6-5-2-O9,F6.140.298O-2-5-6-L-19-J-18-K-21-25-M-OJ,186.290.149O-M-25-21-K-18-I-18-K-21-25-M-OI5.490.9410O-M-25-21-K-17-22-23-N-26-P-O17,22,236.120.3111O-2-5-G-L-19-L-6-5-2-OL,195.640.7912O-M-25-20-21-23-24-N-26-P-O20,21,246.100.3313O-M-25-21-K-21-25-M-O25,K5.500.9314O-2-5-6-7-E-7-6-5-2-O6,7,E6.380.0515O-R-31-32-35-34-A-1-O31,32,35,346.320.1116O-R-29-Q-30-Q-28-P-OQ,30,286.110.3217O-P-26-27-26-N-26-P-O26,27,N6.230.2018O-2-3-D-4-D-3-2-O3,D,45.990.4419O-1-A-33-31-R-29-R-OA,33,295.970.4620O-2-5-M-O2,5,M5.401.0321O-1-B-C-O1,B,C5.980.4522O-P-O-R-OP,R5.321.11问题四巡视组数已定，规定尽快完毕巡视，讨论T，t和V变化对最佳巡视路线影响。要尽快完毕巡视，就得规定每组完毕巡视时间尽量均衡，由于总完毕巡视时间按最长完毕巡视时间计算。当前讨论在均衡度容许范畴内已提成n组后，变化T，t和V对最佳巡视路线影响。显然在分组不变状况下，无论了T,t、V如何变化，对每组内最佳巡视路线是没有影响，但也许会影响各组间均衡性。因而该问题事实上讨论T，t和V对于分组影响，即在不破坏本来分组均衡条件下，T，t和V容许最大变化范畴。在分n组状况下，设：表达第i组最佳推销员回路路线总长度；：表达第i组所要停留乡镇数目；：表达第i组所要停留村数目；i=1,2,3,…,n显然，当时，即每组乡（镇）数、村数、最佳巡回长度均相等，因而分组绝对均衡时，即=0时，无论T，t和V如何变化都不会变化本来分组均衡。不影响分组均衡时，T，t和V最大容许变化范畴讨论：对任意一种组i，其完毕巡视时间设均衡分组最大容许时间均衡度为，即则有记则表达均衡分组所容许最大时间误差，则(1)由（1）式咱们得到（2）由式（2）可得当>0时，要保持原均衡分组不变，T必要满足条件为（3）2.当时，要保持原均衡分组不变，t必要满足条件为(4)3.当>0时，由（2）式得当有当时，有（6）由（3）—（6）式，当T,t,V三个变量中任意两个变量无论如何变化，都可计算出为保持均衡性分组不变，三个变量所容许最大变化范畴。（二）分三组实例讨论现对分三组状况进布寸论对问题一中所得三个分组若考虑停留时间和行驶时间且取小时，小时，公里/小时，成果如表5：表5（路程单位：公里；时间单位：小时）编号行驶时间总时间=1\*ROMANI513191.15.4628.46=2\*ROMANII611192.35.4928.49=3\*ROMANIII611216.46.1829.18实际均衡度为。实际时间误差为小时。现分别规定均衡分组最大容许均衡度和，即最大容许时间误差分别为小时和小时，计算出T,t,V三个参量中固定任意两个时，要不破坏原均衡分组，另一种参量所容许变化范畴，成果如下表：表6V,t不变T,V不变T,t不变上表可以看出：（1）当实际均衡度刚好等于最大容许均衡度时，要保持原均衡分组，当t，V不变时，T只能减小，且下界为1.25小时；T上界为小时；T，V不变时，t只能增大，且上界为1.38小时；t下界为小时；t，T不变时，V只能增大，且下界为35；无上界；（2）当实际均衡度不大于最大容许均衡度时，即时要保持原均衡分组，当t，V不变时，T变化下界为0.51小时；T上界为2.74小时；T，V不变时，t上界为1.75小时；t下界为0.63小时；t，T不变时，V增大但无上界，且下界为17.3公里/小时；（三）对实例成果分析上述实例均衡分组有一种特点，各组停留时间相等,即取小时，小时，公里/小时，在表5分组中定义4各组停留时间相等均衡分组称为停留时间相等均衡分组，由（7）式得现讨论对停留时间相等均衡分组,T,t,V变化规律，对停留时间相等均衡分组，分组实际时间误差：其中，为使最大组标号；为使最小组标号。（*）当T,t不变时,即,时，因由（6）式懂得，要保持平衡分组,V下界应为取时，由（9）式得时，由（9）式得故有如下定