文档介绍：最佳灾情巡视路线摘要本文首先引入了图论中关于最佳推销员路径问题与最佳H圈问题的有关结论,通过floyd最短路算法建立基于原图的完备图,将最佳推销员路径问题转化为最佳H圈问题。并采用两边逐次修正法建立了所要巡视的点集与其最佳巡视路径的函数关系。对于问题一,我们建立了一个严格的优化模型,其中变量是对所有要巡视点集的一个分组,但是求解这个问题是十分困难的,我们根据原图中任意两点的最短路径给出了一个与分组方案,在根据均衡性要求,又给出了调整的算法。最后三组的路程分别为(千米):,,,可见均衡性很好,。问题二中加入了停留时间,我们经过判断,认为至少分4组,并发现4组也是可行的,所用的方法与问题一类似,也是预分组加调整。我们最后的结果四组分别是(小时):,,,。它们满足24小时巡查完毕的要求,且比较均衡。问题三要求求出人员足够的条件下,完成巡视的最短时间,显然分52组,每组沿着以县政府到各村或乡镇的最短路径分别访问各个村或乡镇再按原路返回是最快的。。但是,在保证这个最短用时下,分52组是对人员的浪费,我们首先消除了本可以顺路巡视的情况,对得到的结果不均衡的地方又进行了第二轮调整,最终分为24组,,完成了任务,并给出了具体路径。关键字最佳推销员路径最佳H圈均衡性正文一问题的重述(略),不会出现抛锚等现象;,在每个乡镇、村的停留时间一定,不会出现特殊情况而延误时间;;,各小组只能走自己区内的路,不能走其他小组的路,除公共路外;5人员足够多则可以分任意多组。三符号说明(用于表示地点时) 表示县政府,表示村,表示乡镇,其中36表示乡镇A,37表示乡镇B,依次类推,O除外。上述i从1到52构成的地点集合对V的一个分组从0(县政府)出发,经过中所有点最后回到0点的最佳推销员回路的权值(即总路程)巡视人员在各乡镇停留的时间巡视人员在各村停留的时间巡视人员行驶速度从0(县政府)出发,经过中所有点最后回到0点的最佳推销员回路中用于停留在各村、乡镇的时间总和。四模型的建立与分析准备工作1首先引入图论中的几个重要结论:经过图G的每个顶点正好一次的圈(如果存在),称为G的哈密尔顿圈或H圈。其中权最小的哈密尔顿圈称为最佳H圈。完备图一定存在最佳H圈。,最佳哈密尔顿圈不一定是最佳推销员回路,同样最佳推销员回路也不一定是最佳哈密尔顿圈。但是最佳推销员回路问题可转化为最佳H圈问题。方法是由给定的图G=(V,E)构造一个以V为顶点集的完备图G’=(V,E’),E’的每条边(x,y)的权等于顶点x与y在图中最短路的权。这时,我们有结论:加权图G的最佳推销员回路的权与G’的最佳H圈的权相同。2根据以上结论,将所给图转化为满足任意两点之间边的权值为原图中任意两点之间的最短路长度的完备图。这里我们用到的一个重要算法是求一个图中任意两点之间最短路的floyd算法(见附录)。最后我们转换成的完备图邻接矩阵如下(只摘录前十行和前十列):