[数学]98数模—抗洪方法总结.doc

1提出问题 下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 问题三：在上述关于T , t和v的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和v改变对最佳巡视路线的影响。 2问题假设与符号说明2.1问题假设假设一：假设在巡视过程中不考虑天气、汽车故障等因素的影响假设二：假设路线上的公路路况良好，没有被洪水冲断，可以供巡视工作使用。假设三：假设在巡视工程中，经过邻县村时，不做任何时间的耽搁。假设四：假设巡视人员上下车的时间及汽车加油时间忽略不记。假设五：假设汽车在行驶途中车速不变且满足速度要求。假设六：假设可使用车辆数量不受限制。假设七：假设巡视人员的巡视时间可以大于当地所需巡视时间。假设九：假设巡视人员巡视时可以不需要车辆陪同。2.2符号说明赋权连通图；赋权连通图的第个子图子图中的最佳回路；最佳回路的各边权值之和第个乡、村到第个乡、村的距离某组从城市到城市时为1，无巡视组视为0表示各乡（镇）停留时间表示各村停留时间均衡度第i组的最佳推销员回路路线总长度；第i组所要停留的乡（镇）数目；第i组所要停留的村的数目三、问题分析本文研究的是考察灾情最佳巡视线路设计的问题，准确合理的路线设计对灾情巡视救治起着重要作用。方案一：对于问题一，题目要求在分三组巡视的情况下，使总路程最短且各小组所走路程均衡。先考虑分区，我们将得出的最小生成树图形和最短路树图形，进行比较并找出其公共部分。分组要求尽量不破坏最短生成树和最小生成树，所以我们以公共部分为界限，将此网络图分为三组。为使每小组所走路程均衡，我们引入了均衡度。它表示最大路程和最小路程的差值与最大路程的比值。越小，表示均衡度越好。以总路程最短和均衡度最小作为目标函数建立多目标规划模型，利用哈密顿原理得出各组的巡回路线，并对其分析修正求得各组最优巡回路线。对于问题二，要求在24小时内完成所有巡视。 通过第一问的结果，求得在分三组的情况下所用的平均时间大于24小时，所以我们先考虑分四组。我们的分组原则为：1、每子区域所分得的点近似相等；2、尽量使每一个子区域连通；3、使每一个子区域中与点O的最短路上的点在该区域内。根据以上分组原则将整个图大致划分为四个子图，同样利用哈密顿算法求得在相对均衡的情况每个小组的最短路径和所需时间。如果部分时间大于24小时，则调整分组方式；若所有时间均大于24小时再考虑多加一组。直到找到相对均衡条件下的最佳路线。对于问题三，考虑在人员足够多的情况下，求出最短的巡视时间。假设一个小组只巡视一个点的情况下，则去巡视离点最远的点所花时间最长。我们以巡视小组中所耗时间最长的小组所用时间作为这次整个巡视的最短时间。要使这次巡视时间最短，则要求去巡视离点最远的点所花时间最小，由图一可知，离O点最远的点为H，所以就以巡视所花时间作为。当此小组只巡视H时，最小。在不超过的情况下，根据其他小组的剩余时间确定沿途是否巡视其他点。其中巡视原则为：当一组人员巡视完规定点后时，在剩余时间允许的情况下，优先考虑原巡视点附近而距离较远的点，最大限度使用剩余时间，主要考虑原则。按照此原则，逐个巡视，直至巡视完所有点。对于问题四，若巡视组数已定，则每个小组的最短路径就已确定，、改变只影响的是整个的巡视时间。要求尽快完成巡视，即巡视时间要尽可能小。巡视时间包括到巡视点的行驶时间和在巡视点的停留时间。行驶时间主要取决于速度，而停留时间由、决定。所以此问题讨论的是当、改变时对巡视时间的影响，即对、的灵敏度分析。方案二：在数据分析中，我们采用避圈法得到了最小生成树，见附录二。针对问题一：题目要求分三组（路）巡视，并且要设计出总路程最短且各组尽可能均衡的巡视路线。为此，根据数据分析中得到的最小生成树，我们可以按照各个顶点的聚集方式和方位分为三组，然后运用最优回路算法建立模型一，通过Lingo求解分别得到三组巡视路线和对应的巡视路程，接着算出均衡度，并对巡视路线的结果进行逐步改进，使得均衡程度达到较好的水平。针对问题二：考虑停留时间T、t、速度v、分组数m等因素，通过分析我们得知随着其中每个量的改变，都将对回路的设计结果产生很大影响。所以，我们可以采用就近原则和均衡原则对巡视路线进行重新分组，然后使用最佳回路算法建立模型二来得出最佳巡视路线和对应路线巡视完需要的时间，最后根据得出的结果算出对应的均衡度。 针对问题三：需要我们在最短时间完成巡视的要求下，得到最佳的巡视路线。因为巡视人员足够多, 即巡视组数足够多, 要使巡视时间最短, 可以假设每个乡(镇) , 村都派一组, 因此要派52 个组。根据任意两点间的最短路径的求解方法(算法), 得到52 个乡(镇)、村分别对于县城的最短距离和相应的以乡(镇) , 村为目的地的巡视小组完成巡视的最短时间，则得到其中较大的那个即为所求的最短时间。为了简化模型，可任取离政府较远的乡镇、村为特殊点，进行比较计算得出最短时间。针对问题四：要求在巡视组数已定和尽快完成巡视的条件下，讨论，和改变对最佳巡视路线的影响。文中以分4组为例进行讨论。在讨论时，可以采用控制变量法分别对进行理论分析和定量分析，并就各因素可能产生的影响提出改进的建议。方案三：此问题可以转化为旅行商问题，再设计相应的算法求解针对问题一：问题一要求设计3组巡视，巡视总路程最短且尽可能均衡，首先我们通过主观筛选法将原图划分为3个子图，每个子图顶点数大约为17个，相邻的点划在一个子图中，且尽量使每个子图构成一个回路，这样将原问题转化为单旅行商问题求解针对问题二：问题二在问题一的基础上加了时间的限制，在每一个顶点都有停留时间，且在24小时巡视完。通过计算可得至少分为4组，才可能实现。和问题一类似我们将原图划分为4个子图，分别计算每组的巡视时间，设计每组的巡视路线。针对问题三：问题三T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间，并设计最佳路线。首先，我们分析可知巡视H使用的时间是最长的。那么，设计分组时，其它组巡视的时间不能超过这一最长时间。在计算过程中我们先从距O点远的点开始考虑，因为若巡视时间与最小时间相差较远可以考虑顺便访问途径的乡、村。运用图论软件可以很好解决这一问题。针对问题四：巡视组数已定，要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。我们分别考虑当其中两个变量不变时对最佳路线的影响。分为3种情况讨论。方案四：将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权（路程或时间）最小. 本题是旅行售货员问题的延伸多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题. 众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.方案五：本题给出了某县的道路交通网络图，要求的是在不同条件下，求解灾情巡视的最佳分组方案和路线。这是一类图上的点的遍历性问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。点的遍历性问题在图论中属于哈密顿问题，和旅行推销员问题类似。我们可以把该题抽象为图论的赋权连通问题，即有一赋权无向连通图，且。两村之间的公路长度即为无向图的边权。寻找最佳巡视路线，即在图中找到一条包含O点的回路，它至少经过所有的顶点一次，且使得总路程或总时间最短。对于问题一：如果将巡视人员分成三组，每组考察全县的一个区域，使所有乡（镇）、村都考察到，实际上就是将图分为三个连通的子图，且每个子图都与O点相连，然后在每个子图中寻找到一条含O点的最佳回路。针对三组巡视成员，需对该县分为三个区域。我们采用算法通过MATLAB编程求出图的最小树形图，然后将树形图分成三个区域，最后，采用哈密顿回路法求解每个子图内的最佳巡视路线。对于问题二：在问题一的基础上，问题二增加了巡视人员在各乡（镇）、村停留时间以及汽车途中行驶时间，并要求在24小时内完成巡视，求最佳分组和最佳巡视路线使各组的时间均衡性较好。通过分析可得要使巡视人员在24小时内完成巡视，则巡视人员至少分四组，然后根据最小树形图，将整个区域分成四个区域，利用最佳哈密顿回路法，求解每个子图的最佳巡视路线和最短巡视时间。最后利用定义的均衡度公式求出时间均衡度，根据求出的均衡度判断各组是否均衡，若均衡度较大，说明分组不够均衡，需要继续改进直至时间均衡度在允许的范围内。对于问题三：此问题就是要求如果有足够多的巡视人员，怎样确定最佳路线使完成巡视的时间最短。实际上，完成巡视的时间受到巡视最远乡（镇）、村路途时间和在乡（镇）、村停留时间的制约。通过分析可以求出巡视镇花费的时间最长，为6.43小时。由此可知，即使巡视人员再多，分组再细，完成巡视至少需要6.43小时。于是我们制订了两种分组巡视原则：对图中偏西且距县政府较远的乡（镇）、村，巡视车开往最远巡视乡（镇）、村，并在途经乡村放下巡视员，到达最远乡（镇）后等待，然后按原路返回并且依次接回巡视员；对图中偏东且距县政府较近的乡（镇）、村，制定按圈巡视原则，巡视车从县政府出发，巡视一圈并在途经乡村放下巡视员，车不停留继续巡视第二圈并在途中接回巡视员。然后根据分组原则，计算得出各组巡视时间。对于问题四：要尽快完成巡视，就得要求各组完成巡视的时间尽可能相等，因为总的完成巡视的时间按最长巡视时间计算。显然在分组不变的情况下，无论怎么改变，对每组的最佳巡视路线是没有影响的，但可能会影响各组间的均衡，因此此问题实际上是讨论对分组的影响，即不破坏原来分组均衡性的条件下，的最大变化范围。讨论不影响分组均衡时，定量的得出其他变量所允许的最大变化范围。最后根据得出的结论对分三组的实例进行讨论并分析结果。四、数据处理方案一：由题目可知，共有53个乡镇，即在网络图赋权网络图中共有53个点. 其中表示图G的53个节点，表示相关联的两点的边集，表示相关联两点间的权值。定义决策变量：其中相关联表示两点之间有权值，不相关表示之间没有权值。将这些点和权值生成图的矩阵，对于不相关的两点权值作为无穷大处理（数据.txt）。用MATLAB编写程序，得出该网络图的最小生成树。再运用迪克斯特拉算法求出出发点到各点的最短距离，即网络图的最短路径树。画出的两种图形如图1所示。方案二：为了研究方便，先给出图论中相关的定义：定义1 经过图G的每个顶点正好一次的圈，称为G的哈密尔顿圈(H图)定义2 经过每个顶点至少一次且权最小的闭通路称为最佳推销员回路。4.1图与数据的处理 首先，利用避圈法得到无向图的最小生成树：设是无向连通加权图，不妨设中没有环，否则把所有的环先去掉。步骤1. 按照边权从小到大的关系，将条边排序：;步骤 2. 取（最小生成树边的集合），然后依次检查. 若与已经在中的边，不构成回路，则取，否则就舍弃；步骤3. 当（或，或加入任何一条边都产生回路）时，算法中止，即得到的一棵最小生成树，再计算最小生成树的边权总和。得到带权无向图的邻接矩阵后，应用MATLAB编写问题的程序（程序见附录四），得到最小生成树的边权总和为，最小生成树的边的集合如下表所示：表4.1 最小生成树的边的集合22561316172320212627313567141722242525272832313413334133478993335363636373839394040404110111213141518131819172119414242424344444545454646472062325261250282930293647484949495050515252525353(注：表中为边的两个端点，分别代表点)根据表4.1得到的最小生成树的边的集合，可以在画图工具中挑出相应的边，抹去不相关的边，最终得到灾情巡视路线的最小生成树如下图：图4.1 灾情巡视路线的最小生4.2任意两点间的最短距离采用算法(程序见附录)求得任意两点的最短距离矩阵以及最短路线查找矩阵 。例如从矩阵D上可以观察到离O点最远距离的点是H，从矩阵R中就能查找出从O点到H点的最短路线为O2567E9F12H12F9E7652O。方案三：4.1理论知识1定义 一个图G是指一个二元组(V(G),E(G)，其中：其中元素称为图G的顶点。 2) E(G)是顶点集V(G)中的无序或有序的元素偶对组成的集合，即称为边集,其中元素称为边.定义 图G的阶是指图的顶点数|V(G)|, 用来表示；图的边的数目|E(G)|用来表示. 用表示图，简记也用来表示边 设G=是加权的连通图，对任意边e，其权C(e)0。令T=是G的一棵加权生成树，其所有枝上的权的总和称为树T的权，记为C(T)。一般说来，对于G的不同生成树T，C(T)也是不同的。可以知道，其中必有一个最小者，而这正是人们最为感兴趣的。因此，给定连通加权图G=，T0=是G的加权生成树，C(T0)为T0的权。若对G的任意加权生成树T均有C(T0)C(T)，则称T0是G的最小生成树。下面给出一种求最小生成树的方法(破圈法)：设G是有n个结点的连通图，下面算法产生的是最小生成树。算法的基本思想先将图G 的边按权的递减顺序排列后, 依次检验每条边, 在保持连通的情况下, 每次删除最大权边, 直到余下n- 1 条边为止。4.2数据分析处理我们把53个乡(镇)村看作53个顶点，它们之间的距离为权重，建立邻接矩阵，运用图论软件，可视化如下图所示运用图论软件，自动选择最短路径，可以求得O点到53个顶点的最短距离及路径。 图一方案四：.任意两点，间的间距。 .各点的停留时间，即点权。汽车行驶速度。 从任意点至点的时间，则。方案五：4.1强加权矩阵运用算法，求得任意乡、村与乡、村之间的最短距离。 1234505152531014.200019.000039.90006.000016.100033.400018.3000214.200004.800025.70008.200018.300036.200021.1000319.00004.8000020.900013.000023.100041.000025.9000439.900025.700020.9000033.900044.000061.900046.8000522.50008.300013.100024.000016.500026.600044.500029.4000632.200018.000022.800033.700026.200036.300054.200039.1000739.500025.300023.300027.800033.500043.600061.500046.4000854.700040.500038.500020.400048.700058.800076.700061.6000954.500040.300038.300036.200048.500058.600076.500061.40001070.900056.700054.700052.600064.900075.000092.900077.8000。4467.100060.900065.700071.600061.100059.100072.600074.00004559.300045.100049.900055.800053.300053.700067.200066.20004649.700043.600048.400059.300043.700041.700055.200056.60004744.000029.800034.600042.300038.000041.800055.300050.90004825.800019.700024.500035.400019.800029.900047.800032.70004937.100033.900038.700049.600031.100021.000034.500044.0000506.00008.200013.000033.9000010.100028.000012.90005116.100018.300023.100044.000010.1000020.400023.00005233.400036.200041.000061.900028.000020.4000015.10005318.300021.100025.900046.800012.900023.000015.100004.2均衡度处理本文定义均衡度公式为，。其中表示分组数，表示各分组的路程或时间的权值，用来衡量分组的均衡性。设定为最大允许均衡度，显然，越小，说明分组的均衡度越好。确定一个后，以下各模型的均衡度，则模型精度良好，否则继续改进。4.3最小树成法因为最小树成中能包含图中所有的顶点，而且最小树的边权是相邻两顶点间的距离，它描述了顶点之间的相近程度，故可以采用最小生成树进行分组。本模型的主要思想是：首先采用算法得到图的最小生成树，然后基于最小生成树生成一个可行的巡视路线，求得路线的最优总路程为。利用下述算法可以在赋权图求出最小生成树。（1）选取边，使得最小；（2）设已经选取，则在中选取边使得： （）不含圈；（）尽可能小；（3）当第2步无法实施时停止。 根据算法进行编程求解（具体程序见附录1），于是我们得到图的最小生成树如图1。图1四、模型建立与求解方案一：6.1 问题一6.1.1 模型建立通过问题一的分析，建立多目标规划模型。（1）三组巡视的总路线最短：（2）巡视路线尽量均衡：我们设当时，认为均衡度比较好。综上得出目标函数：约束条件：每个小组所走的路线必须是条回路。6.1.2 模型求解根据问题一的分析，根据两图的公共部分作为分组的界限，分组图如下（图2）：将分好的三个子区域分别利用哈密顿原理进行编程求解，得到三个小组的巡视路线为：第一组：O, P ,26 ,N ,23, 24 ,27 ,28 ,Q, 29, Q ,30, 32 ,31, R ,A, 33, 35 ,34 ,B, 1 ,O行走的总路程为第二组：O ,M ,21, K ,22 ,17, 16 ,I ,18 ,I ,15 ,14, 13, 14,H ,12 ,G ,11, J ,19, L ,20, 25 M ,O行走的总路程为第三组：O, 2 ,5 ,6 ,7, E, 9 ,F, 10 ,F, 9 ,E, 8 ,4 ,D, 3, C, O行走的总路程为三组所行走的总路程：6.1.3均衡度分析根据三组所行走的路程求得均衡度：因为，我们认为均衡度不好，需要对分组进行修正。通过结果发现第二小组所行走的路程比较多，而第三小组行走路程较短，我们考虑将分区2中离分区1较近但距1较远的11，G，12三个点划到第三分区中，而分区的区域不变。在此情况下，重新利用哈密顿算法编程得到三个小组的巡视路线如下表 1：小组路线行走路程第一组O, P ,26 ,N ,23, 24 ,27 ,28 ,Q, 29, Q ,30, 32 ,31, R ,A, 33, 35 ,34 ,B, 1 ,O206.8km第二组O,M,25,21,K,22,17 ,16 ,I ,18 ,I ,15 ,H ,14 ,13 ,J ,19 ,L ,20, 25, M, O216.6km第三组O ,2 ,5 ,6, 7 ,E, 9 ,F ,10, F ,12 ,G ,11, E ,8, 4, D ,3 ,C, O186.4km则三组所行走的总路程：此分区下的均衡度：由可知，此种情况下的分区较为合理。各小组的巡视路线如下图36.2问题二6.2.1模型准备：根据第一问的结果得出在分三组的情况下，各小组所用时间：第一组：第二组：第三组：通过以上数据观察可知，分三组时不能满足题目要求，所以我们先考虑分四组。6.2.2模型建立根据问题二分析，建立多目标规划模型。要求设计最佳巡视路线，即使总路程最短，并且所用时间相对均衡，得出目标函数：约束条件：每个小组巡视所用时间均不超过24小时，即6.2.3 模型求解根据问题二分析，得出整个区域的分组情况。利用哈密顿算法编程求得各小组最短巡视路线及所用时间如下：第一组:巡视区域：A,B,Q,R,1,29,30,31,32,33,34,35最短路程，所用时间第二组：巡视区域：K,M,N,P,16,17,21,22,23,24,25,26,27,28最短路程，所用时间 第三组G,H,I,J,11,12,13,14,15,18,19,20最短路程，所用时间 第四组C,D,E,F,2,3,4,5,6,7,8,9,10最短路程，所用时间 6.2.4均衡度分析根据以上所求结果，发现所用时间都小于24小时。但第三组用时较多，几乎接近24小时，而第一组用时较少。我们对各组所用时间进行均衡度分析：因为，我们认为此分组结果不够合理，需要重新调整分组方式。通过观察分析，将2分区中的村28划分到1中，同时将3分区中的村11划分到4中，同样利用matlab编程求得各组的最短巡视路线和所用时间，如下表2：组号巡视点寻访个数巡视路径总路程长耗时长（小时）第一组A B Q R 1 28 29 30 31 32 33 34 3513O,1,B,A,34,35,33,31,32,30,Q,28,Q,29,R,O142.121.06第二组K M N P 16 17 21 22 23 24 25 26 2713O,P,26,27,26,N,24,23,22,17,16,17,K,21,25,M,O152.121.35第三组G H I J L 12 13 14 15 18 19 2012O,M,6,L,19,J,13,G,12,H,14,15,I,18,J,19,20,25,M,O196.522.61第四组C D E F 2 3 4 5 6 7 8 9 10 1114O,2,5,6,7,E,11,G,12,F,10,F,9,E,8,4,D,3,C,O186.423.33根据表中数据可知，所有时间均小于24小时，对时间进行均衡度分析为：我们认为此情况下的分组较为合理，同时得出各组的路线图为：6.3问题三由最短树路径树可知，从点到所有点距离中的最大距离，从点出发到点。同时计算出其所用时间：即完成此次巡视所用的最短时间。在不超过的情况下，其他小组巡视点的剩余时间：其中下面对剩余时间的利用进行讨论：当时，直接返回县政府；当时，巡视一个村；当时，巡视两个村或一个乡（镇）；当时，巡视三个村或一个村和一个乡（镇）；当时，巡视四个村、两个个乡（镇）或两个村和一个乡（镇）；当，巡视五个村、三个村和一个乡（镇）或一个村和两个乡（镇）；当，情况不存在。根据对的讨论和我们的巡视原则，逐个除去已巡视的点，直到所有点巡视完结束，最终求得需要23组。各小组巡视情况如下表3：小组路线巡视点剩余时间兼巡视点最终路线1O,2,5,6,7,E,9,F,12,HH0无O,2,5,6,7,E,9,F,12,H2O,2,5,6,L,19,J,13,14141.2713O,2,5,6,L,19,J,13,143O,M,25,21,K,18,I,15151.4318O,M,25,21,K,18,I,154O,2,5,6,7,E,9,F,12121.589O,2,5,6,7,E,9,F,125O,2,5,6,7,E,9,F,10101.668O,2,5,6,7,E,8,E9,F,106O,2,5,6,7,E,11,GG0.85无O,2,5,6,7,E,11,G7O,M,25,21,K,18,II0.94无O,M,25,21,K,18,I8O,M,25,21,K,17,16161.9817O,M,25,21,K,17,169O,2,5,6,7,E,11112.23EO,2,5,6,7,E,1110O,2,5,6,7,E,9,FF1.287O,2,5,6,7,E,9,F11O,2,5,6,L,19,JJ1.3319O,2,5,6,L,19,J12O,P,26,N,23,22222.63KO,P,26,N,23,22,K,2213O,P,26,N,24242.9023,26O,P,26,N,24,23,2414O,M,25,21213.17M,25O,M,25,2115O,2,5,6,LL2.205,6O,2,5,6,L16O,M,25,20203.24NO,M,25,N,25,2017O,1,A,34,35353.37A,34O,1,A,34,3518O,R,29,Q,30303.39Q,29O,R,29,Q,3019O,2,3,D,443.433,DO,2,3,D,420O,R,31,32323.70R,33O,R,31,33,31,3221O,P,26,27273.81P,28O,P,26,27,28,2722O,R,31314.171,BO,R,31,1,B23O,2,CC3.772O,C,O,26.4问题四完成所有巡视所用最短时间：我们以问题一中的第一组为例，其中。为方便讨论，将T,t统一作为时间变量，设(),则上式可改写为：当停留时间t不变时，利用matlab作图得到巡视时间与行驶速度的关系如下：由图示可知，当取值较小时，对巡视时间影响较大，即速度小范围波动时，我们也需重新考虑分组。取值较大时，对巡视时间影响较小，即小范围波动时，不需要调整分组情况。当速度不变时，同样利用matlab作图得到巡视时间与停留时间的关系如下图：由图形可知，与成线性变化。即无论取何值，对的影响较大，当停留时间小范围波动时，也需重新考虑分组。3. 方案二：问题一的解答此题研究的是最佳巡视路线的问题。首先需要根据分组准则进行分组，然后提出相应的算法并对该问题进行求解。5.1分组的确定方法我们按照各个顶点的聚集方式及方位分成三组（见附录三图3.1），分别为东北方向、东南方向、西北方向，即将分成三个部分，分别为。满足如下条件：划分组的准则为： 各组的点聚集程度尽可能的高； 各组的点尽可能的靠近个； 尽量使所分的子图的边权总和（第组巡视所走路程）均衡，这可以通过均衡度来衡量，越小，则均衡度越大；尽量使所分的子图能够形成较大的哈密尔顿圈；5.2模型的建立（最优Hamilton回路算法）对于每一个子图，分别寻找其最大的Hamilton回路，建立如下模型：设，是边的权值，即与之间的距离，（1表示连接，0表示不连接）。则有 5.3模型一的求解根据前面所给的分组规则，利用最优Hamilton回路算法(程序见附录)得到如下分组方案：表5.1最佳巡视路线组号Hamilton回路路程1OP26N23242728Q30Q29RA3331323534B1O198.92OC3D48E11G12F10F9E7652O183.33OM252021K221716I18I151413J19L652O215.4巡视总路程为597.6 km.由表5.1中的结果，可得到均衡度5.4结果的改进 比较大，我们需要对所求路线进行一些调整，发现改变个别点后可以使均衡程度得到较好的水平，但是需要增加巡视总路程。采用逐次改进算法对表5.1的结果进行改进(程序见附录)，最后得到改进后的方案如下：表5.2改进后的最佳巡视路线组号Hamilton回路路程1OP26N23242728Q30Q29RA3331323534B1O198.92OC3D48E9F10F12H12G11E7652O203.73OM252021K221716I18I1514H1413J19L652O195.6改进后的巡视总路程为598.2 km,得到改进后的均衡度为所以改进后的路线方案的均衡度更大，更接近最优解。4. 问题二的解答6.1分组的确定（就近原则和均衡原则）在给定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。那么在乡镇村停留的总时间为小时，遍历各个村落的时间大于小时，显然如果仅分成三组，不可能在24小时内完成巡视，分组的数目至少为四组。为了避免一个组巡视完后等待另一个组较长时间，我们采用均衡原则，得到平均一个组分有4个乡(镇)，9个村；根据就近原则，得到每个组的乡(镇)和村相隔的较近，大致都分在同一区域。（分组图见附录三图3.2）6.2模型二的建立（同模型一）则得到问题二的模型(最优Hamilton回路算法)6.3模型二的求解用类似问题(1)中的作法求出各组的近似最佳巡视路线(程序见附录六)：表6.1最佳的巡视路线最佳组号巡视路线路程(km)时间(h)1OR29(Q)(28)2728Q303231333534AB1O159.222.552OM252021K(17)1617222324N26PO143.621.103O(M)(25)(21)(K)18I1514H12G11(G)13J19L6(5)(2)O196.121.604OC(3)25(6)7(E)(9)(F)10F9E84D3(2)O194.821.57注：括号中的地点只经过不作停留。得到巡视时间的均衡度6.4结果分析 单从均衡度的值来看，这个分组的均衡性还是比较好的，且时间都限制在24小时内。但利用回路算法求解时，得到的最佳路线是不准确的，因某些点要重复经过，而实际只需停留一次即可，这样得出的路线长度应该比实际要长一些，经过计算时间，利用算法求得任意两点的最短路，然后对求得回路进行适当调整，并对结果中只经过不停留的点用括号表示，最终得到分组结果即为表6.1。5. 问题三的解答对于问题三，建立如下求解过程模型模型三7.1 模型三的建立在问题三中，在、和一定，在巡视人员足够多的情况下，需要寻找一种最佳的巡视路线方案，使得巡视的时间最短。很显然，如果每个乡（镇）村均分配一组去巡查，即共分配组，每组仅负责巡视一个乡（镇）或村，则巡视最早结束应该决定于巡视时间最长（设为）的一组，这个时间也是完成巡视的最短时间。但是如果这样分配，需要的巡视人员很多，并且各组巡查的时间很不均衡。所以需要寻找分配组数最少，且均衡度最高的一种方案，根据分析得到问题三的目标为： ，并且有约束条件：对于，可以采用如下算法确定： 将所有点按其到的距离从大到小排序，然后按照下面步骤依次分组； 距离最远的点先分配组，负责巡查该点的小组，按最短路径达到该点，到达并巡视完成后，按原路返回，不停留； 对于未分配人员巡查的次远点，若以最短路径达到该点，巡视完成按原路返回的时间满足：若，则第组可以多巡查一村（与其靠近的乡镇村优先选择），并按最短路径返回，增加值；若，则第组可以多访问乡（镇）村（与其靠近的乡镇村优先选择），并按最短路径返回，增加值； 若，则该组不能再增加巡视点，再找次远点，转步骤，直到所有的点都有分配。7.2 模型三的求解 在数据分析与处理中，已经求得任意两点的最短距离矩阵以及最短路线查找矩阵，根据可以得到距离最远的点为，最远距离为：，那么可以从出发，沿最短路线到达点巡视，然后原路返回，沿途所有点一律不停，所需的时间为，这个时间即为完成巡视的最短时间。以此时间为限制，根据模型三的算法，最后得到22组巡视路线，其结果如表7.1 。表7.1.最佳巡视路线组号巡视线路停留点巡视路程(km)巡视时间(h)1O2567E9F12H12F9E7652OH1556.42862O256L19J131413J19L652O13,14145.46.15433OM2521K18I15I18K2125MO18,15139.85.99434O2567E9F12G11E7652O12,11137.85.93715O2567E9F10F9E76 52O9,10131.85.76576O2567E11G11E7652OG125.45.58297OM2521K18I18K2125M OI122.25.49148OM2521K171617K2125MO17,16120.65.44579O2567E9F9E7652 O7,F110.26.148610O256L19J19L652O19,J99.46.102911O2567E8E7652OE,899.45.840012OP26N2322K2125MO22,K102.85.937113OP26N24232125MO24,23,21101.95.911414O256L2025MOL,20,2582.86.365715OR29Q30Q29RO29,Q,3074.06.114316O1A343534A1OA,34,35726.057117O23D4D32O3,D,469.85.994318OP26NMON,M65.15.8619OR313231RO31,32,R60.45.725720OP262726POP,26,2756.85.622921O25652O1B1O5,6,1,B78.26.234322OP28PO23CO28,2,C77.75.5886 得到相应的时间均衡度为7.3结果分析 本题依旧用偏差程度来刻画分组路线的均衡性，得到相应的时间均衡度，从使用时间的角度来看，这个分组的均衡性比较好，能保证所有的巡视小组在较短的时间内完成巡视，而且使用的时间相差很小，从而极大地避免了一个组巡视完后等待另一个组较长时间的情况发生。但从具体的各小组的巡视路线和路程来看，有些地方重复出现了很多次，所巡视的路程也增加了很多，而我们只取其中的一次作停留视察。所以如果只考虑在最短时间完成巡视而建立并使用上述方案，会造成很大的人力（巡视人员大量增多导致）和财力（路程变大，使得路费增多导致）等方面的浪费。由此可见，此种最佳的巡视路线对当前要努力创建的节约型社会而言在实用性方面并不是很可取的。6. 问题四的解答 针对问题四，我们先进行理论分析，然后进行定量分析。8.1理论分析以分四组为例，采用控制变量法来讨论的变化对最佳巡视路线的影响 。依题意，巡视时间满足为了讨论的方便，可以令，则巡视时间的表达式为：1) 当数目完全相同时，即每一组的情况完全一样时，的改变对最佳巡视路线没有影响；2) 若不变，变化i. 若的变化幅度很小，则对每组巡视所用的时间的影响很小，那么对最佳巡视路线影响不大；ii. 若的变化幅度大，则对有显著影响，那么此时各村、乡（镇）的停留数目应该尽可能均衡，才能保证对最佳巡视路线的影响不大；否则，对于最佳巡视路线的影响就十分明显了，所以必须对路线进行调整。3) 若不变，变化i. 若的变化很小，则对最佳巡视路线的影响不大；ii. 如的变化幅度很大，则对的值起主导作用，那么此时各条路线的总路程应该尽可能均衡，才能保证的变化对最佳巡视路线的影响不大；否则，对路线有显著影响，就必须对其进行调整。8.2定量分析以分四组为例，进行定量分析。当，即为模型二的结果，如表8.1表8.1 V,t都不发生改变组号时间 (h)122.55221.10321.60421.57 针对理论分析(2),即保持V不变，t发生改变的情况有：当和时，得到的结果如下表：表8.2 V不变，t改变后的结果组号时间（h）时间（h）120.748637.5486220.302937.1029321802938.6029421.765738.5657 将表8.2中的数据与表8.1中的数据进行对比，得到：V不变时，当的变化幅度很小（此处变化值为0.1）时，对每组巡视所