灾区巡视最佳路线 选择问题 数学建模.docVIP

灾情巡视 摘要 本文解决的是对全县各乡镇和村庄进行灾情巡视线路的设计问题，该问题属于点的遍历性的TSP问题。因此我们结合图论的相关知识并考虑到分组的均衡性，建立起了约束最优化线路模型来解决该问题。 针对问题一，我们先建立起目标函数(见5.11中式)，随后根据各点的集中区域进行划分，引入均衡度?进行分组方案的比较，最终采用方案二(见5.2中方案二)。再利用破圈法和最小生成树法得到了最短回路。最后matlab编程求解（见附录一）得出各组的巡视路程分别为公里,公里,公里,总路程为公里?=0.0405。具体路线安排见表二。 针对问题二，分析得到要在24小时完成巡视的任务最少要四组巡视人员，将问题一中各条线路的权重由路程改为了时间，并在结点处增加了结点权重。Matlab求解（见附录二）得巡视的时间分别为21.73小时22.51小时，23.60小时，21.18小时。所以至少分四组，具体路线安排见表三。 针对问题三，通过图论软件得出巡视到距离O最远的点H要的时间为6.43小时，要在这个时间上限内完成巡视，分析得到最优分配为24组。最后借助图论软件求出最终方案(见表四)。 针对问题四，在不影响分组的均衡条件下, T,t,V分别为变量时的各自允许变化范围得出了这三个变量的关系式进行了讨论Hamilton 圈 破圈法 TSP问题 最小生成树 1问题重述 1.1问题背景 今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 说明 G 表示加权图 Gi 表示子图 V 表示顶点，每一个乡(镇)或村看成一个点 E 表示边，乡(镇)或村之间的路线 w(x，y) 表示权重，乡(镇)或村之间的距离 S 表示回路路程总和 ? 表示路程均衡度 Li 表示每一条子回路 T 表示在每个乡(镇)停留的时间 I 表示在每个村停留的时间 Ti 表示第i组的巡视时间 V 表示汽车行驶速度 Z 表示划分的区域数 N 表示乡(镇)的数目 n 表示村的数目 Ni 表示第i组巡视乡(镇)的数目 ni 表示第i组巡视村的数目 m 表示所分的组数 表示时间均衡度 3问题分析 本文研究的是最佳巡视路线设计问题，要求从O点出发巡视完所有乡(镇)村后，在回到O点，此问题可以转化为旅行商问题，再设计相应的算法求解 针对问题一：问题一要求设计3组巡视，巡视总路程最短且尽可能均衡，首先我们通过主观筛选法将原图划分为3个子图，每个子图顶点数大约为17个，相邻的点划在一个子图中，且尽量使每个子图构成一个回路，这样将原问题转化为单旅行商问题求解 针对问题二：问题二在问题一的基础上加了时间的限制，在每一个顶点都有停留时间，且在24小时巡视完。通过计算可得至少分为4组，才可能实现。和问题一类似我们将原图划分为4个子图，分别计算每组的巡视时间，设计每组的巡视路线。 针对问题三：问题三T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间巡视组数已定，要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。G是指一个二元组(V(G),E(G))，其中：其中元素称为图G的顶点。 2) E(G)是顶点集V(G)中的无序或有序的元素偶对 组成的集合，即称为边集,其中元素称为边. 定义 图G的阶是指图的顶点数|V(G)|, 用来表示； 图的边的数目|E(G)|用来表示. 用表示图，简记也用来表示边 设G=V，E，W是加权的连通图，对任意边e(，其权C(e)≥0。令T=VT,ET,WT是G的一棵加权生成树，其所有枝上的权的总和称为树T的权，记为C(T)。一般说来，对于G的不同生成树T，C(T)也是不同的。可以知道，其中必有一个最小者，而这正是人们最为感兴趣的。因此，给定连通加权图G=V，E，W，T0=V，ET0，WT0是G的加权生成树，C(T0)为T0的权。若对G的任意加权生成树T均有C(T0)≤C(T)，则称T0是G的最小生成树。 下面给出一种求最小生成树的方法(破圈法)： 设G是有n个结点的连通图，下面算法产生的是最小生成