搜索
1提出问题下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。问题三：在上述关于T,t和v的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和v改变对最佳巡视路线的影响。2问题假设与符号说明2.1问题假设假设一：假设在巡视过程中不考虑天气、汽车故障等因素的影响假设二：假设路线上的公路路况良好，没有被洪水冲断，可以供巡视工作使用。假设三：假设在巡视工程中，经过邻县村时，不做任何时间的耽搁。假设四：假设巡视人员上下车的时间及汽车加油时间忽略不记。假设五：假设汽车在行驶途中车速不变且满足速度要求。假设六：假设可使用车辆数量不受限制。假设七：假设巡视人员的巡视时间可以大于当地所需巡视时间。假设九：假设巡视人员巡视时可以不需要车辆陪同。2.2符号说明(,)GVE赋权连通图；iG赋权连通图的第i个子图(1,2,)i，kiL子图Gi中的最佳回路；iC最佳回路Li的各边权值之和ijW第i个乡、村到第j个乡、村的距离(j1,2,53)i，，ijX某组从城市i到城市j时为1，无巡视组视为0ie表示各乡（镇）停留时间je表示各村停留时间均衡度Si第i组的最佳推销员回路路线总长度；iX第i组所要停留的乡（镇）数目；iY第i组所要停留的村的数目三、问题分析本文研究的是考察灾情最佳巡视线路设计的问题，准确合理的路线设计对灾情巡视救治起着重要作用。方案一：对于问题一，题目要求在分三组巡视的情况下，使总路程最短且各小组所走路程均衡。先考虑分区，我们将得出的最小生成树图形和最短路树图形，进行比较并找出其公共部分。分组要求尽量不破坏最短生成树和最小生成树，所以我们以公共部分为界限，将此网络图分为三组。为使每小组所走路程均衡，我们引入了均衡度。它表示最大路程和最小路程的差值与最大路程的比值。越小，表示均衡度越好。以总路程最短和均衡度最小作为目标函数建立多目标规划模型，利用哈密顿原理得出各组的巡回路线，并对其分析修正求得各组最优巡回路线。对于问题二，要求在24小时内完成所有巡视。通过第一问的结果，求得在分三组的情况下所用的平均时间htTT.828)358.6093517(311大于24小时，所以我们先考虑分四组。我们的分组原则为：1、每子区域所分得的点近似相等；2、尽量使每一个子区域连通；3、使每一个子区域中与点O的最短路上的点在该区域内。根据以上分组原则将整个图大致划分为四个子图，同样利用哈密顿算法求得在相对均衡的情况每个小组的最短路径和所需时间。如果部分时间大于24小时，则调整分组方式；若所有时间均大于24小时再考虑多加一组。直到找到相对均衡条件下的最佳路线。对于问题三，考虑在人员足够多的情况下，求出最短的巡视时间。假设一个小组只巡视一个点的情况下，则去巡视离O点最远的点所花时间最长。我们以巡视小组中所耗时间最长的小组所用时间作为这次整个巡视的最短时间。要使这次巡视时间最短，则要求去巡视离O点最远的点所花时间最小，由图一可知，离O点最远的点为H，所以就以巡视H所花时间作为minT。当此小组只巡视H时，minT最小。在不超过minT的情况下，根据其他小组的剩余时间确定沿途是否巡视其他点。其中巡视原则为：①当一组人员巡视完规定点后时，在剩余时间允许的情况下，优先考虑原巡视点附近而距离O较远的点，②最大限度使用剩余时间，主要考虑原则①。按照此原则，逐个巡视，直至巡视完所有点。对于问题四，若巡视组数已定，则每个小组的最短路径就已确定，T、t、V改变只影响的是整个的巡视时间。要求尽快完成巡视，即巡视时间要尽可能小。巡视时间包括到巡视点的行驶时间和在巡视点的停留时间。行驶时间主要取决于速度V，而停留时间由T、t决定。所以此问题讨论的是当T、t、V改变时对巡视时间的影响，即对T、t、V的灵敏度分析。方案二：在数据分析中，我们采用Kruskal避圈法得到了最小生成树，见附录二。针对问题一：题目要求分三组（路）巡视，并且要设计出总路程最短且各组尽可能均衡的巡视路线。为此，根据数据分析中得到的最小生成树，我们可以按照各个顶点的聚集方式和方位分为三组，然后运用最优Hamilton回路算法建立模型一，通过Lingo求解分别得到三组巡视路线和对应的巡视路程，接着算出均衡度，并对巡视路线的结果进行逐步改进，使得均衡程度达到较好的水平。针对问题二：考虑停留时间T、t、速度v、分组数m等因素，通过分析我们得知随着其中每个量的改变，都将对回路的设计结果产生很大影响。所以，我们可以采用就近原则和均衡原则对巡视路线进行重新分组，然后使用最佳Hamilton回路算法建立模型二来得出最佳巡视路线和对应路线巡视完需要的时间，最后根据得出的结果算出对应的均衡度。针对问题三：需要我们在最短时间完成巡视的要求下，得到最佳的巡视路线。因为巡视人员足够多,即巡视组数足够多,要使巡视时间最短,可以假设每个乡(镇),村都派一组,因此要派52个组。根据任意两点间的最短路径的求解方法(FordWarshall算法),得到52个乡(镇)、村分别对于县城的最短距离和相应的以乡(镇),村为目的地的巡视小组完成巡视的最短时间，则得到其中较大的那个即为所求的最短时间。为了简化模型，可任取离政府较远的乡镇、村为特殊点，进行比较计算得出最短时间。针对问题四：要求在巡视组数已定和尽快完成巡视的条件下，讨论T，t和V改变对最佳巡视路线的影响。文中以分4组为例进行讨论。在讨论时，可以采用控制变量法分别对VtT,,进行理论分析和定量分析，并就各因素可能产生的影响提出改进的建议。方案三：此问题可以转化为旅行商问题，再设计相应的算法求解针对问题一：问题一要求设计3组巡视，巡视总路程最短且尽可能均衡，首先我们通过主观筛选法将原图划分为3个子图，每个子图顶点数大约为17个，相邻的点划在一个子图中，且尽量使每个子图构成一个回路，这样将原问题转化为单旅行商问题求解针对问题二：问题二在问题一的基础上加了时间的限制，在每一个顶点都有停留时间，且在24小时巡视完。通过计算可得至少分为4组，才可能实现。和问题一类似我们将原图划分为4个子图，分别计算每组的巡视时间，设计每组的巡视路线。针对问题三：问题三T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间，并设计最佳路线。首先，我们分析可知巡视H使用的时间是最长的。那么，设计分组时，其它组巡视的时间不能超过这一最长时间。在计算过程中我们先从距O点远的点开始考虑，因为若巡视时间与最小时间相差较远可以考虑顺便访问途径的乡、村。运用图论软件可以很好解决这一问题。针对问题四：巡视组数已定，要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。我们分别考虑当其中两个变量不变时对最佳路线的影响。分为3种情况讨论。方案四：将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权（路程或时间）最小.本题是旅行售货员问题的延伸－多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.显然本问题更应属于NP完全问题.有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.方案五：本题给出了某县的道路交通网络图，要求的是在不同条件下，求解灾情巡视的最佳分组方案和路线。这是一类图上的点的遍历性问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。点的遍历性问题在图论中属于哈密顿问题，和旅行推销员问题类似。我们可以把该题抽象为图论的赋权连通问题，即有一赋权无向连通图(,)GVE，且OV。两村之间的公路长度即为无向图的边权()we。寻找最佳巡视路线，即在图(,)GVE中找到一条包含O点的回路，它至少经过所有的顶点一次，且使得总路程或总时间最短。对于问题一：如果将巡视人员分成三组，每组考察全县的一个区域，使所有乡（镇）、村都考察到，实际上就是将图(,)GVE分为三个连通的子图Gi，且每个子图都与O点相连，然后在每个子图中寻找到一条含O点的最佳回路。针对三组巡视成员，需对该县分为三个区域。我们采用Kruskal算法通过MATLAB编程求出G图的最小树形图，然后将树形图分成三个区域，最后，采用哈密顿回路法求解每个子图内的最佳巡视路线。对于问题二：在问题一的基础上，问题二增加了巡视人员在各乡（镇）、村停留时间以及汽车途中行驶时间，并要求在24小时内完成巡视，求最佳分组和最佳巡视路线使各组的时间均衡性较好。通过分析可得要使巡视人员在24小时内完成巡视，则巡视人员至少分四组，然后根据最小树形图，将整个区域分成四个区域，利用最佳哈密顿回路法，求解每个子图的最佳巡视路线和最短巡视时间。最后利用定义的均衡度公式求出时间均衡度，根据求出的均衡度判断各组是否均衡，若均衡度较大，说明分组不够均衡，需要继续改进直至时间均衡度在允许的范围内。对于问题三：此问题就是要求如果有足够多的巡视人员，怎样确定最佳路线使完成巡视的时间最短。实际上，完成巡视的时间受到巡视最远乡（镇）、村路途时间和在乡（镇）、村停留时间的制约。通过分析可以求出巡视H镇花费的时间最长，为6.43小时。由此可知，即使巡视人员再多，分组再细，完成巡视至少需要6.43小时。于是我们制订了两种分组巡视原则：对图中偏西且距县政府较远的乡（镇）、村，巡视车开往最远巡视乡（镇）、村，并在途经乡村放下巡视员，到达最远乡（镇）后等待，然后按原路返回并且依次接回巡视员；对图中偏东且距县政府较近的乡（镇）、村，制定按圈巡视原则，巡视车从县政府出发，巡视一圈并在途经乡村放下巡视员，车不停留继续巡视第二圈并在途中接回巡视员。然后根据分组原则，计算得出各组巡视时间。对于问题四：要尽快完成巡视，就得要求各组完成巡视的时间尽可能相等，因为总的完成巡视的时间按最长巡视时间计算。显然在分组不变的情况下，无论,,TtV怎么改变，对每组的最佳巡视路线是没有影响的，但可能会影响各组间的均衡，因此此问题实际上是讨论,,TtV对分组的影响，即不破坏原来分组均衡性的条件下，,,TtV的最大变化范围。讨论不影响分组均衡时，定量的得出其他变量所允许的最大变化范围。最后根据得出的结论对分三组的实例进行讨论并分析结果。四、数据处理方案一：由题目可知，共有53个乡镇，即在网络图赋权网络图），，（WEVG中共有53个点.其中)53(},,{21nvvvVn表示图G的53个节点，}{ijeE表示相关联的两点ji,的边集，}{ijwW表示相关联两点ji,间的权值。定义决策变量ijr：两点不相关表示两点相关联表示jijirij.0,1其中相关联表示ji,两点之间有权值，不相关表示ji,之间没有权值。将这些点和权值生成图G的矩阵，对于不相关的两点权值作为无穷大处理（数据.txt）。用MATLAB编写程序，得出该网络图G的最小生成树。再运用迪克斯特拉算法求出出发点O到各点的最短距离，即网络图的最短路径树。画出的两种图形如图1所示。方案二：为了