灾情巡线论文.docVIP

题目：最佳灾情巡视路线 摘要 本文建立了关于某县灾情巡视路线的一系列问题的简洁的数学模型。应用最小生成树法结合哈密尔顿圈找出最优哈密回路圈，从而将问题转化问求哈密尔顿最优问题，这就相当于所谓旅行推销员问题：推销员从驻地出发经过所要去的城市至少一次返回原地，应如何安排使其总的旅行距离最短。今年水灾统计2010-08-05 04:39 受灾人口：1.4亿因灾死亡：1,072人因灾失踪：619人受灾省份：8个受灾农作物：972万公顷倒塌房屋：110万间直接经济损失：约2,096亿元某县的乡（镇）、村公路网示意图今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 ）所谓旅行推销员问题是推销员从驻地出发经过所要去的城市至少一次返回原地，应如何安排使其总的旅行距离最短。 类似的可以使费用最小或时间最短等。称符合要求的巡游路线为一个巡回。巡回的概念里不包含优化指标的比较，只是一个可行。从旅行推销员问题的概念来看它的本质是哈密尔顿圈的应用与延伸若把城市作为一个顶点，哈密尔顿圈只要求过每一个顶点一次且仅一次；而推销员回路是至少一次必要时允许重复通过。旅行推销员问题中各个顶点重复通过主要是考虑巡回线路的最佳化问题。定义： 1。 推销员回路： 在过各个顶点的巡回线路中，若每个顶点至少经过一次，则称为推销员回路 2 哈密尔顿回路 在过各个顶点的巡回线路中，若每个顶点只经过一次，则称为哈密尔顿回路。……Vp-1，Vx)即为开网络N1中的P*A=（S，V1，V2，……Vp-1，f）。 在N1中求解最小生成数。当最小生成数的各个节点度数不大于2时，则得到S到f的哈密尔顿路。若大于3，则最小生成树的哈密尔顿路（对应的）不止一条。因此确定N中的最优哈密尔顿路长的下界为L(N)。则在度数大于3的顶点中选择度数较小的分枝。 N1=N11∪N12∪N13……; N11=N1\eT1； N12=N1\eT2； . . . 其中N11，N12，N31，…；分枝以后的新网络；eT1 ，eT2 ，eT3，…为分枝借点关联的变。 继续在N11，N12，N31，…中应用最小生成树算法，寻求最优哈密尔顿路，确定下界时L（Nt）。设在分枝网络中解得的最优哈密尔顿路所对应的界为N1中最优解的上界，记为M1Nk，则M1Nk小于所有分枝的下界时，Nk1中所得的最优哈密尔顿路即为N1的最优解。 多路巡回路问题可大概表示如下。 在网络N中从V0出发m组巡回各点，求最短路。我们可将V0分解为V01，…，V0n的m个节点，其中每个节点与N中其他借点的连接关系相同，正如图2所示，就是本题中的V50，分解为V501，V502,V503.（因为有三组巡回）。 我们称这种变换为拓展立体网络变换，所得结果为拓展立体网络，在立体网络中应用求哈密尔顿回路的算法，可求得哈密尔顿圈，如图3所示。 V501，V502,V503被穿入哈密尔顿圈之中，则3组巡回路即为：V501→V502, V502→V503,V503→V501，是最优多组巡回路线，也即n个节点的图变为n+m-1个节点的圈来求解。 至此，问题的算法已经严密的建立起来，本题中将图N变换成N0后，在N0中，对应O点一个的是3个O1,O2,O3,连接关系不变，应用上面的算法就可以求得巡回路线。 问题2中表明N中的节点也将带权，在上面求哈密尔顿算法中，将一条的权表示为路上所有边和点权之和，就可以求一个等价的“哈密尔顿路”。 我们在各组所用的时间均衡的条件下，让组数从1到53变化（其实从1到10变化就可以了），可得24小时巡视的最小组数。问题1、问题2的理论模型算法见附录，克鲁斯科尔算法。最后我们要说明两点： 任意N化为N0后，N0是完全图，绝对有哈密尔顿路； 理论模型只有理论上的意义，其算法中有些环节（如分枝定界等）在节点数n叫大时，实现十分困难，复杂度剧增。所以我们仅有里下面的实用简化模型对所给问题进行求解。 应用简化模型求解 应用理论模型的思想，结合节点分类的方法，可以建立一个简化的使用模型来解决题目中的各种问题。下面我们以题目中的问题来建立、分析并求解模型。 问题一