线路的优化模型

1、I加另就彳M A A与Shenyang Aerospace University数学模型课程结业论文线路的优化模型任务书要求1、将所给的问题翻译成汉语；2、给论文起个题目（名字或标题）3、根据任务来完成数学模型论文；4、论文书写格式要求按给定要求书写；5、态度要认真，要独立思考，独立完成任务；6、论文上交时间：6月1日前（要求交纸质论文和电子文档）。7、严禁抄袭行为，若发现抄袭，则成绩记为“不及格”。任务下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公 里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有 关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所

2、在地 出发，走遍各乡（镇）、村，又回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡 视路线。假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间 t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡 视，至少应分几组；给出这种分组下你认为最佳的巡视路线。在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡 视的最短时间是多少；给出在这种最短时间完成巡视的要求下， 你认为最佳的巡视路线。若巡视组数已定（如三组），要求尽快完成巡视，讨论T，t和V 改变对最佳巡视路线的影响。成绩评定单评语：成绩任课 年月日摘要本题是一个有深刻背景的NPC问题

3、，文章分析了分组回路的拓扑结构，并构 造了多个模型，从多个侧面对具体问题进行求解，最短树结构模型给出了局部寻优 的原则，算法模型体，算法模型体现了由简到繁，确保较优的思想；而三个层次分 明的表述模型证明了这一类问题共有的性质。在此基础上，我们的结果也是比较令 人满意的，如对第一题给了总长599.9，单项长为216的分组，第二题给出了至少 分四组的证明。最后，我们还谈到了模型的优缺点及推广思想。关键词：关键词1；关键词2；关键词3；关键词4目录1第1级标题错误！未定义书签。1.1目录1第1级标题错误！未定义书签。1.1.1第3级标题1.1.2第3级标题1.2第2级标题1.2.1第3级标题1.2.

4、2第3级标题1.2.3第3级标题1.3第2级标题错误！未定义书签。错误！未定义书签。错误！未定义书签。错误！未定义书签。错误！未定义书签。错误！未定义书签。错误！未定义书签。错误！未定义书签。错误！未定义书签。错误！未定义书签。错误！未定义书签。错误！未定义书签。附录I程序清单错误！未定义书签。附录I程序清单论文正文：正文所含内容：标题：问题提出（问题重述）：模型假设模型的建立：模型求解（算法设计和计算机实现）：结果（数据、图形）。结果分析和检验（如误差分析、统计检验、灵敏性检验）：优缺点，改进方向：参考文献附录（程序、更多的计算结果、复杂的推导、证明等）。1.1.标题:线路的优化模型问题提出

5、1998年夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领 有关部门负责人到全县各17个乡（镇）、35个村巡视。巡视路线指从县政府所 在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。（1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视 路线。（2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1 小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少 应分几组；给出这种分组下你认为最佳的巡视路线。（3）在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视 的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最 佳的巡视路

6、线。（4）若巡视组数已定（如三组），要求尽快完成巡视，讨论T，t和V改 变对最佳巡视路线的影响。问题重述本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的 最分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公 路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权， 所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题， 即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点0, 使得总权（路程或时间）最小.本题是旅行售货员问题的延伸一多旅行售货员问题.本题所求的分组巡视的最 佳路线，也就是m条经过同一点并覆盖所

7、有其他顶点又使边权之和达到最小的闭链 （闭迹）.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.显 然本问题更应属于NP完全问题.有鉴于此，一定要针对问题的实际特点寻找简便 方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近 似算法来求得近似最优解.3.3.模型假设汽车在路上的速度总是一定，不会出现抛锚等现象；忽略天气、故障等因素的 影响。巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；每个小组的汽车行驶速度完全一样；分组后，各小组只能走自己区内的路，不能走其他小组的路，除公

8、共路外。4.模型的建立和模型求解及结果w（i,jw（i,j）.任意两点i，j间的间距。七.各点的停留时间，即点权。v汽车行驶速度。d.从任意点i全点j的时间，则jd. = w（i, j）/V。j（2）模型的建立公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公 路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权， 所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定 点O出发，行遍所有顶点至少一次再回到O点，使得总权（路程或时间）最小，此 即最佳推销员回路问题。在加权图G中求最佳推销员回路问题是NP完全问题，我们采用一种近似算法 求出

9、该问题的一个近似最优解，来代替最优解，算法如下：算法一求加权图G （V，E）算法一求加权图G （V，E）的最佳推销员回路的近似算法：用图论软件包求出G中任意两个顶点间的最短路，构造出完备图Gr（V,E），V（x, y ）e E， s G, y）= MindgG, y）；输入图G的一个初始H圈；用对角线完全算法（见23）产生一个初始H圈；随机搜索出G中若十个H圈，例如2000个；对第2、3、4步所得的每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈；在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳H圈的 近似解.1.2.3.4.5.6.由于二边逐次修正法的结果与初始圈有关，故本算法

10、第2、3、4步分别用三种 方法产生初始圈，以保证能得到较优的计算结果。模型求解及结果问题一：此问题是多个推销员的最佳推销员回路问题.即在加权图G中求顶点集V的划分 匕,匕， 匕，将G分成n个生成子图0gV2.gv 使得（1） 顶点 O eVi=1，2，3ni（2）n Vi = v （g ）（3）y （q 1 心L，其中C为v.的导出子图gV中的最佳推销员tf- W aC iiiMaxw （C ）i回路，sCJ为q的权，i, j=1, 2, 3n（4）葺 w （C ） = Mini定义 称以MaX （Ci ） w（CJ为该分组的实际均衡度。a为最大容许均a =。 Max w （C ）ii衡度。显

11、然。a。 1，a0越小，说明分组的均衡性越好.取定一个a后，a。与a满足 条件（3）的分组是一个均衡分组.条件（4）表示总巡视路线最短。此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路， 即为单个推销员的最佳推销员问题。由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故多 个推销员的问题也不存在多项式时间内的精确算法.而图中节点数较多，为53个， 我们只能去寻求一种较合理的划分准则，对图1 1 9进行粗步划分后，求出各部分 的近似最佳推销员回路的权，再进一步进行调整，使得各部分满足均衡性条件（3）。2 (1)9322 (1)932302712/色1平8d-31

12、(7.9l2.1覆j嵯!7.4趴 X1IL1(7.9i-l.J工 7.3M.8 L从O点出发去其它点，要使路程较小应尽量走O点到该点的最短路.故用图论软件包求出O点到其余顶点的最短路，这些最短路构成一棵O为树根的树，将从O点出发的树枝称为十枝，见图11 1 0，从图中可以看出，从O点出发到其它点共有6条十枝，它们的名称分别为，。根据实际工作的经验及上述分析，在分组时应遵从以下准则：准则一：尽量使同一十枝上及其分枝上的点分在同一组；准则二：应将相邻的十枝上的点分在同一组；准则三：尽量将长的十枝与短的十枝分在同一组.由上述分组准则，我们找到两种分组形式如下：分组一：（，），（，），（，）分组二：（

13、，），（，），（，）显然分组一的方法极不均衡，故考虑分组二。对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路线. 使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图11-10中树上的 边的H圈作为其第2步输入的初始圈。所以此分法的均衡性很差。为改善均衡性，将第II组中的顶点所以此分法的均衡性很差。为改善均衡性，将第II组中的顶点C，2, 3, D，4分给第III组（顶点2为这两 组的公共点），重新分组后的近似最优解见表2。小组名称路线总路线长 度路线 的总 长度IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-

14、O191.1558.5IIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-7-E-8-4-D-3-C241.9IIIO-R-29-Q-30-32-31-33-35-34-A-B-1-O125.5表1 （单位：公里）因为该分组的均衡度a广打以-8（C 2）= 241.9 - 125.5 = 54.2%Max （C. ） 一 241 .9i=1,2,31表2 （单位：公里）编号路线路线长度路线总 长度IOP282726N24232217 16I15I18K212025MO191.1599.8IIO2567E8E9F10F 12H 1413G 11J 19L65

15、2O216.4IIIOR29Q303231333534A 1BC3D4D32O192.3因该分组的均衡度a 0Max因该分组的均衡度a 0MaxW（C 216.4 191.1216.4=11.69%i=1,2,3 所以这种分法的均衡性较好。问题二由于T=2小时，t=1小时，V=35公里/小时，需访问的乡镇共有17个，村共有 35个.计算出在乡（镇）及村的总停留时间为17x 2+35=69小时，要在24小时内完 .一，. 69 一，.,成巡回，若不考虑行走时间，有：69 24 （i为分的组数）.得i最小为4,故全i少要分4组。由于该网络的乡（镇）、村分布较为均匀，故有可能找出停留时间尽量均衡的6

16、9分组，当分4组时各组停留时间大约为69 = 17.25小时，则每组分配在路途上的时4间大约为24-17.25=6.75小时.而前面讨论过，分三组时有个总路程599.8公里的 巡视路线，分4组时的总路程不会比599.8公里大太多，不妨以599.8公里来计算.599 817,路上时间约为-99 = 17小时，若平均分配给4个组，每个组约需一=4.25小时6.75354小时，故分成4组是可能办到的。现在尝试将顶点分为4组.分组的原则：除遵从前面准则一、二、三外，还应遵 从以下准则：准则四：尽量使各组的停留时间相等。用上述原则在图11-10上将图分为4组，同时计算各组的停留时间，然后用算法 一算出各

17、组的近似最佳推销员巡回，得出路线长度及行走时间，从而得出完成巡视 的近似最佳时间.用算法一计算时，初始圈的输入与分三组时同样处理。这4组的近似最优解见表3：表3 （路程单位：公里；时间单位：小时）组名路线路线 总长度停留时间行走 时间完成巡视 的总时间IO G- 9.2567E8E11 12H 12F 10F E7652O195.8175.5922.59IIO 2 16一 P（R29Q30Q2827 6N242322 17 -17 K2223N26 O199.2165.6921.69IIIOM252021K 18 1514 13J 19L MOI6159.1184.5422.54IVO 34一

18、 2RA33313235- _B1C3D4D O一3166184.7422.74上表中符号说明：加有底纹的表示前面经过并停留过，此次只经过不需停留;加框的表示此点只经过不停留。该分组实际均衡度 = 22.74 21.69 = 4.62%022.74可以看出，表3分组的均衡度很好，且完全满足24小时完成巡视的要求。问题二我们发现从O点巡视H点的最短时间是所有最短时间中最长的，其距离为77.5 公里。其时间为775.t =x2 + 2 = 6.43 小时 H 35因此，T=2小时，t=1小时，V=35公里/小时。若巡视人员足够多，完成巡视的 最短时间为6.43小时。在最短时间内限定一下，完成巡视的

19、最优路线应满足如下条件：每个组巡视的总时间不能超过最短时间七=6.43小时；所有点都必须访问到，不能漏点；所需巡视组数要尽量少；在寻求最优路线时，从距离O点较远的一些点(如点12、10、15、22)开始搜 索比较容易，因为到这些点的路线比较少。具体方法如下：第一步：依据图1算出从O点到每一个点的最短距离；第二步：找出其中最大的一个，算出从o点沿最短的路巡视的时间ti，并求出 t = t t ;H i第二步：若At 1,则在余下的点找到距离O 点最远的点，根据条件看这一组能否巡视这一点；第四步：若能巡视，则算出At，转到第二步；第五步：若不能则依次判断次远点、第二远点，满足总巡视时间不超过七，就

20、让这组巡视到这一点，直到At 1,然后再从第二步开始。H通过以上方法，最后我们找到的最优解是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

21、-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-

22、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

23、-OP,R5.321.11问题四巡视组数已定，要求尽快完成巡视，讨论T, t和V的改变对最佳巡视路线的 影响。要尽快完成巡视，就得要求每组完成巡视时间尽量均衡，因为总的完成巡视 时间按最长的完成巡视时间计算。现在讨论在均衡度允许的范围内已分成 n组后，改变T，t和V对最佳巡视路线的影响。显然在分组不变的情况下，无论了 T,t、V如何改变，对每组内的最佳巡视路线是没有影响的，但可能会影响各组间 的均衡性。因此该问题实际上讨论T，t和V对于分组的影响，即在不破坏原来分 组均衡的条件下，T，t和V允许的最大变化范围。在分n组的情况下，设S：表示第i组的最佳推销员回路路线总长度；X :表示第i组所要停

24、留的乡镇的数目；丫；表示第i组所要停留的村的数目；ii=1,2,3,，n显然，当X = X , Y = Y, S = S ; i, j = 1,2,3,员，即每组的乡（镇）数、村数、I j i j i j最佳巡回的长度均相等，因而分组绝对均衡时，即a 0 =0时，无论T，t和V如何改变都不会改变原来分组的均衡。（一）不影响分组的均衡时，T, t和V的最大允许变化范围的讨论: 对任意一个组i，其完成巡视的时间S 一T = X T+Yt + r, i 1,2,3,.,n设均衡分组的最大允许时间均衡度为a，即-一i - a i, j = 123 nMax T 1，2,3,ni=i,2,3,. ,n贝

25、临 T -T a x MaxTi=1,2,3,. n记8 =ax MaxT，则e表示均衡分组所允许的最大时间误差，则ii=1,2,3,., n TOC o 1-5 h z S S,、(X- X )T + (Y- Y )t + i j 8(1)由(1)式我们得到8 (X X )T + (Y Y )t + Si -Sj e(2)i j i j VMax -8-（匕- j+十 1 T Min8Max -8-（匕- j+十 1 T 0X XX X 0X X1 j .1 j .由式(2)可得1.当X X 0时，要保持原均衡分组不变，T必须满足的条件为i j2.当Y Y 0时，要保持原均衡分组不变，t必须

26、满足的条件为ij（3）Max 01S S 18 (X X )t _j一 T 0Y Y1 j8 (X X )t Si - S ji j VY Yij3.当S -S 0时，由(2)式得(X X )T + (Y Y )t 8 Si -Sj 8(X X )T (Y Y )ti j i jVi j i j 当(X. -X )T + (Y Y )t max 8 时，有8V max 0（5）(j) j ()8-W X ) T - Y Y ) ti j i jX )& Y ) t 8i ji j V min 0（6）由（3）（6）式，当T,t,V三个变量中任意两个变量无论如何变化，都可计算出 为保持均衡性分组

27、不变，三个变量所允许的最大变化范围。（二）分三组的实例讨论论 对问题一中所得的三个分组 若考虑停留时间和 t 论 对问题一中所得的三个分组 若考虑停留时间和 t = t = 1小时，V =匕=35公里/小时，结果如表5：行驶时间且取T = T = 2小时编号XYS行驶时间总时间I513191.15.4628.46II611192.35.4928.49III611216.46.1829.18o一一表5 （路程单位：公里；时间单位：小时）29.18 28.46实际均衡度为a = 2.5%。29.18实际时间误差为 = 2.5% x29.18 = 0.72小时。现分别规定均衡分组的最大允许均衡度a

28、= 2.5%和a = 5%，即最大容许的时间 误差分别为 = 0.72小时和 = 1.44小时，计算出T,t,V三个参量中固定任意两个时， 要不破坏原均衡分组，另一个参量所容许的变化范围，结果如下表：表6V,t不变T,V不变T,t不变a = 2.5% = 0.72小时1.25 T 21 t 35a= 5% = 1.44小时0.51 T 2.740.63 t 17.3上表可以看出：（1）当实际均衡度a0 = 2.5%刚好等于最大容许均衡度a = 2.5%时，要保持原 均衡分组，当t，V不变时，T只能减小，且下界为1.25小时；T的上界为T0 = 2小 时；T，V不变时，t只能增大，且上界为1.3

29、8小时；t的下界为t = 1小时；0t，T不变时，V只能增大，且下界为35；无上界；（2）当实际均衡度a = 2.5%小于最大容许均衡度a = 5%时，即。时要保持 原均衡分组，当t，V不变时，T变化的下界为0.51小时；T的上界为2.74小时；T，V不变时，t的上界为1.75小时；t的下界为0.63小时；t，T不变时，V增大但无上界，且下界为17.3公里/小时；（三）对实例结果的分析上述实例的均衡分组有一个特点，各组的停留时间相等，即取T = T = 2小时，t = t0 = 1小时，V = V = 35公里/小时，、在表5的分组中G X）.T - Y Y）t = 0, i, j = 1,2

30、,3（7）i j 0 i j 0定义4各组的停留时间相等的均衡分组称为停留时间相等的均衡分组，由（7）式 得T = % -1 , X - X。0,i, j = 1,2,3（8）0 X X 0 i j现讨论对停留时间相等的均衡分组，T,t,V的变化规律，对停留时间相等的均衡分 组，分组的实际时间误差： = = max0i, jx).t +YQ. t + H TOC o 1-5 h z =max JI i j = S S（9）i,j I V J V 00其中，i为使S,最大的组的标号；j为使.最小的组的标号。（*）当 T,t 不变时，即 T = T , t = t 时，因 & X）.T +Y Y） t = 0 0sX)T Yi jiY ) tj