数学建模路线优化问题

选路的优化模型选路的优化模型 摘要摘要 本题是一个有深刻背景的 NPC 问题 文章分析了分组回路的拓扑结构 并构造了多个 模型 从多个侧面对具体问题进行求解 最短树结构模型给出了局部寻优的准则算法 模型体现了由简到繁 确保较优的思想而三个层次分明的表述模型证明了这一类问 题共有的性质 在此基础上我们的结果也是比较令人满意的 如对第一题给出了总长 为 599 9 单项长为 216 的分组 第二题给出了至少分四组的证明 最后 我们还谈到 了模型的优缺点及推广思想 一 问题描述一 问题描述 水大无情 人命关天 为考察灾情 县领导决定派人及早将各乡 镇 村巡视 一遍 巡视路线为从县政府所在地出发 走遍各乡 镇 村又回到县政府所在地的路 线 1 若分三组巡视 试设计总路程最短且各组尽可能均衡的巡视路线 2 假定巡视人员在各乡 镇 停留时间为 T 2 小时 在各村停留时间为 t 1 小 时 汽车行驶速度为 V 35 公里 时 要在 24 小时内巡视完 至少分成几组 给出这种分组下你认为最佳的巡视路线 3 上述关于 T t 和 V 的假定下 如果巡视人员足够多 完成巡视的最短时间是 多少 给出在这种最短时间完成巡视的要求下 你认为最佳的巡视路线 4 巡视组数已定 如三组 要求尽快完成巡视 讨论 T t 和 V 改变时最佳路线 的影响 图见附录 二 问题假设二 问题假设 1 乡 镇 村只考察一次 多次经过时只计算一次停留时间 2 非本县村不限制通过 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 四 模型建立四 模型建立 1 在这一节里 我们将提出若干个模型及其特点分析 不涉及对题目的求解 最简树结构模型 在这个模型中我们依靠利用最短树的特殊结构所给出的准则 进行局部寻优 在 一个不大的图里 我们较易得到较优解 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 若有如图所示结构 一般思想是 将中间树枝上的点串到两旁树枝 以便 连成回路 五 模型求解五 模型求解 问题一 该问题完全可以用均衡模型表述 用算法模型 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 给出的为 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 0 5 乡 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 O 5 乡 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 0 8 乡 11 村长 256 3 公里 总长 727 7 公里 2 问题二 利用最小时模型所给结论 应分组 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 公 里 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 小时 我们认为在这个时间限制下 最佳路线指派出人数最少路线 依靠最小时模