建模案例最佳灾情巡视路线.doc

文档介绍：建模案例:、、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、,走遍各乡(镇)、村,(路)巡视,(镇)停留时间T=2h,在各村停留时间t=1h,汽车行驶速度V=35km/,至少应分几组;、,不会出现抛锚等现象;,在每个乡镇、村的停留时间一定,不会出现特殊情况而延误时间;;,各小组只能走自己区内的路,不能走其它小组的路(除公共路外).三、模型的建立与求解将公路网图中,每个乡(镇)或村看作图中的一个节点,各乡(镇)、村之间的公路看作图中对应节点间的边,各条公路的长度(或行驶时间)看作对应边上的权,所给公路网就转化为加权网络图,问题就转化为在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次再回到O点,使得总权(路程或时间)最小,—完全问题,我们采用一种近似算法求出该问题的一个近似最优解,来代替最优解,算法如下:算法一求加权图G(V,E)的最佳推销员回路的近似算法:用图论软件包求出G中任意两个顶点间的最短路,构造出完备图,,;输入图的一个初始H圈;用对角线完全算法产生一个初始H圈;随机搜索出中若干个H圈,例如个;对第2、3、4步所得的每个H圈,用二边逐次修正法进行优化,得到近似最佳H圈;在第5步求出的所有H圈中,找出权最小的一个,,故本算法第2、3、4步分别用三种方法产生初始圈,,,将G分成n个生成子图,使得(1)顶点,i=1,2,3,…,n;(2);(3),其中为的导出子图中的最佳推销员回路,为的权,i,j=1,2,3,…,n;(4),越小,,与满足条件(3)(4):第一,对顶点分组;第二,在每组中求最佳推销员回路,,,为53个,我们只能去寻求一种较合理的划分准则,对图1进行粗步划分后,求出各部分近似最佳推销员回路的权,再进一步调整,使得各部分满足均衡性条件(3).图2O点到任意点的最短路图(单位:km)从O点出发去其它点,,这些最短路构成一棵以O为树根的树,将从O点出发的树枝称为干枝,见图2,从图中能够看出,从O点出发到其它点共有6条干枝,她们的名称分别为①,②,