灾情巡视的最佳路线.pdf

第 卷 第 期 数 学 的 实 践 与 认 识
年 月 「, ‘ 【
灾情巡视的最佳路线
丁颂康
上海海运学院 , 上海
摘 要 今年夏季 , 我国长江 、 松花江流域的广大地 区遭受了特大水灾 作为 冬州 年全国
大学生数学建模竞赛 题的 “ 灾愉丛视路线 ” 问题就是在这样的背景下构思而成的 本文
中 , 我们将结合答卷评阅情况 , 简单介绍一些有关该题解答的要点
一 、 关于问题 的数 学模型
本题给出了某县 的道路交通 网络图 , 要求的是在不同条件下 , 灾情巡视的最佳分组方案和路
线 这 是一类 图上 的点的行遍性 问题 , 也就是要用若干条 闭链复盖 图上所有 的顶点 , 并使某些指
标达到最优
点 的行遍 性 问题在 图论和 组合最优化 中分别 称为哈密尔顿 间题 和 旅行商问题 所谓 哈 密尔
顿 问题 , 就 是研究图 中是否存在经过所有顶点恰好一 次的圈或路 , 这种圈或路 如果存在 分别
称为哈密尔顿圈和 哈密尔顿路 , 简称为 一 圈和 一 路 而旅行商问题通常是指在赋权 图上经
过所有顶点 至 少 一 次 , 且使 总长度 即边权 之和 达到最 小的闭链 而本题所求的分组巡视 的最
厂
佳路 线 , 则与多旅行商问题 , 日 类 似 , 也就是 , , , 条经过 同一 点并复 盖所有其它顶点 又 使边
权之和