1998年大学生数学建模优秀论文选路的优化模型.pdf

本文作者 侯哲 韦日华 张扬明 本文获成功参赛奖本文作者 侯哲 韦日华 张扬明 本文获成功参赛奖 选路的优化模型选路的优化模型 摘要摘要本题是一个有深刻背景的 NPC 问题文章分析了分组回路的拓扑结构并构造了多个 模型从多个侧面对具体问题进行求解最短树结构模型给出了局部寻优的准则算法模型体 现了由简到繁确保较优的思想而三个层次分明的表述模型证明了这一类问题共有的性质 在此基础上我们的结果也是比较令人满意的如对第一题给出了总长为 599 9单项长为 216 的分组第二题给出了至少分四组的证明最后我们还谈到了模型的优缺点及推广思想 一一 问题的提出 问题的提出 水大无情人命关天为考察灾情县领导决定派人及早将各乡镇村巡视一遍巡 视路线为从县政府所在地出发走遍各乡镇村又回到县政府所在地的路线 1若分三组巡视试设计总路程最短且各组尽可能均衡的巡视路线 2假定巡视人员在各乡镇停留时间为 T 2 小时在各村停留时间为 t 1 小时汽车行驶 速度为 V 35 公里 时要在 24 小时内巡视完至少分成几组给出这种分组下你认为最佳的 巡视路线 3 上述关于 Tt 和 V 的假定下如果巡视人员足够多完成巡视的最短时间是多少给出在 这种最短时间完成巡视的要求下你认为最佳的巡视路线 4 巡视组数已定如三组要求尽快完成巡视讨论 Tt 和 V 改变时最佳路线的影响图 见附录 二二 问题的假设 问题的假设 a 乡镇村只考察一次多次经过时只计算一次停留时间 b 非本县村不限制通过 c 汽车的行驶速度始终一致 三三 名词解释及符号约定 名词解释及符号约定 名词解释 a 两点间最小原则在数学上两点间直线长最短在本图中我们根据实际也认为任 两点间连线长不一定是直线总比过第三点的要短 b 最短路径某一节点到中心长度最小的路径 c 最短路径生成树简称最短树由最短路径所构成的树状结构见附录 1 约定符号 v1 v2 v35 依次表示村庄 12 35 v36 v37 v52 依次表示乡镇AB NP R vi vj vi vj 间边权数值上等于村镇ij 之间的道路长 Vi 表示巡视 Vi 需停留时间 G V E 1 1 赋权值简记为 G其中 V 为节点集E 为边集 Ti 第 i 人走的回路Ti vvi i v2 i vn i Ti 00 表示第 i 人在 0 点没移动 Vi Ti 的点集 Si Ti 的长度 Si W 0 vi i w v1 i v2 i w vn i 0 Hi v 在 V 上定义的特殊函数 仅当 V 被第 i 人走过且停留时 Hi v 1 否则为 0 四四 问题的分析 问题的分析 a 本题实质上是以旅行商问题为背景的 而旅行商问题属于图论中的 NPC 问题 至今尚 未建立起有效算法至于本题我们所要作的是根据具体的数据和图形结构构造 合适的模型求解 b 联系实际本题着重点在于如何使巡视时间最小其可能出现的拓扑结构如下 要求各路线尽可能均衡 结构 3 和 4 明显不合理 结构 2 没有把相邻的点尽可能连在一起 总路程将偏大相比之下结构 1 是较合理的 i 建模前的准备 在这一项里我们要对地图分析简化 1 用两点间最小原则检查地图发现处处符合 2 用地图做如下六处修改修改后的地图见附录 2 五五 模型的提出与分析 模型的提出与分析 在这一节里我们将提出若干个模型及其特点分析不涉及对题目的求解 最简树结构模型最简树结构模型 在这个模型中我们依靠利用最短树的特殊结构所给出的准则进行局部寻优在一个不大 的图里我们较易得到较优解 a 分片 准则 1利用最短树的长度可大致的估算出路程长在具体操作中各片中的最 短路程长度不宜相差太大 准则 2尽可能将最短树连成一个回路这可保证局部上路程是较短的 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若有如图所示结构一般思想是将中间树枝上的点串到两旁树枝以便连成回 路 3 建议走法为具体操作规则数据为 23 表述模型表述模型 1路程最小模型路程最小模型 要求在遍历所有村镇的前提下只考虑最小路程 数学表达式为min s n i si 1 s t V1U U V 32VV U Vn 结论结论在该模型下对任一图 Gn 取任意自然数时最小总路程都相等 证明证明记 i 人遍历时的最小总路程为 Si 1 设 n 人分别沿过 O 点的回路 T1 T2 T3 Tn 走时能够遍历所有的点并且这时 总路程最小为 S Sn 而只用一个人依次沿 T1 T2 Tn 走时 也能够遍历所有的点 这时总路程为S Sn S1 2 设一人遍历S S1 时回路为 T 此时若出动 n 人能沿以下回路遍历所有的点 T1 T T2 T3 Tn 00 所走路程 S S1 Sn S1 Sn 由此可知最小路程与 n 无关记为 S 算法 1 给出了 S 的较令人满意的近似值 500 3公 里 2均衡模型均衡模型 要求遍历所有的点总路程最小且尽可能均衡实际就是不计点权的时间最小问题 数学表达 min s max si i 1 2 n s t V1U U V 32VV U Vn 结论结论对该模型的解 si i 1 2 n n 1 必须有 S n i Si 1 证明证明在问题分析中已经说明 n 人遍历的回路应是并列型结构 取两人遍历的简单情况 如图一人遍历时走两环外沿对于情形 1走 AB 连线由两点间最小原则SS1 S2 情形 2则不走 OA 边同样有 S S1 S2 多人情形也类似有 1 SSSi n i 4 一般的 n 越大 Si 间重复的路段就越可能比较多 n i Si 1 与 S 一步拉大 3最短时模型最短时模型 该模型下考虑了节点的停留时间目标是时间花费最少 min t Max ti i 1 2 n s t V1 V UU 32VV U Vn 其中 ti i h 1 iiv n Vk i k k v si 为第 i 人的花费时间 结论结论设 t 是 1 人遍历所花的最少时间那么对于任意的 n n 2 3 有 1 tt n i i 证明证明t 17T 35t v s 根据结论 2 n i ti 1 11 ivhiivk n i ni k k v si n i 1 17T 35t v si n 1i 17T 35t v s t 即证 利用这一问题的结论我们 可以对限制时间下的分组进行估计在本题条件下 t 17 2 35 35 3 500 8329小时 t Max ti i 1 2 n n ti n t n t t 又 n 是正整数所以 n t t 1 是高斯取整符号 六六 具体问题的求解 具体问题的求解 5 问题一问题一 该问题完全可以用均衡模型表述 1用算法模型 1经过局部优化手工多次比较我们能够给出的最佳结果为 第一组路径为 0 P 28 27 26 N 24 23 22 17 16 1 15 1 18 K 21 20 25 M 0 长 191 1经 5 镇6 村 第二组路径为 0 2 5 6 L 19 J 11 G 13 14 H 12 F 10 F 9 E 8 E 7 6 5 2 0 长 216 5经 6 镇11 村 第三组路径为 O 2 3 D 4 D 3 C B 1 A 34 35 33 31 32 30 Q 29 R 长 192 3经 6 镇11 村总长 S 599 9公里 2由算法 2 给出的为 1 组 0 P 29 R 31 33 A 34 35 32 30 Q 28 27 26 N 24 33 22 23 N 2 6 P 05 乡 13 村长 215 2 公里 2 组 0 M 25 21 K 17 16 I 15 I 18 K 21 25 20 L 19 J 11 G 13 14 O5 乡 11 村长 256 2 公里 3 组 O 2 5 6 7 E 9 F 12 H 12 F 10 F 9 E 8 4 0 7 6 M 5 2 3 L 13 1 08 乡 11 村长 256 3 公里 总长 727 7 公里 问题二问题二 利用最小时模型所给结论应分组 n t t 1 24 29 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 0 1 A 33 31 R 29 Q 30 32 35 34 13 C 3 2 0 9村5乡140 7公里 2 23 1 8 2 5 M 6 7 0 4 8 E 9 F 10 1 2 0 9村4乡216 3公里 6 3 22 9 3 H 14 13 G 11 J 19 L 20 25 21 K 0 7 村 5 乡 207 55 公 里 4 21 2 7 18 L 15 I 16 17 22 18 24 N 26 27 28 54 0 10 村 3 乡 184 45 公里 注以上每一路径是含 0 的回路如果两点之间没有公共边则走连接两点之间的最短路径 因篇幅有限不能将途径的所有点都罗列 问题三问题三 可以这样认为 往每个点都派一个巡视组去访问 并且都走最短路径 这时所花时间最少 由于点的个数有限时间是容易求的从地图上看H 是最短路径最长的点且停留时间最长 它所花的时间即为所求 E 77 1 2 35 2 6 43 小时 我们认为在这个时间限制下最佳路线指派出人数最少路线依靠最小时模型结论可以 给出估计n t t 1 83 29 6 43 1 13 但上限为 17 35 52 不能确定 n 的取值现我们 用计算机结合算法模型 2 进行搜索得到 n 的最优值为 35 问题四问题四 n 人遍历下如最小模型所费时 t max ti i 1 2 n 其中 ti i h 1 iiv n Vk i k k v si mT nt v si m n 分别为巡视的乡镇村个数 一般情况下V T t 越大节点停留时间的决定意义就越大当 V 时t将完全由节 点停留时间决定这些情形下要求最佳路线能将节点分布均匀 V T t 越小路程远近的决定意义就越大当 V 时0 将完全由路程这些情形下 要求各路程长尽可能均衡 特别的本题中分三组的情形由局部优化给出的解各路线长不超过 20 公里而接点 的分布竟均匀到像作除法一样17 5 6 635 13 11 11可以断定在 V T t 实际可能出现 的抖动范围内这组解是稳定的 七七 模型的检验与评价 模型的检验与评价 文中两个算法模型都是较优解无法得到和确定最优解下面给出了一组对比数据 算法模型 最长路线 总线路 花费时间 耗时下限 1 2165 7276 3146 2 2562 5999 3432 相差 156 212 382 t 3 分三组 算法模型 最长路线 总线路 花费时间 耗时下限 7 1 2014 74925 2347 2 2165 6629 2318 相差 69 017 接近 0 t 4 20 82 分四组 从以上这组数据我们发现分四组与分三组相比答案更相近花费时间与理想情形更接 近一般来说越大的时候这两种方法得到的答案就可能越一致可以断定较优解很可能 越 接近最优值但两种算法模型相比1 局部寻优适用于小范围2 用计算机对大规模的求解更 有利另外2 的复杂度大也是它的缺点 八八 推广思想 推广思想 对于图论这种离散类型问题虽然肯定存在最优解但实际上情况复杂我们仍建议用多 种方法如模拟退大神经网络等