第卷第期年月数学的实践与认识「,‘【灾情巡视的最佳路线丁颂康上海海运学院,上海摘要今年夏季,我国长江、松花江流域的广大地区遭受了特大水灾作为冬州年全国大学生数学建模竞赛题的“灾愉丛视路线”问题就是在这样的背景下构思而成的本文中,我们将结合答卷评阅情况,简单介绍一些有关该题解答的要点一、关于问题的数学模型本题给出了某县的道路交通网络图,要求的是在不同条件下,灾情巡视的最佳分组方案和路线这是一类图上的点的行遍性问题,也就是要用若干条闭链复盖图上所有的顶点,并使某些指标达到最优点的行遍性问题在图论和组合最优化中分别称为哈密尔顿间题和旅行商问题所谓哈密尔顿问题,就是研究图中是否存在经过所有顶点恰好一次的圈或路,这种圈或路如果存在分别称为哈密尔顿圈和哈密尔顿路,简称为一圈和一路而旅行商问题通常是指在赋权图上经过所有顶点至少一次,且使总长度即边权之和达到最小的闭链而本题所求的分组巡视的最佳路线,则与多旅行商问题厂,日类似,也就是,,,条经过同一点并复盖所有其它顶点又使边权之和达到最小的闭链求解非完全图的多旅行商问题,通常所用的方法可分为两步首先是利用任意两点问的最短路长度作为该两点间边的权构造一个完全图这一点对于原图中没有边相连的点对尤为重要,容易证明,在如此构造出来的完全图中,各边的权将自然满足三角不等式,即任意三点间,两边权之和不小于第三边的权并且该完全图中的最优哈密尔顿圈与原图上的最优旅行商路线等价第二步,以一点为起终点本题中的县城的多旅行商问题,可以采用将该点视作若干点,,,,。,,⋯,,,、左为旅行商人数,并令,,‘,。,,,,,,,,。对所有的点,‘笋。,及,之,‘,双,二笋,该,,,一,们的方法,再将前述的完全图拓展成增广完全图然后,在该增广完全图上求最优哈密尔顿圈通常情况下,这个最优哈密尔顿圈将经过。,⋯,汽各一次,而这些点在圈上又不相邻因此,它们将把这个圈分解成恰好段这左段形成以粉作为起终点的闭链,分别对应左个旅行商的旅行路线并月这些旅行路线对于总长度最短的目标来说一定是最优的在拓展完全图上求解最优哈密尔顿圈‘,可以表达成下述线性规划更确切地讲是一规划的形式,,‘,艺艺,更,,“,,之了。艺,礼,‘,城艺,‘,,、为、艺二、七斌官、爪且‘万并。任,少任写“‘、了或©1994-2008ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net丁颂康灾情巡视的最佳路线其中、“就是点和间边的权是图的点集而条件兄八全是为了保证取之...
