灾情巡视路线的数学模型.doc

灾情巡视路线的数学模型
摘要
本文是解决灾情巡视路线最佳安排方案的问题。某县领导将带人下乡巡视灾情,打算从县城出发,视察所有乡、村后返回县城。为确定安排巡视路线,本文将此安排问题转化为旅行售货员问题,建立了四个最优化模型解决问题。
对于问题一,建立了双目标最优化模型。首先将问题一转化为三个售货员的最佳旅行售货员问题,得到以总路程最短和路程均衡度最小的目标函数,采用最短路径的算法,并用MATLAB软件编程计算,得到最优树图,然后按每块近似有相等总路程的标准将最优树分成三块,最后根据最小环路定理,、,,路程均衡度为,具体巡视路线安排见表1。
对于问题二,建立了单目标最优化模型。首先根据条件计算可确定至少要分4组巡视,于是可将问题转化为四个售货员的最佳旅行售货员问题,采用算法求出巡视路线的最小生成树。再根据求最优哈密顿圈的方法,运用LINGO软件编程计算,求出了各组的最佳巡视路线。各组巡视的路程分别为、184、、,、、、,%,具体巡视路线安排见表2。
对于问题三, 建立了以最少分组数为目标函数的单目标最优化模型。运用问题一中最短路径的Dijkstra算法,运用LINGO软件编程计算,得到从县城到各点的最短距离,。最后采用就近归组的搜索方法,逐步优化,最终得到最少需要分22组进行巡视,具体的巡视方案见表3。
对于问题四,建立了单目标优化模型,并且对变量进行讨论。在分析乡(镇)停留时间,村庄停留时间和汽车行驶速度的改变对最佳巡视路线的影响时,我们通过控制变量的变化,初步的得出了当与变化时和变化时对最佳巡视路线的影响。
关键词最优化模型旅行售货员问题最优哈密顿圈

今年夏天某县遭受水灾,为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡、村巡视。巡视路线指从县政府所在地出发,走遍各乡(镇)、村,又回到县政府所在地的路线。(路线相关信息见附表1)
本文需解决的问题:
问题一:若分三组巡视,试设计总路程最短且各组尽可能均衡的巡视路线。
问题二:假定巡视人员在各乡(镇)停留时间=2小时,在各村停留时间=1
小时,汽车行驶速度=35公里/小时。要在24小时内完成巡视,至少应分几组;给出这种分组下你认为最佳的巡视路线。
问题三:在上述关于, 和的假定下,如果巡视人员足够多,完成巡视的
最短时间是多少;给出在这种最短时间完成巡视的要求下,你认为最佳的巡视路线。
问题四:若巡视组数已定(如三组),要求尽快完成巡视,讨论,和改变
对最佳巡视路线的影响。


假设1:巡视人员足够多,汽车足够多;
假设2:每组视察路线的路况相同,并且各汽车的平均速度相等;
假设3:每个乡(镇)、村均只视察一次,第二次经过时不作停留;
假设4:各巡视小组只在各自计划的乡(镇)、村停留,非计划之内的乡(镇)、村可以经过,但是不停留。
假设5:在乡镇的停留时间与在村的停留时间成正比例关系。

赋权连通图
赋权连通图的第个子图
子图中的最佳回路
边的边权
点的点权
的各边权之和
的各点权之和
巡视中在每个乡镇停留时间
巡视中在每个村的停留时间
汽车行驶速度
各乡(镇)、村所在地
县政府所在地
对应示意图中的公路
乡(镇)、村的总个数
第组停留的乡(镇)数
第组停留的村数

本文是领导视察受灾县,并求最佳巡视路线的数学建模问题,题中已给出该县公路的网络图,要求在不同的题目要求下,得到灾情巡视的最佳分组方案和路线。
若将每个乡(镇)或村看作一个图的顶点,各乡镇、村之间的公路看作此图对应顶点间的边,各条公路的长度(或行驶时间)看作对应边上的权,所给公路网就转化为加权网络图,问题就转化图论中一类称之为旅行售货员的问题,即在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次再回到点O,使得总权(路程或时间)最小. 本题所求的分组巡视的最佳路线,也就是m条经过同一点并覆盖所有其他顶点又可使边上的权之和达到最小的闭链(闭迹),即最佳旅行售货员问题。
针对问题一, 要求分三组(路)巡视,得到总路程最短且各组尽可能均衡的巡视路线,可转化为三个售货员的最佳旅行售货员问题。先用MATLAB软件编程计算得到加权网络图的最小生成树,按每块近似有相等总路程的标准将最小生成树分成三块,每一块都转化为一个最佳旅行售货员问题。再确定总路程最短且满足各组尽可能均衡的路线的目标函数,最后对目标函数适当改进,得到最终的