下载文档原格式
灾情巡视路线的数学模型(总26页)-CAL-FENGHAI.-(YICAI)-Company One1-CAL-本页仅作为文档封面，使用请直接删除灾情巡视路线的数学模型摘要本文是解决灾情巡视路线最佳安排方案的问题。
某县领导将带人下乡巡视灾情，打算从县城出发，视察所有乡、村后返回县城。
为确定安排巡视路线，本文将此安排问题转化为旅行售货员问题，建立了四个最优化模型解决问题。
对于问题一,建立了双目标最优化模型。
首先将问题一转化为三个售货员的最佳旅行售货员问题，得到以总路程最短和路程均衡度最小的目标函数，采用最短路径的Dijkstra算法，并用MATLAB软件编程计算，得到最优树图，然后按每块近似有相等总路程的标准将最优树分成三块，最后根据最小环路定理，得到三组巡视路程分别为208.8km、205.3km和210.5km，三组巡视的总路程达到624.6km，路程均衡度为2.47%,具体巡视路线安排见表1。
对于问题二，建立了单目标最优化模型。
首先根据条件计算可确定至少要分4组巡视，于是可将问题转化为四个售货员的最佳旅行售货员问题，采用Kruskal算法求出巡视路线的最小生成树。
再根据求最优哈密顿圈的方法，运用LINGO软件编程计算，求出了各组的最佳巡视路线。
各组巡视的路程分别为154.3km、184km、136.5km、186.4km，时间分别为22.41h、22.26h、21.90h、21.33h,时间均衡度为4.82%，具体巡视路线安排见表2。
对于问题三,建立了以最少分组数为目标函数的单目标最优化模型。
运用问题一中最短路径的Dijkstra算法，运用LINGO软件编程计算,得到从县城到各点的最短距离，再经过计算可得到本问的最短巡视时间为6.43小时。
最后采用就近归组的搜索方法，逐步优化，最终得到最少需要分22组进行巡视，具体的巡视方案见表3。
对于问题四，建立了单目标优化模型，并且对变量进行讨论。
在分析乡（镇）停留时间T，村庄停留时间t和汽车行驶速度V的改变对最佳巡视路线的影响时，我们通过控制变量的变化，初步的得出了当T与t变化时和V变化时对最佳巡视路线的影响。
最优灾情巡视路线摘要关键字1问题重述下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。
今年夏天该县遭受水灾。
为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。
巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。
问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。
要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。
问题三：在上述关于T , t和v的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。
问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和v改变对最佳巡视路线的影响。
2问题假设与符号说明2.1问题假设假设一：假设在巡视过程中不考虑天气、故障等因素的影响假设二：假设路线上的公路没有被洪水冲断，可以供巡视工作使用。
假设三：假设在巡视工程中，经过邻县村时，不做任何时间的耽搁。
2.2符号说明3问题分析本题给出了某县的道路交通网络图，要求的是在不同条件下，灾情巡视的最佳分组方案和路线。
这是一类图上的点的遍历性问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。
点的遍历性问题在图论中属于哈密顿问题和旅行推销员问题类似。
如果巡视人员只分一组，巡视路线是指巡视人员从县政府O 出发，走遍各乡（镇）、村最后又回到县政府。
我们可以把该题抽象为图论的赋权连通问题，即有一赋权无向连通图(,)G V E ，且O V ∈。
两村之间的公路长度即为无向图的边权()w e 。
寻找最佳巡视路线，即在图(,)G V E 中找到一条包含O 点的回路，它至少经过所有的顶点一次且使得总路程（总时间）最短。
针对问题一：如果将巡视人员分成三组，每组考察全县的一个区域，使所有乡（镇）、村都考察到，实际上就是将图(,)G V E 分为三个连通的子图i G ，且每个子图都与O 点相连，然后在每个子图中寻找到一条含O 点的最佳回路。
灾情巡视路线模型摘要本文研究的是考察灾情最佳巡视线路设计的问题，属于多旅行商问题，为此我们建立了网络图模型。
利用最小生成树图形和最短路树图形相结合，通过分析、计算比较得出最优解。
对于问题一，我们建立赋权网络图。
利用matlab编程得到此网络图的最小生成树图和最短路径树图，以两图相重合的部分作为分区的界限，将整个网络图分为三个分区。
以总路程最短和均衡度最小作为目标函数建立多目标规划模型，利用哈密顿算法编写matlab程序求得各组最优巡回路线(见附表1)。
对于问题二，基于对问题一结果的分析，发现分三组的情况下，不能满足题目要求。
因此我们首先考虑分四组的情况。
在分三组的基础上根据分组原则将图大致划分为4各子图。
同样以巡视路程最短和时间均衡度最小为目标函数，各巡视时间小于24小时作为约束条件建立多目标规划模型。
利用哈密顿算法编程求得各组最佳巡视路线及巡视时间（见附表2）。
对于问题三，在巡视人员足够多的情况下，巡视距离O点最远的点所用的时间为最短时间，根据最短路径树，从远到近，依次巡视各村镇，在所用时间不大于最短时间的前提下，各组尽可能多的巡视几个村镇，进行分组确立巡视点，并对已巡视过的点进行逐个剔除。
通过人工记录，得出分组情况及巡视路线（见附表3），最短时间为6.4286小时。
对于问题四，在组数固定时，则各组的最短路径就已确定，T、t、V改变影响的只是整个巡视时间。
我们利用matlab编程画图得到T、t、V与巡视时间的关系曲线。
观察曲线发现：①当速度V较小时，V的变化对巡视时间的影响较大；②停留时间t与巡视时间呈线性关系，无论t取何值，对巡视时间影响都较大。
此两种情况下都需适当调整分组。
关键词最小生成树最短路径树赋权网络图哈密顿算法一、问题重述1.1背景分析：今年夏天该县遭受水灾。
为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。
巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。
最佳灾情巡视路线模型【摘要】“图论”是组合数学的分支，它与其他的数学分支，如群论、矩阵论、拓扑学，数值分析有着密切的联系。
在其它科学领域，如计算机科学、运筹学、电网络分析、化学物理以及社会科学等方面图论也具有越来越重要的地位，并已取得丰硕的成果。
而且，图论的理论和方法在数学建模中也有重要应用。
本文概述了一些常用的图论方法和算法，并通过举例（灾情巡视路线）说明其在数学建模中的应用。
【关键词】图论灾情巡视Hamilton回路数学模型预备知识定义1 完全图：如果图G中每一对不同的顶点恰有一条边连接，则称此图为完全图。
定义2 连通图：如果对图G=（V，E）的任何两个顶点u与v，G中存在一条（u-v）路。
则称G是连通图。
定义3 加权图：边上有数的图称为加权图。
在加权图中，链（迹、路）的长度为链（迹、路）上的所有边的权植的和。
定义4 Hamilton回路：图G中的一个回路C称为一个Hamilton回路如果C含有G 的所有顶点。
含有Hamilton回路的图称为Hamilton图。
定义5 欧拉回路：经过图G的每条边的迹称为欧拉迹，如果这条迹是闭的，则称这条闭迹为G的欧拉回路。
一数学建模中常用的图论方法1 迪克斯特拉算法（Dijkstra）1.1问题来源在加权图中，我们经常需要找出两个指定点之间的最短路，通常称为最短路问题。
解决最短路问题的方法之一就是迪克斯特拉算法。
1.2基本思路假定P：V1→V2→ (V)i→…→Vj→…→Vk是从V1到Vk的最短路，则它的子路Vi →…→Vj一定是从Vi到Vj的最短路。
否则从V1出发沿路p走到Vi，,然后沿Vi 到Vj的最短路走到Vj再沿路P从Vj到Vk，这样得到一条新的从V1出发到Vk的路，其长度小于P，与P是最短路的假设矛盾。
1.3算法设G为所有权都为正数的加权连通简单图。
G带有顶点a=V0, V1, (V)n=z,权W(Vi , Vj) ,若(Vi, Vj)不是G中的边，则W(Vi, Vj) =∞for i=1 to nL((Vi)= ∞L(a)=0S=Ф(初始化标记，a的标记为0，其它结点标记为∞，S 为空集)当z不属于S时beginu=不属于S的L（u）最小的一个顶点S=S∪{u}对所有不属于S的顶点Vif L(u)+W(u,v)<L(v) thenL(v)=L(u)+L(u,v) (这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记)End (L(z)表示从a到z的最短路的长度) 这个算法经过n-1次循环后必定结束，计算量为1/2（n-1）(n-2)，因而是个有效算法。
数模论文之灾情巡视路线（相对优化方案）嘿，各位亲爱的数模爱好者，今天我们来聊聊灾情巡视路线的优化方案。
这个问题可是关系到救援效率和灾民生命安全的头等大事，咱们可得好好研究研究。
先来分析一下现有的巡视路线。
一般来说，现有的路线都是按照行政区域划分，从A点到B点，再到C点，看似合理，但实际上存在很多问题。
比如说，路线过长，导致救援队伍无法在第一时间赶到现场；路线规划不合理，有时候会绕弯路，浪费时间；还有，巡视路线上的重点区域划分不清，容易导致救援资源分配不均。
那怎么办呢？咱们得来个相对优化方案。
下面我就用意识流的方式，给大家详细讲解一下这个方案。
我们要运用图论的知识，对初步的巡视路线进行优化。
具体操作如下：1.将受灾点视为图的节点，受灾点之间的距离视为图的边，建立一张灾情巡视图。
2.运用Dijkstra算法，计算从救援队伍出发点到各个受灾点的最短路径。
3.对最短路径进行排序，优先考虑受灾程度较高的区域。
4.根据道路状况和救援队伍的行动速度，调整路径顺序，使得救援队伍在巡视过程中能够高效地到达各个受灾点。
5.对优化后的巡视路线进行评估，包括救援时间、救援成本、救援效果等方面，确保方案的科学性和实用性。
在这个过程中，我们还要考虑到一些特殊情况。
比如说，有些受灾点因为地形原因，无法直接到达，这时候我们可以采用无人机等先进设备进行巡视。
再比如，有些受灾点之间可能存在交通管制，这时候我们需要及时调整路线，确保救援队伍能够顺利到达。
优化方案有了，就是实施阶段。
我们要与政府部门、救援队伍、志愿者等各方密切配合，确保方案的顺利实施。
具体操作如下：1.制定详细的实施方案，明确各部门的职责和任务。
2.建立一个灾情信息共享平台，实时更新受灾点的受灾情况和救援进度。
3.对救援队伍进行培训，提高他们的救援技能和应对突发事件的能力。
4.加强宣传，提高公众对灾情巡视路线优化方案的认识和支持。
5.定期对方案进行评估和调整，以适应不断变化的灾情和救援需求。
三峡大学12组最优灾情巡视路线摘要本文解决的是灾情巡视路线的最佳安排问题，我们将其转化为多个推销员回路问题，并针对灾情巡视的不同要求，用哈密顿回路法求出了各情况下的近似最优解。
针对问题一：本文采用Kruskal 法求出最小生成树图，然后以最小生成树为依据将该县分为三个区域，分别对应三组巡视人员。
然后利用哈密顿法求解出各组最短的巡视路程，分别为第一组197.6km 、第二组196.8km 、第三组206.8km ，总路程为601.2km 。
最后用本文中自定义的路程均衡度来衡量分组的均衡性，路程均衡度为5.0%，各组的均衡性很好。
针对问题二：本文在解决问题一的基础上，将该县分为四个区域。
然后利用哈密顿法求解出四个区域的最短巡视路程，进而求出巡视时间和停留时间，得到各组的巡视总时间，分别为第一组21.1小时、第二组22.5小时、第三组23.0小时、第四组21.5小时。
其中时间均衡度为8.6%，满足题目要求。
针对问题三：本文分析得出，巡视的最短时间为6.43小时，然后我们根据最短时间并依据最小生成树图将巡视人员分为七组，在新的巡视规则下很好的完成了巡视任务。
各组的巡视路线和停留点时间如下表: 针对问题四：本文在不破坏原来分组均衡性的条件下，讨论了,,T t V 对分组的影响，并得出,,T t V 的最大变化范围。
最后根据得出的结论对分三组的实例进行定量分析，验证了结论的可行性。
组号 巡视路线时间/小时1 2567912141297652O E F H H F E O --------------------6.432 252021181518212025O M K L L K M O ---------------- 5.873 2561913111319652O L J G G J L O ------------------ 6.154 234891098432O D E F F E D O ------------------ 6.385 282726242322171617222324262728O P N N P O -------------------- 6.376 123133341123133341O R A B C O R A B C O -------------------- 5.38 72930323534129303235341O R Q A O R Q A O -------------------- 5.48关键字：哈密顿回路 最小生成树 F l o y d 算法1问题重述下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。
9附录附录一：Kruskal最小树成法程序clear all%图论最小生成树Kruskal避圈算法%w为邻接矩阵w=[0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10.3 5.9 11.2 inf inf inf inf inf inf inf inf inf inf inf 6 inf inf inf ; inf 0 4.8 inf 8.3 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8.2 inf inf inf ;inf 4.8 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.8 8.2 inf inf inf inf inf inf inf inf inf inf inf inf inf inf ;inf inf inf 0 inf inf inf 20.4 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 12.7 inf inf inf inf inf inf inf inf inf inf inf inf inf inf ; inf 8.3 inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 11.3 inf inf inf inf inf inf inf inf 11.4 inf inf inf inf inf ; inf inf inf inf 9.7 0 7.3 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 11.8 9.5 inf inf inf inf inf ; inf inf inf inf inf 7.3 0 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 15.1 7.2 inf inf inf inf inf inf 14.5 inf inf inf inf inf inf ; inf inf inf 20.4 inf inf inf 0 inf inf inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf 8 inf inf infinf inf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf 0 inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf 7.8 5.6 inf inf infinf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf 0 infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf 10.8 inf infinf inf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf 14.2 inf 6.8 infinf 13.2 inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf inf0 inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf 12.2 7.8 10.2 inf inf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf 0 8.6 inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf 8.8 inf 16.4 9.8 inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf 8.6 0 15 inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf 9.9 infinf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf 15 0 inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf 8.8inf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf 0 6.8 inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf 11.8 inf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf 6.8 0 inf inf inf inf 6.7inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf 9.8 inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf 0 inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf 8.28.2 9.2 inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf 0 9.3 inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf inf8.1 inf 7.2 inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf 9.3 0 7.9 infinf inf 6.5 inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf 5.5 inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf 7.9 0 inf9.1 inf 7.8 inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf 4.1 inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf 6.7 inf inf inf inf 0 10 inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf inf 10.1 inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf 9.1 100 8.9 inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf 7.9 inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf8.9 0 inf inf 18.8 inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf 13.2 inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf 6.5 7.8 infinf inf 0 inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf 12 8.8 inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf 0 7.8 inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf 10.5 inf 10.5 infinf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf 18.8 inf 7.8 0 7.9 inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf 7.9 0 inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf 12.1 8.3 inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf 0 inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf 15.2 7.2 7.8 ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf 0 inf inf 10.3 inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf 7.7 inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf 0 8.1 7.3inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf 9.2 ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf 8.1 0 19 inf 14.9 inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf 10.3 7.3 190 inf inf 7.4 inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf inf0 8.2 11.5 17.8 inf inf inf inf infinf inf inf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf 14.9 inf 8.2 0 inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf ;10.3 inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf inf7.4 11.5 inf 0 inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf 8.8 ;5.9 inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf inf 17.8 inf inf 0 11 inf inf inf inf infinf inf inf inf inf inf inf inf inf inf ;11.2 inf 7.8 inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf 11 0 inf inf inf inf infinf inf inf inf inf inf 11.5 inf inf inf ;inf inf 8.2 12.7 11.3 inf 15.1 infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf 0 inf infinf inf inf inf inf inf inf inf inf inf infinf ;inf inf inf inf inf inf 7.2 8 7.8 inf 14.2 inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf 0 inf inf inf infinf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf 5.6 10.8 inf 12.2 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf 0 infinf inf inf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf 6.87.8 8.8 inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf 0 inf infinf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf inf 10.2 inf 9.9 inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf 16.4 inf inf 11.8 inf 8.2 inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf 0 inf inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf 13.2 inf 9.8 inf inf inf inf 8.2 8.1 inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf inf0 inf inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf 9.8 9.2 inf inf 4.1 10.1 inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf 0 inf inf inf inf inf inf inf ;inf inf inf inf inf 11.8 14.5 inf infinf inf inf inf inf 8.8 inf inf inf 7.2 5.5inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf 0 inf inf inf inf inf inf ;inf inf inf inf 11.4 9.5 inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf 12 inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf 0 14.2 19.8 inf infinf ;inf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf inf inf inf inf inf inf7.9 13.2 8.8 10.5 inf inf inf inf infinf inf inf inf inf inf inf inf inf inf infinf inf inf inf inf 14.2 0 inf inf infinf ;6 8.2 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 11.5 inf inf inf inf inf inf inf inf inf 19.8 inf 0 10.1 inf 12.8 ;inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10.5 inf 12.1 15.2 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10.1 0 inf inf ;inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 8.3 7.2 7.7 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 inf ;inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7.8 inf 9.2 inf inf inf inf 8.8 inf inf inf inf inf inf inf inf inf inf inf inf inf 12.8 inf inf 0 ;];n=53;%有53个点k=1;for i=1:n-1for j=i+1:nif w(i,j)~=infx(1,k)=w(i,j);%记录边x(2,k)=i;%记录起点x(3,k)=j;%记录终点k=k+1;endendendk=k-1;%统计边数 k为边数%步骤一%冒泡法给边的大小排序for i=1:kfor j=i+1:kif x(1,i)>x(1,j)a=x(1,i);x(1,i)=x(1,j);x(1,j)=a;a=x(2,i);x(2,i)=x(2,j);x(2,j)=a;a=x(3,i);x(3,i)=x(3,j);x(3,j)=a;endendend%给各点标号赋初值for i=1:nl(i)=i;end%初始时选e1加入集合EE(1,1)=x(1,1); %E矩阵的第一行记录最小生成树的边长E(2,1)=x(2,1); %E矩阵的第二行记录边的起点E(3,1)=x(3,1); %E矩阵的第三行记录边的终点a=min([l(E(2,1)),l(E(3,1))]);l(E(2,1))=a;l(E(3,1))=a;b=1;%记录E中边数for i=2:k%步骤四if b==n-1 %如果树中边数达到n-1break%算法终止end%步骤二if l(x(2,i))~=l(x(3,i)) %如果两顶点标号不同b=b+1; %将这条边加入EE(1,b)=x(1,i);E(2,b)=x(2,i);E(3,b)=x(3,i);%步骤三for j=1:n %对于所有顶点if l(j)==max([l(E(2,b)),l(E(3,b))])%如果该顶点的标号,等于=,新加入边中的顶点标号较大的值l(j)=min([l(E(2,b)),l(E(3,b))]);%将其改为较小的那一个以避圈endendendendE附录二：问题一的求解程序1、计算强加权矩阵程序%floyd 算法通用程序，输入a为赋权邻接矩阵%输出为距离矩阵D，和最短路径矩阵pathfunction [D,path]=floyd(a)a=[0 inf inf inf inf inf inf inf inf inf inf inf inf 10.3 5.9 inf 6 inf inf inf ; inf 0 8.9 inf inf inf inf inf inf inf inf inf inf inf inf 7.9 inf inf inf inf ;inf 8.9 0 inf 18.8 inf inf inf inf inf inf inf inf inf inf 13.2 inf inf inf inf ; inf inf inf 0 7.8 inf inf inf inf inf inf inf inf inf inf 10.5 inf 10.5 inf inf ;inf inf 18.8 7.8 0 7.9 inf inf inf inf inf inf inf inf inf inf inf inf inf inf ;inf inf inf inf 7.9 0 inf inf inf inf infinf inf inf inf inf inf 12.1 8.3 inf ;inf inf inf inf inf inf 0 inf inf inf infinf inf inf inf inf inf 15.2 7.2 7.8 ;inf inf inf inf inf inf inf 0 inf 10.3 inf inf inf inf inf inf inf inf 7.7 inf ;inf inf inf inf inf inf inf inf 0 8.1 7.3inf inf inf inf inf inf inf inf 9.2 ;inf inf inf inf inf inf inf 10.3 8.1 0 19 inf 14.9 inf inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf 7.3 19 0inf 20.3 7.4 inf inf inf inf inf inf ;inf inf inf inf inf inf inf inf inf inf inf0 8.2 11.5 17.8 inf inf inf infinf ;inf inf inf inf inf inf inf inf inf 14.9 20.3 8.2 0 inf inf inf inf inf inf inf ; 10.3 inf inf inf inf inf inf inf inf inf7.4 11.5 inf 0 inf inf inf inf inf 8.8 ;5.9 inf inf inf inf inf inf inf inf inf inf 17.8 inf inf 0 inf inf inf inf inf ;inf 7.9 13.2 10.5 inf inf inf inf inf inf inf inf inf inf inf 0 inf inf inf inf ;6 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 0 10.1 inf 12.8 ;inf inf inf 10.5 inf 12.1 15.2 inf inf inf inf inf inf inf inf inf 10.1 0 inf inf ;inf inf inf inf inf 8.3 7.2 7.7 inf inf inf inf inf inf inf inf inf inf 0 inf ;inf inf inf inf inf inf 7.8 inf 9.2 inf inf inf inf 8.8 inf inf 12.8 inf inf 0 ;];n=size(a,1);D=a;path=zeros(n,n);for i=1:nfor j=1:nif D(i,j)~=infpath(i,j)=j;endendendfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendend2、第1组巡视最短路线程序（第2，3组只变换数据）。
1 符号说明i 用于表示地点 i=0表示县政府 1<= i <=35表示村 36<=i<=52表示乡 v 表示i 从1到52构成的点的集合2、模型的建立与分析经过图G 每一个顶点一次的圈称为哈米尔顿圈或H 圈，，其中全最小的哈密尔顿圈成为最佳H 圈，完备图一定存在最佳H 圈，寻找最佳H 圈的方法是有给定的图G=（V ,E ）构造一个以V 为顶点集的完备图G1=（V ,E1）,E 的每一条边（x,y ）的权等于 x 与y 在图中最短路的权，根据以上结论，将所给的图转化为满足任意两点之间最短路寻找最佳H 圈的方法有很多，它的准确解法有穷举法和动态规划法，此次模型我们采用近似的方法，两边逐次修正法，根据该算法我们求出完备图的邻接矩阵，任给图中的一组顶点，我们都可以求出它的最佳推销员路径，即经过这些顶点至少一次且权值最小。
问题一 若分为3组巡视，设计总路程最短且各组尽可能均衡的巡视路线.此问题是多个推销员的最佳推销员回路问题.即在加权图G 中求顶点集V 的划分12,,,n V V V ，将G 分成n 个生成子图[][][]12,,...,n G V G V G V ，使得（1）顶点i V O ∈, i=1，2，3,…,n ；（2）()G V V ni i== 1 ；（3）()()(),max max i j i ji iC C C ωωαω-≤，其中i C 为i V 的导出子图[]i V G 中的最佳推销员回路，()i C ω为i C 的权，i ，j=1，2，3,…,n ；（4）()1nii C ω=∑取最小.定义 称()()(),0max max i j i ji iC C C ωωαω-=为该分组的实际均衡度.α为最大容许均衡度.显然100≤≤α，0α越小，说明分组的均衡性越好.取定一个α后，0α与α满足条件（3）的分组是一个均衡分组.条件（4）表示总巡视路线最短.此问题包含两方面的的内容：第一，顶点的分组；第二，每组中要求最佳推销回路，即三组能保持一定的均衡度。
