案例：最佳灾情巡视路线.ppt

1. 问题引入与分析1) 98年全国大学生数学建模竞赛B题“最佳灾今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、村巡视. 巡视路线指从县政府所在地出发,走遍各乡(镇)、村,”中的前两个问题是这样的:1)若分三组(路)巡视,)假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/小时. 要在24小时内完成巡视,至少应分几组;) 问题分析:本题给出了某县的公路网络图,要求的是在不同的条件下,(镇)或村看作一个图的顶点,各乡镇、村之间的公路看作此图对应顶点间的边,各条再回到点O,使得总权(路程或时间)(或行驶时间)看作对应边上的权,所给公路网就转化为加权网络图,问题就转化图论中一类称之为旅行售货员问题,即在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次如第一问是三个旅行售货员问题,第二问是四本题是旅行售货员问题的延伸-,也就是m条 众所周知,旅行售货员问题属于NP完全问题, 显然本问题更应属于NP完全问题. 有鉴于此,经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链(闭迹).,想找到解决此类问题的一般方法是不现实的,. 最佳灾情巡视路线的模型的建立与求解问题转化为在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次再回回到点O ,使得总权(路程或时时间)最小,—完全问题,采用一种近似算法求其一个近似最优解,: 1) 用图论软件包求出G中任意两个顶点间的最短路, 构造出完全图),(,),(),,(yxEyxEVG???????);,(minyxdG?2) 输入图的一个初始H圈;G?3) 用对角线完全算法(见[23])产生一个初始圈;4) 随机搜索出中若干个H圈,例如2000个;G?5) 对第2),3),4)步所得的每个H圈,用二边逐次修正法进行优化,得到近似最优H圈;6) 在第5)步求出的所有H圈中,找出权最小的一个, ,故本算法第2),3),4)步分别用三种方法产生初始圈,,)min)(1???niiC?此问题包含两方面:a)对顶点分组, b)在每组中求(单个售货员),为53个,我们只能去寻求一种较合理的划分准则,对图1进行粗步划分后,求出各部分的近似最佳旅行售货员回路的权,再进一进一步进行调整,使得各部分满足均衡性条件3).从O点出发去其它点,要使路程较小应尽量走O点到该点的最短路. .