文档介绍：建模案例:最佳灾情巡视路线

这里介绍1998年全国大学生数学模型竞赛B题中的两个问题.
一、问题
、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、,走遍各乡(镇)、村,又回到县政府所在地的路线.
若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的路线.
假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/,至少应分几组;给出这种分组下最佳的巡视路线.
乡镇、村的公路网示意图见图11-9.
图11-9
假设
,不会出现抛锚等现象;
,在每个乡镇、村的停留时间一定,不会出现特殊情况而延误时间;
;
,各小组只能走自己区内的路,不能走其他小组的路,除公共路外.
三、模型的建立与求解
将公路网图中,每个乡(镇)或村看作图中的一个节点,各乡(镇)、村之间的公路看作图中对应节点间的边,各条公路的长度(或行驶时间)看作对应边上的权,所给公路网就转化为加权网络图,问题就转化为在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次再回到O点,使得总权(路程或时间)最小,此即最佳推销员回路问题.
在加权图G中求最佳推销员回路问题是NP—完全问题,我们采用一种近似算法求出该问题的一个近似最优解,来代替最优解,算法如下:
算法一求加权图G(V,E)的最佳推销员回路的近似算法:
用图论软件包求出G中任意两个顶点间的最短路,构造出完备图,, ;
输入图的一个初始H圈;
用对角线完全算法(见[23])产生一个初始H圈;
随机搜索出中若干个H圈,例如2000个;
对第2、3、4步所得的每个H圈,用二边逐次修正法进行优化,得到近似最佳H圈;
在第5步求出的所有H圈中,找出权最小的一个,此即要找的最佳H圈的近似解.
由于二边逐次修正法的结果与初始圈有关,故本算法第2、3、4步分别用三种方法产生初始圈,以保证能得到较优的计算结果.
问题一若分为三组巡视,设计总路程最短且各组尽可能均衡的巡视路线.
,将G分成n个生成子图,使得
(1)顶点 i=1,2,3……n
(2)
(3),其中为的导出子图中的最佳推销员回路,为的权,i,j=1,2,3……n
(4)
.
显然,越小,,与满足条件(3)(4)表示总巡视路线最短.
此问题包含两方面:第一、对顶点分组;第二、在每组中求最佳推销员回路,即为单个推销员的最佳推销员问题.
由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法,,为53个,我们只能去寻求一种较合理的划分准则,对图11-9进行粗步划分后,求出各部分的近似最佳推销员回路的权,再进一步进行调整,使得各部分满足均衡性条件(3).
图11-10 O点到任意点的最短路图(单位:公里)
从O点出发去其它点,要使路程较小应尽量走O