数学建模路线优化问题

1、选路的优化模型摘要:本题是一个有深刻背景的NPC问题，文章分析了分组回路的拓扑结构，并构造了多个模型，从多个侧面对具体问题进行求解。最短树结构模型给出了局部寻优的准则算法模型体现了由简到繁，确保较优的思想而三个层次分明的表述模型证明了这一类问题共有的性质。在此基础上我们的结果也是比较令人满意的。如对第一题给出了总长为599.9，单项长为216的分组，第二题给出了至少分四组的证明。最后，我们还谈到了模型的优缺点及推广思想。一、问题描述“水大无情，人命关天”为考察灾情，县领导决定派人及早将各乡（镇），村巡视一遍。巡视路线为从县政府所在地出发，走遍各乡（镇），村又回到县政府所在地的路线。1. 若分三

2、组巡视，试设计总路程最短且各组尽可能均衡的巡视路线。2. 假定巡视人员在各乡（镇）停留时间为T=2小时，在各村停留时间为 t =1 小时， 汽车行驶速度为V=35公里/时，要在24小时内巡视完，至少分成几组；给出这种分组下你认为最佳的巡视路线。3. 上述关于T，t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少？给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 4. 巡视组数已定（如三组）要求尽快完成巡视，讨论T，t和V改变时最佳路线的影响（图见附录）。二、问题假设1、乡（镇）村只考察一次，多次经过时只计算一次停留时间。 2、非本县村不限制通过。3、汽车的行驶速度始终一致

3、。三、符号说明符号表示意义Ti第i 人走的回路Ti=vvi(i) v2(i) vn(i) Ti=00表示第i人在0点没移动ViTi的点集SiTi的长度Hi(v)在V上定义的特殊函数仅当V被第i 人走过且停留时Hi(v)=1,否则为0四、模型建立在这一节里，我们将提出若干个模型及其特点分析，不涉及对题目的求解。 最简树结构模型 在这个模型中我们依靠利用最短树的特殊结构所给出的准则，进行局部寻优，在一个不大的图里，我们较易得到较优解。(a) 分片 准则1利用最短树的长度可大致的估算出路程长，在具体操作中，各片中的最短路程长度不宜相差太大。 准则 2 尽可能将最短树连成一个回路，这可保证局部上路程是

4、较短的。(b) 片内调整 细准1对于右图的最短树结构，最好的走法是 a1 a2 a3 a4 a5 a6假设 a3 a4有路相连若 a3 a4 进去重复走的话，它与上述的走法路程差w(a3, a2)+w(a2 ,a5)+w(a4, a5)w(a3, a4)。由两点间最小原则上式是大于0的优劣可见 细准2若有如图所示结构，一般思想是：将中间树枝上的点串到两旁树枝，以便连成回路。五、模型求解问题一 该问题完全可以用均衡模型表述 用算法模型 1 经过局部优化 手工多次比较 我们能够给出的最佳结果为第一组路径为0P282726N242322-1716115118K212025M-0 长 191.1 经

5、5 镇 6 村 第二组路径为 0256L19J11-G1314H12F10F9E8E76520 长 216.5 经 6 镇11 村第三组路径为 O23D4D3CB1A343533313230Q29R 长 192.3 经 6 镇11 村 总长 S=599.9 公里 由算法 2 给出的为 1 组0P29R3133A34353230Q282726N24332223N26P05 乡 13 村长 215.2 公里 2 组 0M2521K1716I15I18K212520L19J11G1314O5 乡 11 村长 256.2 公里 3 组 O2567E9-F12-H-12F10F9E-84076M5-23

6、L13108 乡 11 村长 256.3 公里 总长 727.7 公里问题二 利用最小时模型所给结论 应分组 ntt*+1=2429.83+1=4 当分 4 组时 1 算法模型 1 给出的解为 组号 长度 公里 经乡镇 村 耗时 小时 1 154.2 4 11 23.4 2 140.1 5 8 22.0 3 167.2 3 8 18.8 4 201.2 5 7 22.8 2 算法模型 2 给出的为 组号 时间 路径 1 23.0 2 01A3331R29Q303235 3413C32-0 9村5乡140.7公里 2 23.1 8 25M67048-E9F10120 9村4乡216.3公里 3

7、22.9 3 H1413G11J19L202521K0 7 村 5 乡 207.55 公里 4 21.2 7 18L15I1617-2218-24N26272854-0 10 村 3 乡 184.45 公里 注 以上每一路径是含 0 的回路 如果两点之间没有公共边 则走连接两点之间的最短路径因篇幅有限不能将途径的所有点都罗列 问题三 可以这样认为 往每个点都派一个巡视组去访问 并且都走最短路径 这时所花时间最少由于点的个数有限 时间是容易求的 从地图上看 H 是最短路径最长的点 且停留时间最长它所花的时间即为所求:E=77.1 2/35 +2=6.43(小时) 我们认为在这个时间限制下 最佳路线指派出人数最少路线 依靠最小时模型结论 可以给出估