数学建模图论国赛辅导

1、图论及其应用图论及其应用2015 . 8主要内容主要内容 1、欧拉回路和中国邮递员问题、欧拉回路和中国邮递员问题 2、哈密顿环球旅行、哈密顿环球旅行问题问题 3 3、竞赛题选讲、竞赛题选讲 - -灾情巡视路线灾情巡视路线(CUMCM 1998 B题题)环：起点和终点重合的边。环：起点和终点重合的边。重边：两顶点之间连两条或两条以上的边。重边：两顶点之间连两条或两条以上的边。简单图：无环且无重边的图。简单图：无环且无重边的图。完全图：任意两顶之间都联边。完全图：任意两顶之间都联边。 子图：子图：G(V,E), G1(V1,E1); V1 V, E1 E, 则则G1是是G的子图。的子图。 生成子图

2、：若生成子图：若H G，且且V(H)=V(G)，则则H是是G的生成子图。的生成子图。 导出子图：若导出子图：若H G，且且V(H)=V ，E(H)由由E(G)中顶都在中顶都在V 中的边构成；中的边构成；则则H是是G的导出子图。的导出子图。v1v2v3v4v6v5v1v2v3v4v1v2v3v4v6v5v1v2v3v4abcd树树：无圈、无环的连通图。：无圈、无环的连通图。最小生成树最小生成树 由树的定义知道由树的定义知道, 任意一个连通的任意一个连通的p, q图图(p个顶点个顶点q条边条边)G适当去掉适当去掉q - - p +1条边后条边后, 都可以都可以变成树变成树, 这棵树称为图这棵树称为

3、图G的的生成树生成树. 设设T是图是图G的一棵生成树的一棵生成树, F(T)表示树表示树T中所有中所有边的权数之和边的权数之和, F(T)称为称为树树T的权的权. 一个连通图一个连通图G的生成树一般不止一棵的生成树一般不止一棵, 图图G的的所有生成树中权数最小的生成树称为图所有生成树中权数最小的生成树称为图G的的最小最小生成树生成树. 欲修连接欲修连接n个城市的铁路，已知任意两市间铁个城市的铁路，已知任意两市间铁路造价，试设计总造价最低的线路路造价，试设计总造价最低的线路(在加权完全在加权完全图上求最小生成树图上求最小生成树Kruskal算法算法)。 顶点割顶点割：G是连通图，是连通图，VV(

4、G), GV 不连通。不连通。则集合则集合V 称为称为顶点割顶点割。含。含顶最少的顶点割为顶最少的顶点割为最小顶最小顶点割点割。最小顶点割中所含。最小顶点割中所含顶的个数为图顶的个数为图G的的连通度连通度。 割点割点：G是是连通图，连通图，v V, Gv 不连通，不连通，则称顶则称顶v为割点。为割点。图的最小度图的最小度 min d(v)v G图的最大度图的最大度 max d(v)v G图中的参数图中的参数：顶点顶点v的度：与顶点的度：与顶点v相联的边数。即为相联的边数。即为d(v).一个图的割点一个图的割点有三条割边的图有三条割边的图 图的边连通度图的边连通度：G是是连通图，连通图，EE(G

5、), GE 不连通。则集合不连通。则集合E 称为称为G的的边边割集割集。含边最少的边。含边最少的边割集中所含边数为图割集中所含边数为图G的的边连通度边连通度。当边割集中仅含一条边时，此边称为当边割集中仅含一条边时，此边称为桥桥。可靠通讯网络的构造可靠通讯网络的构造: :某图表示一个通讯网络，某图表示一个通讯网络，那么通讯站那么通讯站( (或通讯线路或通讯线路) )的最少数目就是图的连的最少数目就是图的连通度通度( (或边连通度或边连通度) )：它们的失灵势必危及系统的：它们的失灵势必危及系统的通讯。连通度和边连通度越高，网络就越可靠。通讯。连通度和边连通度越高，网络就越可靠。 匹配：匹配：M

6、E, M中任意两边无公共端点，中任意两边无公共端点，则则M为为G的一个的一个匹配匹配。M中一条边之两个顶叫中一条边之两个顶叫在在M之下相配。之下相配。M中每个顶称为被中每个顶称为被M许配许配。若若G中所有顶均被中所有顶均被M许配，则称许配，则称M为为完备匹配完备匹配。含边最多的匹配为含边最多的匹配为最大匹配最大匹配。红线为一最大匹配红线为一最大匹配红线为一完备匹配红线为一完备匹配ABCD哥尼斯堡七桥示意图哥尼斯堡七桥示意图问题问题( (哥尼斯堡七桥哥尼斯堡七桥问题问题):):能否从任一陆能否从任一陆地出发通过每座桥恰地出发通过每座桥恰好一次回到出发点？好一次回到出发点？ 图中含每条边的迹叫图中

7、含每条边的迹叫Euler迹。闭的迹。闭的Euler迹叫迹叫Euler回路。含回路。含Euler回路的图叫回路的图叫Euler图。图。ABDC七桥问题模拟图七桥问题模拟图欧拉指出：如果每块陆地所欧拉指出：如果每块陆地所连接的桥都是偶数座，则从连接的桥都是偶数座，则从任一陆地出发，必能通过每任一陆地出发，必能通过每座桥恰好一次而回到出发地座桥恰好一次而回到出发地. . 欧拉回路和中国邮递员问题 中国邮递员问题(Chinese Postman Problem, CPP)由我国管梅谷教授于1962年首先提出并发表的 问题是从邮局出发，走遍邮区的所有街道至少一次再回到邮局，走什么路由才能使总的路程最短？

8、 如果街区图是一个偶图，根据定理 3，一定有欧拉回路，CPP 问题也就迎刃而解了 若街区图不是偶图，则必然有一些街道要被重复走过才能回到原出发点 显然要在奇次点间加重复边 如何使所加的边长度最少 归结为求奇次点间的最小 匹配( minimum weighted match) 由Edmons 给出 多项式算法(1965)ABCD中国邮递员问题中国邮递员问题- -定义定义 邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线这就是中中国国邮邮递递员员问问题题. 若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则

9、一个投递区构成一个赋权连通无向图中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为最最佳佳巡巡回回中国邮递员问题中国邮递员问题- -算法算法 1、G是是欧欧拉拉图图 此时 G 的任何一个欧拉巡回便是最佳巡回问题归结为在欧拉图中确定一个欧拉巡回Fleury算算法法：求欧拉图的欧拉巡回 Fleury算法算法-基本思想：从任一点出发，每当访问基本思想：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不只一条边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的一条，则应选一条不是未访问的边集的导出子图的割边割边作为访问边，直到没有

10、边可选择为止作为访问边，直到没有边可选择为止.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10Fleury 算算法法 算算法法步步骤骤 ：（）任选 一个顶点 v0，令道路 w0=v0（）假定 道路 wi=v0e1v1e2eivi已经选好，则从 Ee1,e2, ,ei中选一条边 ei+1，使： a）ei+1与 vi相关联b）除非不能 选择，否 则一定要 使 ei+1不是 Gi=GE-e1,e2, ,ei的割边（）第（ ）步不 能进行时 就停止2、 G 不不是是欧欧拉拉图图 若若G不是欧拉图，则不是欧拉图，则G的任何一个巡回的任何一个巡回经过某些边必定多于一次经过某些边必定多

11、于一次 解决这类问题的一般方法是，在一些点对之间解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小权的总和为最小情情形形G正正好好有有两两个个奇奇次次顶顶点点（）用Dijkstra 算法求出奇次顶点u 与v 之间的最短路径P（）令 G*=GP，则 G*为欧拉图（）用Fleury 算法求出 G*的欧拉巡回，这就是 G的最佳巡回V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9情情形形G 有有n个个奇奇次次

12、顶顶点点（n）Edmonds 最最 小小对对集集算算法法：基 本 思 想 ： 先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小再沿点对之间的最短路径添加重复边得欧拉图 G*，G*的欧拉巡回便是原图的最佳巡回算算 法法 步步 骤骤 ：（）用 Floyd 算法求出的所有奇次顶点之间的最短路径和距离（）以 G 的所有奇次顶点为顶点集（个数为偶数） ，作一完备图，边上的权为两端点在原图 G 中的最短距离，将此完备加权图记为 G1（）在 G 中沿配对顶点之间的最短路径添加重复边得欧拉图 G*（）用Fleury 算法求出 G*的欧拉巡回，这就是 G的最佳巡回（）求出（）求出G1的最小权理想匹配的最小

13、权理想匹配M，得到奇次顶点的最佳配对，得到奇次顶点的最佳配对例例求右图所示投递区的一条最佳邮递路线1图中有 v4、v7、v8、v9四个奇次顶点用Floyd算法求出它们之间的最短路径和距离：3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv2以v4、v7、v8、v9为顶点，它们之间的距离为边权构造完备图G13求出 G1的最小权完美匹配 M=(v4,v7),(v8,v9)4在 G 中沿 v4到 v7的最短路径添

14、加重复边，沿 v8到 v9的最短路径 v8v9添加重复边，得欧拉图 G2G2中一条欧拉巡回就是 G 的一条最佳巡回其权值为返回返回 解中国邮递员问题的步骤0、将图中的所有悬挂点依次摘去1、求所有奇次点间的最短距离和最短路径2、根据奇次点间的最短距离求最小完全匹配3、根据最小完全匹配和最短路径添加重复边4、将悬挂点逐一恢复，并加重复边5、根据得到的偶图，给出欧拉回路的若干种走法1324598760554344426621324598765543444266 解中国邮递员问题的步骤1595543444266212459608746230387添添加加重重复复边边找找出出所所有有基基本本回回路路 哈

15、密顿环球旅行哈密顿环球旅行问题问题: : 十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，个城市，能否从某个城市出发在十二面体上依次经过每个能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏） 含一切顶的规叫含一切顶的规叫Hamilton规。规。 闭的闭的Hamilton规为规为Hamilton圈。圈。 哈密尔顿回路及推销员问题哈密尔顿回路及推销员问题 哈密尔顿回路哈密尔顿回路( Hamiltonian circuit)连通图连通图G(V,E)中的回路称为中的回路称为哈密尔

16、顿回路哈密尔顿回路，若，若该回路包括图中所有的点。显然哈密尔顿回该回路包括图中所有的点。显然哈密尔顿回路有且只有路有且只有 n 条边，若条边，若|V|=n连通图具有哈密尔顿回路的充分必要条件是什连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是么？这个问题是由爱尔兰数学家由爱尔兰数学家哈密尔顿哈密尔顿1859年年提出的，但至今仍未解决提出的，但至今仍未解决.欧拉回路是对边进行访问的问题，哈密尔顿回欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访问的问题路是对点进行访问的问题搜索哈密尔顿回路的难度是搜索哈密尔顿回路的难度是 NP-complete任两点间都有边的图为任两点间都有边的图为

17、完全图完全图, 完全图中有完全图中有(n-1)!/2条不同的哈密尔顿回路条不同的哈密尔顿回路, 有有(n-1)/2个边个边不相交的哈密尔顿回路不相交的哈密尔顿回路.哈密尔顿路径哈密尔顿路径：包含图中所有点的路径：包含图中所有点的路径. 推销员问题推销员问题(TSP)：设：设v1, v2, .,vn 为为 n 个城市，个城市，城市之间的路程已知，推销员从城市之间的路程已知，推销员从 v1出发，走遍所出发，走遍所有城市一次且仅一次回到有城市一次且仅一次回到v1，并使总旅程最短，并使总旅程最短.不允许点重复的推销员问题就是最小哈密尔顿回路问题不允许点重复的推销员问题就是最小哈密尔顿回路问题一般推销员

18、问题一般推销员问题( (GTSPGTSP) )：允许点重复的：允许点重复的TSPTSP当网路边权满足三角不等式时，一般推销员问题等价于当网路边权满足三角不等式时，一般推销员问题等价于最小哈密尔顿回路问题最小哈密尔顿回路问题网路边权不满足三角不等式时，用两点间最短路的距离网路边权不满足三角不等式时，用两点间最短路的距离代替原来边权，就可满足三角不等式，在此基础上求最小代替原来边权，就可满足三角不等式，在此基础上求最小哈密尔顿回路哈密尔顿回路 G是有向图，把是有向图，把G各边方向去掉所得无向图各边方向去掉所得无向图叫叫G的底图；若的底图；若G的底图是连通图，则称的底图是连通图，则称G是是弱连弱连通

19、有向图通有向图；在有向图；在有向图G中，中，u,v V(G), 且且G 中存在中存在有向轨有向轨P(u,v)，则称则称u可到达可到达v，每对顶都连边的有向图为每对顶都连边的有向图为竞赛图竞赛图。竞赛图必有竞赛图必有Hamilton轨。轨。一台机器完成一台机器完成n项工作，项工作，i工作工作j工作的机器调工作的机器调整时间为整时间为tij试安排试安排n项工作，使项工作，使 tijmin ;(有有向图上求向图上求Hamilton轨轨)哈哈 密密 尔尔 顿顿 图图定义定义设 G=(V,E)是连通无向图（） 经过 G 的每个顶点正好一次的路径，称为 G 的一条 哈密尔顿路径哈密尔顿路径（）（） 经过

20、G 的每个顶点正好一次的圈，称为 G 的哈密尔哈密尔 顿圈顿圈或 H 圈（）含 H 圈的图称为哈密尔顿图哈密尔顿图或 H 图返回返回推销员问题推销员问题- -定义定义 流动推销员需要访问某地区的所有城镇，流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题总行程最小这就是推销员问题 若用顶点表示城镇，边表示连接两城若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的

21、最短闭寻找一条经过每个顶点至少一次的最短闭通路问题通路问题定义在加权图定义在加权图G=(V,E)中，中，（）权最小的哈密尔顿圈称为最佳（）权最小的哈密尔顿圈称为最佳H圈圈（）经过每个顶点至少一次的权最小的闭（）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路通路称为最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈哈密尔顿圈H回路，长回路，长22最佳推销员回路，最佳推销员回路，长长4定定理理在加权图G=(V,E)中，若对任意 x,y,zV，zx,zy,都

22、有 w(x,y)w(x,z)+w(z,y)，则图 G 的最佳 H 圈也是最佳推销员回路最佳推销员回路问题可转化为最佳 H 圈问题方法是由给定的图 G=(V,E)构造一个以 V 为顶点集的完备图 G=(V,E)，E的每条边(x,y)的权等于顶点 x 与 y 在图中最短路的权即：x,yE w(x,y)=mindG(x,y)定定理理加权图 G的最佳推销员回路的权与 G的最佳 H 圈的权相同推销员问题近似算法：推销员问题近似算法：二边逐次修正法：二边逐次修正法：（）任取初始H 圈: C0=v1,v2,vi, ,vj,vn,v1（）对所有的 i ,j，1i+1jn,若w(vi, vj)+w(vi+1,v

23、j+1)w(vi,vi+1)+w(vj,vj+1)则在 C0中删去边(vi,vi+1)和(vj,vj+1)而加入边(vi, vj)和(vi+1,vj+1)，形成新的 H 圈 C，即C= v1,v2,vi,vj , vj-1, ,vi+1,vj+1, ,vn,v1）对 C 重复步骤（） ，直到条件不满足为止，最后得到的 C 即为所求例对以下完备图，用二边逐次修正法求较优例对以下完备图，用二边逐次修正法求较优H圈圈返回返回灾情巡视路线灾情巡视路线(CUMCM 1998 B题题) 今年夏天该县遭受水灾。为考察灾情、组织今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定带领有关部门负责人到全县自救

24、，县领导决定带领有关部门负责人到全县各乡各乡(镇镇)、村巡视。巡视路线从县政府所在地出、村巡视。巡视路线从县政府所在地出发，走遍各乡发，走遍各乡(镇镇)、村，又回到县政府所在地。、村，又回到县政府所在地。 1.若分若分3组组(路路)巡视，试设计总路线最短且巡视，试设计总路线最短且各组尽可能均衡的巡视路线。各组尽可能均衡的巡视路线。 2.假设巡视人员在各乡假设巡视人员在各乡(镇镇)停留停留2小时，在小时，在各村停留各村停留1小时，汽车速度小时，汽车速度35公里公里/小时。要在小时。要在24小时内完成巡视至少分几组？给出这种分组小时内完成巡视至少分几组？给出这种分组下你认为最佳的巡视路线。下你认为

25、最佳的巡视路线。A B C D E F G HRPMQ29313230NJLL2018K21图例：图例：北北县政府所县政府所在地在地乡政府所乡政府所在地在地村村 3. 在上述关于在上述关于T、t、和和V的假设下，如果巡的假设下，如果巡视人员足够多，完成巡视的最短时间是多少？视人员足够多，完成巡视的最短时间是多少？给出这种最短时间完成巡视的要求下，你认为给出这种最短时间完成巡视的要求下，你认为最佳的巡视路线。最佳的巡视路线。 4. 若巡视组数已定若巡视组数已定(比如比如3组组)，要求尽快完成，要求尽快完成巡视，讨论巡视，讨论T、t、V改变对最佳路线的影响。改变对最佳路线的影响。最佳灾情巡视路线的

26、数学模型最佳灾情巡视路线的数学模型杨庭栋杨庭栋 李晓涛李晓涛 郑长江郑长江解放军后勤工学院解放军后勤工学院一一. 问题重述问题重述(略略)二二. 模型假设与符号说明模型假设与符号说明(略略)三三. 模型的建立与分析模型的建立与分析 问题要求在县、乡、村公路网中，寻找从县出发问题要求在县、乡、村公路网中，寻找从县出发走遍各乡、村，返回县的最短路程或最小时间。走遍各乡、村，返回县的最短路程或最小时间。 把县、乡、村看作点把县、乡、村看作点，乡与村之间的，乡与村之间的公路公路看作看作边，边，距离看作距离看作对应边上的对应边上的权权。问题就转化成在加。问题就转化成在加权有向图从给定点权有向图从给定点O

27、出发，历遍各点回到出发，历遍各点回到O，使使总总权和最小权和最小。为方便，先给出图论中一些相关定义。为方便，先给出图论中一些相关定义。 定义定义1：经过图：经过图G每个顶点各一次的圈，每个顶点各一次的圈，称为称为哈米尔顿圈哈米尔顿圈，简称，简称H圈。圈。定义定义2：在加权图：在加权图G=(V, E)中中(1). 权和最小的权和最小的H圈称为圈称为最佳最佳H圈圈。 (2). 经过每个顶点至少一次且权和最小经过每个顶点至少一次且权和最小的通路称为的通路称为最佳推销员回路最佳推销员回路。 最佳推销员回路可转化成最佳最佳推销员回路可转化成最佳H圈求圈求。 方法是：以图方法是：以图G的顶点集的顶点集构造

28、完备图构造完备图G (V,E ), E 中每条边中每条边(x,y)的权为顶点的权为顶点x与与y在图在图G中最短中最短路线。则：路线。则：定理定理1：图图G中最佳推销员回路与中最佳推销员回路与G 中最佳中最佳H圈圈相同。相同。定理定理2：加权有向图中求最佳：加权有向图中求最佳H圈是圈是NP完备完备问题。问题。下面采用近似算法求此问题一个近似最优解。下面采用近似算法求此问题一个近似最优解。本问题就是求图本问题就是求图G的最佳推销员回路。的最佳推销员回路。算法算法1：(求图求图G的最佳推销员回路的最佳推销员回路) 1. 用用Dijkstra算法求出图算法求出图G中中任意两顶点任意两顶点之间的最短路。

29、之间的最短路。构造完备图构造完备图G (V,E )。2.输入图输入图G 一个初始一个初始H圈。圈。3. 用对角线完全算法产生一个初始用对角线完全算法产生一个初始H圈。圈。 4. 随机输入随机输入G 一个一个H圈，圈，(例如例如2000个个)； 5.对第对第2、3、4步所得每个步所得每个H圈，用改良圈圈，用改良圈法求一个近似最佳法求一个近似最佳H圈。圈。 问题问题1：分分3组巡视，设计总路线最短且各组组巡视，设计总路线最短且各组尽可能均衡的路线。尽可能均衡的路线。求图求图G顶点集顶点集V的一个划分的一个划分V1，V2， Vn。 6. 取第五步求出所有取第五步求出所有H圈中，权和最小者圈中，权和最

30、小者为近似解。为近似解。 将将G分成分成n个生成子图个生成子图GV1, GV2, , GVn。使得：使得：(1). 顶点顶点O G(Vi)； i=1,2,n. (2). U Vi = V(G)n i =1aCCCiijiji)(max)()(max,(3).其中其中Ci为为G(Vi)导出导出子图中的最佳子图中的最佳H圈，圈， (Ci)为为Ci的权。的权。(4). (Ci)=minn i =1 定义定义3.称称:a0= 为该分组实为该分组实际路线的均衡度。际路线的均衡度。a为最大允许度。为最大允许度。)(max)()(max,iijijiCCC 求求V的一个划分：求的一个划分：求O到其余各点的最

31、短路，到其余各点的最短路，这些路构成一棵树，如图这些路构成一棵树，如图(1): 由经验知，分组应由经验知，分组应遵从以下准则：遵从以下准则： (1).同一干支同一干支上的点尽量分在上的点尽量分在一组。一组。 (2).应将相邻干应将相邻干支的点分在一组。支的点分在一组。(3). 尽量将长干支尽量将长干支与短干支分在一组。与短干支分在一组。按以上准则找按以上准则找到两种分组形式：到两种分组形式：OCBRQA1 165PN4MK3LEFH2图图 1分组分组1:(,) (,) (,)分组分组2:(,) (,) (,)不均不均衡舍衡舍去去! 就分组就分组2中每组顶点的生成子图，用算法中每组顶点的生成子图

32、，用算法1求尽量包含图求尽量包含图1中树上边的近似最佳解。中树上边的近似最佳解。该分组均衡度：该分组均衡度：a0=54.2%表表1 分组分组2的近似最优解的近似最优解小组小组名称名称路路 线线总路总路线长线长路线路线总长总长O-P-28_27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-OO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-8-4-D-3-C-OO-R-29-Q-30-32-31-33-35-34-A-B-1-O191.1241.9125.5558.5均衡均衡性很差性很差 为改善均衡性，将第为改善均衡性，

33、将第组中顶点组中顶点C、2、3、D、 4归入第归入第组。重新求得近似最优解，如表组。重新求得近似最优解，如表2。表表2 分组分组3的近似最优解的近似最优解小组小组名称名称路路 线线总路总路线长线长路线路线总长总长 O-P-2827-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-OO-2-5-6-7-E-8-E-9-F-10-F-12-H-14-13-G-11-J-19-L-6-5-2-OO-R-29-Q-30-32-31-33-35-34-A-1-B-C-3-D-4-D-3-2-O191.1216.4192.3599.8该分组均衡度：该分组均衡度：a0=

34、11.69%改善了改善了均衡度均衡度最优巡视路线见图最优巡视路线见图2。用算法用算法1算出整个网络的近似算出整个网络的近似最佳推销员回路：最佳推销员回路：O-C-3-2-5-D-4-8-E-9-F-10-F-12-H-12-G-11-J-19-L-7-6-M-N-25-20-21-K-18-J-13-14-15-I-16-17-22-23-24-27-26-P-28-Q-30-Q-29-R-31-33-31-32-35-34-A-B-O 总路线长为总路线长为588.6公里。公里。可以认为表可以认为表2所示结果近似最优。所示结果近似最优。 问题问题2：当巡视人员在乡、村停留时间一定，当巡视人员在

35、乡、村停留时间一定，汽车速度一定，且在汽车速度一定，且在24小时内巡视完，至少分小时内巡视完，至少分OC BARPNIKMDLJGHFE图图2. 分为分为3组时各组的巡视路线组时各组的巡视路线Q几组及最佳巡视路线。几组及最佳巡视路线。 T2小时小时，t=1小时，小时，V=35公里公里/小时，小时，乡镇共乡镇共17个，村共个，村共35个。假设分个。假设分4组计算：组计算：乡镇总停留时间为：乡镇总停留时间为：1723569小时小时 24小时巡视完至少分小时巡视完至少分4组组。69/417.25小时，小时，2417.256.75小时小时分分4组时路线总长不会比组时路线总长不会比599.8大太多。大太

36、多。599.8/35/4=4.25(小时小时) 6.75(小时小时)分分4组的分组原则：组的分组原则：准则一、二、三同上准则一、二、三同上。准则四：尽量使各组停留时间相同准则四：尽量使各组停留时间相同。 按以上准则分按以上准则分4组，再用算法组，再用算法1求出近似求出近似最优解，得：最优解，得：表表3 分组分组4的近似最优解的近似最优解(单位：公里单位：公里)小组小组名称名称路路 线线行走行走时间时间路线路线总长总长O-2-5-6-7-E-8-E-11-G-12-H-12-F-10-F-9-E-7-6-5-2-OO-R-29-Q-30-Q-28-27-26-N-24-23-22-17-16-K

37、-22-23-N-26-P-OO-M-25-20-21-K-18-I-15-14-13-J-19-L-6-M-O199.2 16 5.69 21.69 159.1 18 4.54 22.54O-R-A-33-31-32-35-34-B-1-C-D-4-D-3-2-O195.8 17 5.59 22.59166 18 4.74 22.74停留停留时间时间 总总 时间时间该分组均衡度：该分组均衡度：a0=4.62%OC BARPNIKMDLJGHFE图图3. 分为分为4组时各组的巡视路线组时各组的巡视路线Q 注注:兰点前面已停留此次只过不停留，上加线点只过不停留。兰点前面已停留此次只过不停留，上加

38、线点只过不停留。 问题问题3:在在T、t、V假定下，假定下，巡视人员足够巡视人员足够多完成巡视任多完成巡视任务的最短时间务的最短时间为多少？并给为多少？并给出最佳路线。出最佳路线。 经计算知经计算知O到到H的最短时间是所有最短时间的最短时间是所有最短时间中最长者，其距离为中最长者，其距离为77.5公里。所需时间为：公里。所需时间为：tH=277.5/3526.43小时小时在最短时间限下完成巡视的最优路线应满足：在最短时间限下完成巡视的最优路线应满足：(1)每个巡视组总时间不超过每个巡视组总时间不超过6.43小时；小时；(2)所有点必须访问到，不得遗漏。所有点必须访问到，不得遗漏。(3)巡视组要

39、尽量少。巡视组要尽量少。寻找最优路线从距寻找最优路线从距O较远点开始。步骤如下：较远点开始。步骤如下：第一步：由图第一步：由图1算出算出O到每个点的最短距离。到每个点的最短距离。 第二步：找出最远一点，计算第二步：找出最远一点，计算O沿最短路沿最短路线巡视最短时间线巡视最短时间ti，并求并求 t= tH ti第三步：若第三步：若t1，则在余下的点中选一距则在余下的点中选一距O最远者，最远者，根据条件看这一组能否巡视这一点。根据条件看这一组能否巡视这一点。第四步：若能巡视则计算第四步：若能巡视则计算 t，转第三步。转第三步。第五步：若不能，依次找次远点，第第五步：若不能，依次找次远点，第3远点远

40、点满足总巡视时间不超过满足总巡视时间不超过tH ，就让这组巡视这，就让这组巡视这一点，直到一点，直到t0时：时： 要保证原均衡分组不变，则：要保证原均衡分组不变，则：max T SiSjVXiXj 0 (YiYj)tXiXjmax SiSjVXiXj 0 (YiYj)tXiXj(3)2.当当YiYj0时：时： 要保证原均衡分组不变，则：要保证原均衡分组不变，则：max T SiSjVXiXj 0 (XiXj)tYiYjmax SiSjVXiXj 0 (XiXj)tYiYj3.当当SiSj0时：由时：由(2)得得. 0 (XjXi)T+(YjYi)t 时：时： (XiXj)T+(YiYj)t SiSjV max (5)SiSj 0. (XjXi)T+(YjYi)t 时：时：(4) (XiXj)T(YiYj)t SiSj max V SiSj 0(XjXi)T+(YjYi)t SiSj max (6)SiSj 0(二二). 分三组的实例讨论分三组的实例讨论问题问题1所得的所得的3组，当组，当TT02小时小时，t=t0=1小时，小时，VV035公里公里/小时；结果如表小时；结果如表5：编号编号 Xi Yi Si 行驶时间行驶时间 总时间总时间 5 13 1