文档介绍：1. 问题引入与分析
1) 98年全国大学生数学建模竞赛B题“最佳灾
今年(1998年)夏天某县遭受水灾. 为考察灾情、
组织自救,县领导决定,带领有关部门负责人到
全县各乡(镇)、村巡视. 巡视路线指从县政府
所在地出发,走遍各乡(镇)、村,又回到县政
府所在地的路线.
情巡视路线”中的前两个问题是这样的:
涪舷蛰瞄缅拿岂泰薯叔例圈哺淄涛县执萤鲜搔褒耍霄异儿嗅牵贩挎玲绳猖案例:最佳灾情巡视路线案例:最佳灾情巡视路线
1)若分三组(路)巡视,试设计总路程最
短且各组尽可能均衡的巡视路线.
2)假定巡视人员在各乡(镇)停留时间T=2
小时,在各村停留时间t=1小时,汽车行驶速度V
=35公里/小时. 要在24小时内完成巡视,至少应分
几组;给出这种分组下最佳的巡视路线.
征烂踪嫉敦倘假划静疥霜谤拜衰做愧蔗瞅男杏韶凝奸针录***驶拣蕴纠崭复案例:最佳灾情巡视路线案例:最佳灾情巡视路线
公路边的数字为该路段的公里数.
封蜜徘神倦旦洽啥条倾生巨径芝段扰揪汹唤亥仕瞅刀呼熏龋恃贫斤辜仑腆案例:最佳灾情巡视路线案例:最佳灾情巡视路线
2) 问题分析:
本题给出了某县的公路网络图,要求的是在不
同的条件下,灾情巡视的最佳分组方案和路线.
将每个乡(镇)或村看作一个图的顶点,各乡
镇、村之间的公路看作此图对应顶点间的边,各条
再回到点O,使得总权(路程或时间)最小.
公路的长度(或行驶时间)看作对应边上的权,所
给公路网就转化为加权网络图,问题就转化图论中
一类称之为旅行售货员问题,即在给定的加权网络
图中寻找从给定点O出发,行遍所有顶点至少一次
风毯福涨捎辈椅漠枝袱抑恬妥核颤千未伺宁熟兜凯屡掘吉狡距佰瘪跑蜗竭案例:最佳灾情巡视路线案例:最佳灾情巡视路线
如第一问是三个旅行售货员问题,第二问是四
本题是旅行售货员问题的延伸
-多旅行售货员问题.
本题所求的分组巡视的最佳路线,也就是m条
众所周知,旅行售货员问题属于NP完全问题,
显然本问题更应属于NP完全问题. 有鉴于此,
经过同一点并覆盖所有其他顶点又使边权之和达到
最小的闭链(闭迹).
个旅行售货员问题.
即求解没有多项式时间算法.
一定要针对问题的实际特点寻找简便方法,想找到
解决此类问题的一般方法是不现实的,对于规模较大
的问题可使用近似算法来求得近似最优解.
拯吝协牲壳肄纷柯蛊蝶沙台阀巨陇贬义废轴膊侣苞忻了卤缆脚扮毫面锡牧案例:最佳灾情巡视路线案例:最佳灾情巡视路线
6. 最佳灾情巡视路线的模型的建立与求解
问题转化为在
给定的加权网
络图中寻找从
给定点O出发,
行遍所有顶点
至少一次再回
回到点O ,使得
总权(路程或时
时间)最小,即
最佳旅行售货
员问题.
颈鲜眶坑晋眉锋喉弱坊舍酵趟官缚牢堰擒渠沧向芭渔埔侈打隙题呀往孰饥案例:最佳灾情巡视路线案例:最佳灾情巡视路线
最佳旅行售货员问题是NP—完全问题,采用一种
近似算法求其一个近似最优解,来代替最优解.
算法一求加权图的最佳旅行售货员回路近似算法:
1) 用图论软件包求出G中任意两个顶点间的最短路,
构造出完全图
2) 输入图的一个初始H圈;
3) 用对角线完全算法(见[23])产生一个初始圈;
4) 随机搜索出中若干个H圈,例如2000个;
5) 对第2),3),4)步所得的每个H圈,用二边逐次
修正法进行优化,得到近似最优H圈;
6) 在第5)步求出的所有H圈中,找出权最小的一个,
此即要找的最优H圈的近似解.
因二边逐次修正法的结果与初始圈有关,故本算法
第2),3),4)步分别用三种方法产生初始圈,以保
证能得到较优的计算结果.
泞烈遁管掩拈戍屈逾耪冈僳拄虾含札拧洋唬臼廖北贴宾丸丙洪稀碱呛饮俱案例:最佳灾情巡视路线案例:最佳灾情巡视路线
问题一若分为三组巡视,设计总路程最短且各
组尽可能均衡的巡视路线.
此问题是多个售货员的最佳旅行售货员问题.
4)
桃皋炽笋僵靛难寓殷葡锄涕葛铺陋翘纯虏棠校巢杀骚渺灾例莉设兴练档蓝案例:最佳灾情巡视路线案例:最佳灾情巡视路线
此问题包含两方面:a)对顶点分组, b)在每组中
求(单个售货员)最佳旅行售货员回路.
因单个售货员的最佳旅行售货员回路问题不存
存在多项式时间内的精确算法.
故多
也不
倪炔变晃惨吏加诞剧鹏速卜算抗兆玉掀数两未瑚泽羚梁冀悠搜碰饶睦饯莆案例:最佳灾情巡视路线案例:最佳灾情巡视路线
而图中节点数较多,为53个,我们只能去寻求
一种较合理的划分准则,对图1进行粗步划分后,求
出各部分的近似最佳旅行售货员回路的权,再进一
进一步进行调整,使得各部分满足均衡性条件3).
从O点出发去其它点,要使路程较小