1998年全国大学生数学建模竞赛题.docx

《1998年全国大学生数学建模竞赛题.docx》由会员分享，可在线阅读，更多相关《1998年全国大学生数学建模竞赛题.docx（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、假如巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你以为最佳的巡视道路。(4)若巡视组数已定(如三组，要求尽快完成巡视，讨论T，t和V改变对最佳巡视道路的影响。灾情巡视道路模型摘要本文将求最佳巡视道路间题转化为图论中求最佳推销员回路哈米尔顿回路的问题,并用近似算法去寻求近似最优解。对赋权图中的途径分组问题定义了平衡度用以衡量分组的平衡性。对问题1和问题2先定出几个分的准则进行初步分组,并用近似算法求每一组的近似最佳推销员回路,再根据平衡度进行微调,得到较优的平衡分组和每组的近似最佳推销员回路。对问题1，运用求任意两点间最短路的Floyd算法,得出总路程较短且各组

3、尽可能平衡的道路,各组的巡视路程分别为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年夏天某县遭受水灾。为考察灾情、组织自救

4、，县领导决定，带领有关部门负责人到全县各17个乡镇、35个村巡视。巡视道路指从县政府所在地出发，走遍各乡镇、村，又回到县政府所在地的道路。(1)若分三组路巡视，试设计总路程最短且各组尽可能平衡的巡视道路。(2)假定巡视人员在各乡镇停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你以为最佳的巡视道路。(3)在上述关于T,t和V的假定下，假如巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你以为最佳的巡视道路。(4)若巡视组数已定(如三组，要求尽快完成巡视，讨论T，t和V改变对最佳巡视道

5、路的影响。二、问题分析此题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最分组方案和道路.将每个乡镇或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度或行驶时间看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权路程或时间最小.此题是旅行售货员问题的延伸多旅行售货员问题.此题所求的分组巡视的最佳道路，也就是m条经过同一点并覆盖所有其他顶点又使边权之和到达最小的闭链闭迹.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.众所周知

6、，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.显然本问题更应属于NP完全问题.有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.三、模型假设1汽车在路上的速度总是一定，不会出现抛锚等现象；忽略天气、故障等因素的影响。2巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；3每个小组的汽车行驶速度完全一样；4分组后，各小组只能走本人区内的路，不能走其他小组的路，除公共路外。四、符号讲明(,)wij.任意两点i，j间的间距。ie.各点的停留时间，即点权。V汽车行驶速度。ijd从任意点

7、i至点j的时间，则(,)/ijdwijV。五、模型建立与求解公路网图中，每个乡镇或村看作图中的一个节点，各乡镇、村之间的公路看作图中对应节点间的边，各条公路的长度或行驶时间看作对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到O点，使得总权路程或时间最小，此即最佳推销员回路问题。在加权图G中求最佳推销员回路问题是NP完全问题，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下：算法一求加权图GV，E的最佳推销员回路的近似算法：1用图论软件包求出G中任意两个顶点间的最短路，构造出完备图),(EVG，()E

8、yx?,，()()yxMindyxG,=；2输入图G的一个初始H圈；3用对角线完全算法见23产生一个初始H圈；4随机搜索出G中若干个H圈，例如2000个；5对第2、3、4步所得的每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈；6在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳H圈的近似解.由于二边逐次修正法的结果与初始圈有关，故本算法第2、3、4步分别用三种方法产生初始圈，以保证能得到较优的计算结果。问题一：此问题是多个推销员的最佳推销员回路问题.即在加权图G中求顶点集V的划分12,.nVVV，将G分成n个生成子图nVGVGVG,.,21，使得1顶点iOVi=1，2，3n2()

9、1niiVVG=3()()(),ijijiiwMaxCwCMaxwC-，其中iC为iV的导出子图iVG中的最佳推销员回路，()iC为iC的权，i，j=1，2，3n4()1niiwCMin=定义称()()(),0ijijiiMaxwCwCMaxwC-=为该分组的实际平衡度。为最大容许平衡度。显然100，0越小，讲明分组的平衡性越好.取定一个后，0与知足条件3的分组是一个平衡分组.条件4表示总巡视道路最短。此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路，即为单个推销员的最佳推销员问题。由于单个推销员的最佳推销员回路问题不存在多项式时间内的准确算法，故多个推销员的问题也不存在多项

10、式时间内的准确算法.而图中节点数较多，为53个，我们只能去寻求一种较合理的划分准则，对图19进行粗步划分后，求出各部分的近似最佳推销员回路的权，再进一步进行调整，使得各部分知足平衡性条件3。从O点出发去其它点，要使路程较小应尽量走O点到该点的最短路.故用图论软件包求出O点到其余顶点的最短路，这些最短路构成一棵O为树根的树，将从O点出发的树枝称为干枝，见图0，从图中能够看出，从O点出发到其它点共有6条干枝，它们的名称分别为，。根据实际工作的经历及上述分析，在分组时应遵从下面准则：准则一：尽量使同一干枝上及其分枝上的点分在同一组；准则二：应将相邻的干枝上的点分在同一组；准则三：尽量将长的干枝与短的

11、干枝分在同一组.由上述分组准则，我们找到两种分组形式如下：分组一：，分组二：，显然分组一的方法极不平衡，故考虑分组二。对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视道路.使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图11-10中树上的边的H圈作为其第2步输入的初始圈。分组二的近似解见表1。表1单位：公里小组名称道路总道路长度道路的总长度IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O191.1558.5IIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-7-E-8-4

12、-D-3-C241.9IIIO-R-29-Q-30-32-31-33-35-34-A-B-1-O125.5图11-10O点到任意点的最短路图单位：公里由于该分组的平衡度0=()()()=-=-=9.2415.1259.2413,2,121iiCMaxCC54.2%所以此分法的平衡性很差。为改善平衡性，将第组中的顶点C，2，3，D，4分给第组顶点2为这两组的公共点，重新分组后的近似最优解见表2。表2单位：公里编号路线道路长度道路总长度IOP282726N2423221716I15I18K212025MO191.1599.8IIO2567E8E9F10F12H1413G11J19L652O216.

13、4IIIOR29Q303231333534A1BC3D4D32O192.3因该分组的平衡度=0()()()=-=-=4.2161.1914.2163,2,113iiCMaxCC11.69%所以这种分法的平衡性较好。问题二由于T=2小时，t=1小时，V=35公里/小时，需访问的乡镇共有17个，村共有35个.计算出在乡镇及村的总停留时间为17?2+35=69小时，要在24小时内完成巡回，若不考虑行走时间，有:2469IO2567E8E11G12H12F10F9E7652O195.8175.5922.59IIOR29Q30Q282726N242322171617K2223N26PO199.2165.

14、6921.69IIIOM252021K18I151413J19L6MO159.1184.5422.54IVORA3331323534B1C3D4D32O166184.7422.74上表中符号讲明：加有底纹的表示前面经过并停留过，此次只经过不需停留；加框的表示此点只经过不停留。该分组实际平衡度0=-74.2269.2174.224.62%能够看出，表3分组的平衡度很好，且完全知足24小时完成巡视的要求。问题三我们发现从O点巡视H点的最短时间是所有最短时间中最长的，其距离为77.5公里。其时间为因而，T=2小时，t=1小时，V=35公里/小时。若巡视人员足够多，完成巡视的最短时间为6.43小时。在

15、最短时间内限定一下，完成巡视的最优道路应知足如下条件：1每个组巡视的总时间不能超过最短时间Ht6.43=小时；2所有点都必须访问到，不能漏点；3所需巡视组数要尽量少；在寻求最优道路时，从距离O点较远的一些点如点12、10、15、22开场搜索比拟容易，由于到这些点的道路比拟少。详细方法如下：第一步：根据图1算出从O点到每一个点的最短距离;第二步：找出其中最大的一个，算出从O点沿最短的路巡视的时间it，并求出Hittt=-;第三步：若1,t?则在余下的点找到距离O点最远的点，根据条件看这一组能否巡视这一点；第四步：若能巡视，则算出t?，转到第三步；第五步：若不能则依次判定次远点、第三远点,知足总巡

16、视时间不超过Ht，就让这组巡视到这一点，直到1,t?3O-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

17、.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

18、-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的改变对最佳巡视道路的影响。要尽快完成巡视,就得要求每组完成巡视时间尽量平衡,由于总的完成巡视时间按最长的完成巡视时间计算。如今讨论在平衡度允许的范围

19、内已分成n组后，改变T，t和V对最佳巡视道路的影响。显然在分组不变的情况下,无论了T,t、V怎样改变,对每组内的最佳巡视道路是没有影响的，但可能会影响各组间的平衡性。因而该问题实际上讨论T，t和V对于分组的影响，即在不毁坏原来分组平衡的条件下，T，t和V允许的最大变化范围。在分n组的情况下，设iS：表示第i组的最佳推销员回路道路总长度；iX：表示第i组所要停留的乡镇的数目；iY：表示第i组所要停留的村的数目；i=1,2,3,n显然，当,;,1,2,3,nijijijXXYYSSij=时，即每组的乡镇数、村数、最佳巡回的长度均相等，因此分组绝对平衡时，即0=0时，无论T，t和V怎样改变都不会改变

20、原来分组的平衡。一不影响分组的平衡时，T，t和V的最大允许变化范围的讨论：对任意一个组i，其完成巡视的时间设平衡分组的最大允许时间平衡度为，即则有1,2,3,ijiinTTMaxT=-?记1,2,3,iinMaxT=?则表示平衡分组所允许的最大时间误差，则()()ijijijSSXXTYYtV-+-+(1)由1式我们得到()()ijijijSSXXTYYtV-+-+2由式2可得1.当ijXX-0时，要保持原平衡分组不变，T必须知足的条件为00()()ijijijijijijXXXXijijSSSSYYtYYtVVMaxTMinXXXX-?-+-?-?32.当0ijYY-时，要保持原平衡分组不变

21、，t必须知足的条件为00()()ijijijijijijYYYYijijSSSSXXtXXtVVMaxTMinYYYY-?-?-?(4)3.当ijSS-0时，由2式得当()()ijijXXTYYt-+-时，有当()()?-?-tYYTXXjiji时，有()()?-?-?-tYYTXXSSVjijijiSSji0min6由36式，当T,t,V三个变量中任意两个变量无论怎样变化，都可计算出为保持平衡性分组不变，三个变量所允许的最大变化范围。二分三组的实例讨论现对分三组的情况进布寸论对问题一中所得的三个分组若考虑停留时间和行驶时间且取20=TT小时，10=tt小时，350=VV公里/小时，结果如表5

22、：表5路程单位：公里；时间单位：小时编号行驶时间总时间I513191.15.4628.46II611192.35.4928.49III611216.46.1829.18实际平衡度为%5.218.2946.2818.290=-=。实际时间误差为72.018.29%5.20=?=小时。现分别规定平衡分组的最大允许平衡度%5.2=和%5=，即最大容许的时间误差分别为72.0=小时和44.1=小时，计算出T,t,V三个参量中固定任意两个时，要不毁坏原平衡分组，另一个参量所容许的变化范围，结果如下表：表6V,t不变T,V不变T,t不变上表能够看出：1当实际平衡度%5.20=恰好等于最大容许平衡度%5.2

23、=时，要保持原平衡分组，当t，V不变时，T只能减小，且下界为1.25小时；T的上界为20=T小时；T，V不变时，t只能增大，且上界为1.38小时；t的下界为10=t小时；t，T不变时，V只能增大，且下界为35；无上界；2当实际平衡度%5.20=小于最大容许平衡度%5=时，即时，由9式得故有下面定理定理当000,ttTTVV=时,对图进行停留时间相等的平衡分组后,设该分组的实际时间误差为0。1若取最大允许时间误差0=,当T,t不变时,要使该平衡分组保持不变,V的下界为0V即V只能增加不能减少；2若取最大允许时间误差0优点1、本文提出的分组准则简便易行,可操作性强,且可逐步调整使分组到达平衡；2、

24、用平衡度的概念定量的刻画了分组的平衡性；3、在用近似算法求近似最佳推销员回路时,采取了三种不同的方法产生初始圈,使得算法比拟完善,得到了误差很小的近似最优解；4、从理论上定量地讨论了T,V,t的变化又中平衡分组灵敏度的影响,得到了很好的结果。缺点略六、参考文献1赵静，数学建模与数学实验第三版，北京：高等教育出版社，2020；2胡运权，运筹学基础及应用第三版，哈尔滨：哈尔滨工业大学出版社，1998；3孙惠泉，图论及其应用，北京：科学出版社，2004。附录用Floyd算法求赋权图中任意两点间最短途径及路长,MATLAB程序代码如下：n=53;A=xlsread(D:file1.xls);D=A;%赋初值for(i=1:n)for(j=1:n)R(i,j)=j;end;end%赋途径初值for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j)当前位置：文档视界1998年全国大学生数学建模竞赛题1998年全国大学生数学建模竞赛题