当前位置：文档之家 › 案例：最佳灾情巡视路线页PPT文档

案例：最佳灾情巡视路线页PPT文档

  • 格式：ppt
  • 大小：624.50 KB
  • 文档页数：21

下载文档原格式

  / 21

合集下载

案例：最佳灾情巡视路线ppt课件

案例：最佳灾情巡视路线ppt课件
1
1）若分三组（路）巡视，试设计总路程最 短且各组尽可能均衡的巡视路线.
2）假定巡视人员在各乡（镇）停留时间T=2 小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分 几组；给出这种分组下最佳的巡视路线.
2
公路边的数字为该路段的公里数.
3
2) 问题分析：
O—R—29—Q—30—Q—28—27—26—N—24—23 —22—17—16—17—K—22—23—N—26—P—O
199.2
16
5.69
21.69
O—M—25—20—21—K—18—I—15—14—13—J —19—L—6—M—O
159.1
18
4.54
22.54
O—R—A—33—31—32—35—34—B—1—C—3 —
II —22—17—16—17—K—22—23—N—26—P—O
199.2
16 5.69
21.69
O—M—25—20—21—K—18—I—15—14—13—J III —19—L—6—M—O
159.1
18 4.54
22.54
O—R—A—33—31—32—35—34—B—1—C—3 —
IV D—4—D—3—2—O
长度 总长度
O—P—28—27—26—N—24—23—22—17—16—I—15— I—18—K—21—20—25—M—O O—2—5—6—L—19—J—11—G—13—14—H—12—F— 10—F—9—E—7—E— 8—4—D—3—C—O O—R—29—Q—30—32—31—33—35—34—A—B—1—O
18
表3
（路程单位：公里；时间单位：小时）
组名

1998年数学建模灾情巡视路线的设计

1998年数学建模灾情巡视路线的设计

183.2
99.25
max Ck min Ck ， 规定 0.2 分组均衡.计算得分组二 max Ck
的均衡度为
C1 C3 228.8 99.25 0.5662 ，所以此分法的均衡性很差. C1 228.8
为改善均衡性， 将第一组中的顶点 C,2,3,D,4 分给第三组（顶点 2 为这两组 的公共点） ，重新分分组后的近似最优解如下： 小组名称 路线 总路线长度 分组 2 总长度 176.7 552.9
5.1 问题一的模型 第一问中，要在返回 O 点的条件下，找到三组路径，使得总路径最短且三组 划分均衡.因此我们考虑先以三组尽可能均衡为目标，划分出各组，把问题转化 为三个旅行商问题.之后求出各分组的最短路径.具体实施过程如下： 首先我们对数据进行了处理， 从图中人工提取出各邻接点之间的权及较近两 点之间的最短路的权，得到图 1 的残缺权矩阵（见附录）.之后利用 Floyd 算法 求出缺省值，得到图一的完备权矩阵（部分如下表）.
第 一 组 O-2-5-6-7-E-8-E-9-F-10-F-12-H（①，②） 14-13-G-11-J-19-L-6-5-2-O
6
第 二 组 O-P-28-27-26-N-24-23-22-17-16（③，④） I-15-I-18-K-21-20-25-M-O 第 三 组 0-R-29-Q-30-32-31-33-35-34-A-1（⑤，⑥） B-C-3-D-4-D-3-2-O
183.2
193
表三分组二修正最短路线表 算得该分组的均衡度为 很好.巡视路线图如下：
C3 C1 193 176.7 0.0845 ，故该方法均衡度 C3 193
图 4 问题一路线图 5.2 问题二的模型 问题二是在问题一的基础上加了时间考量.故首先由时间限制对图二进行分 组，这就将问题二转化成了问题一的单旅行商问题.具体分组过程如下： 由于 T 2h ，t 1h ，V 35km / h ，需访问的乡镇共有 17 个，村共有 35 个. 计算出在乡（镇）及村的总停留时间为 17 * 2h 35* h 69h ，要在 24h 内完成巡 回， 加上行走时间得不等式: 69h

灾情巡视路线

灾情巡视路线

B题：灾情巡视路线第六组B ：灾情巡视路线摘要本文针对对受灾区灾情巡视的最佳路线选定问题，采用图论法建立数学模型，求解得到在不同条件下的灾情最佳巡视路线。

对于问题（1），首先将该县的公路网示意图转化为赋权图，再用WinQSB 软件求得该赋权图的最小生成树，根据生成树将赋权图分解为三个子图，运用lingo 软件求出各子图的最小哈密顿圈1C 、2C 、3C ，比较得出各图的最小哈密顿圈即为最佳灾情巡视路线1l 、2l 、3l 。

对于问题（2），先根据问题（1）求得的最佳路线得出公式a t T V243517≤++，算出至少分四组可在24小时内完成巡视；运用与问题（1）相同的方法求出各组的最佳巡视路线。

对于问题（3），运用图论软件包求出各点间的最短距离及各点到县政府的最短路径，计算出单独巡视最远点所需时间即为最短时间，以这个时间为限制，逐层找出巡视路线。

对于问题（4），进行简单讨论，得出结果。

关键词：赋权图 哈密顿圈 最小生成树一、问题重述今年夏天某县遭受水灾。

为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。

巡视的基本路线为从县政府所在地出发，走遍17个乡（镇）、35个村，最后回到县政府所在地。

要求在各条件下求出灾情巡视的最佳路线，具体问题：1.若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。

2.假定巡视人员在各乡（镇）停留时间2=t小时，汽=T小时，在各村停留时间1车行驶速度35V公里/小时。

要再24小时内完成巡视，至少应分几组；给出=这种分组下你认为最佳的巡视路线。

3.在上述关于T，t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。

4.若巡视组数已定（比如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。

下图为该县的乡（镇）、村公路示意图：二、符号说明=il(,2,1)29,分别表示第i组的巡视路线；i)7,C=k(,2,1分别表示所求哈密顿圈；kl表示最短总路程；a 表示巡视组数；i m 表示第i 组巡视的乡（镇）数；i n 表示第i 组巡视的村数； i s 表示第i 组的巡视路线长度三、 模型假设（1） 假设在巡视途中不会遇到塞车、道路毁坏等问题。

灾情巡视最佳路径选择(含程序)

灾情巡视最佳路径选择(含程序)

灾情巡视最佳路径选择摘要本文解决的是对全县各乡镇和村庄进行灾情巡视线路的设计问题，该问题属于点的遍历性的TSP问题。

因此我们结合图论的相关知识并考虑到分组的均衡性，建立起了约束最优化线路模型来解决该问题。

针对问题一，我们先建立起目标函数(见5.11中式(0.1))，随后根据各点的集中区域进行划分，引入均衡度ə进行分组方案的比较，最终采用方案二(见 5.2中方案二)。

再利用破圈法得到了最短回路。

最后matlab编程求解（见附录一）得出三组的巡视路程分别为200.1公里,196.8公里,205.1公里,总路程为602公里，均衡度ə=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问题背景今年夏天该县遭受水灾。

为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。

巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。

1.2需要解决的问题若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。

假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。

灾情巡视路线

灾情巡视路线

各组所走的路程分别为（单位：km） ：212.2、125.5、215.9， 各组所走的路程总和为（单位：km） ：553.6， 并求出其均衡度为：0.49。 4.2 问题二 4.2.1 问题分析 与第一题相同， 将巡视人员分为几组便将区域划分为几个部分。因此我们首 先确定在 24 小时内至少需要将巡视人员分为几组。在划分区域的过程中，经过 观察与计算发现，图中乡、村的分布十分的均匀，不存在某个区域集中出现乡或 者镇， 因此可以忽略停留时间对最小生成树与深度搜索的影响。所以我们套用第 一问的模型。 先进行粗略的分割得到大致所需的路程，然后根据最小生成树进行 深度优先算法，得到精确的路径，根据路径算出各组所需时间以及总时间。 4.2.2 模型的求解 首先计算需要把巡视人员分为几组： 乡镇停留时间:T=2 小时,村镇停留时间:t=1 小时,车速:V=35 公里/小时,乡 镇共有 17 个，村镇有 35 个, 总停留时间为 17×2+35=69 小时，要在 24 小时内 完成巡回，若不考虑汽车行驶时间，由 69/i<24(i 为分的组数)得到 i 最小为 4， 故至少要分 4 组。 由于该网络的乡(镇)、村分布较为均匀,故有可能找出停留时间尽量均衡的 分组,当分 4 组时各组停停留时间大约为 69/4=17.25 小时， 则每组分配在路途上 的时间大约为 24-17.25=6.75 小时。 根据第一问, 分三组时有个总巡视路程 602 公里，分 4 组时的总路程不会 比 603 公里大太多 , 不妨以 603 公里作为第二问的巡视总路程。路上约花 603/35=17 小时,若平均分配给 4 个组,每个组约需 17/4=4.25 小时小于 6.75 小 时,故巡视路线分成 4 组是合理的。 接下来套用第一题的最小生成树的 DFS 模型，得出了以下四个分组的路径：

灾情巡视

灾情巡视

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）表示总巡视路线最短.此问题包含两方面的的内容：第一，顶点的分组；第二，每组中要求最佳推销回路，即三组能保持一定的均衡度。

最佳灾情巡视路线模型

最佳灾情巡视路线模型【摘要】“图论”是组合数学的分支，它与其他的数学分支，如群论、矩阵论、拓扑学，数值分析有着密切的联系。

在其它科学领域，如计算机科学、运筹学、电网络分析、化学物理以及社会科学等方面图论也具有越来越重要的地位，并已取得丰硕的成果。

而且，图论的理论和方法在数学建模中也有重要应用。

本文概述了一些常用的图论方法和算法，并通过举例（灾情巡视路线）说明其在数学建模中的应用。

【关键词】图论灾情巡视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)，因而是个有效算法。

灾情巡视路线的数学模型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关键字1问题重述下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。

灾情巡视路线选择


根据上述的问题分析，先把 6 个干枝编号①-⑥，把①②分为一组，③④分 为一组，⑤⑥分为一组。分组如下：
计算其总距离与均衡度，计算结果如下：
均衡度α
=
241.9−125.5 241.9
= 48.12%
由上面的计算结果可以看出， 其总距离较短但是均衡度较大， 所以这种划分不合 理要进行优化。所以要将现有的路线进行手工改进，稍稍改变其路线，调整均衡 度，改进后的结果如下：
195.8
22.59
Ⅱ
162.4
22.64
Ⅲ
156.9
21.48
Ⅳ
186.6
22.33
我们可以看出 4 条路线的巡视都在 24 小时内完成，而且都控制在 23 小时内，路 线划分合理。
问题三 3.3.1 问题分析 对于问题三，我们可以从题目得到，巡视的人员足够多，但是务必要求在最 短的时间内完成巡视。 要求最短的时间， 就应该求出离县委政府 O 最远的乡 （镇） 或村所需的时间，且在途经的乡（镇）或村不作停留，这样才能求出最短的巡视 时间。我们要得到最佳的巡视路线，尽管人员足够多，我们还是应当避免不必要 的人力物力的浪费， 每组完成巡视的时间应当尽量差不多。根据最小生成树及该 县地图还有求出的最短的巡视时间，我们将整个巡视路线进行统筹规划，合理分 组。 3.3.2 问题解答 我们通过计算可得离县委政府 O 最远的乡 （镇） 为 H， 到 H 所需的时间至少是 6.43 小时。并通过最小生成树及该县的地图进行合理的分组。显然，其余组的时间要 小于第一组 O-H-O 的时间 6.43 小时，根据统筹学，我们进行了合理的划分和计 算。详细如下表： 小组名 称 第一组 第二组 第三组 第四组 第五组 第六组 第七组 第八组 第九组 第十组 第十一 组 第十二 组 第十三 组 第十四 组 第十五 组 路线 O-H-O O-3-D-4-D-3-2-O O-2-5-6-M-O O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-O O-2-5-6-E-11-G-11-E-6-5-2-O O-2-5-6-7-E-9-F-9-E-7-6-5-3-O O-2-5-6-7-E-11-E-8-E-8-E-11-E-7-6-5-2-O O-2-5-6-L-20-L-6-5-2-O O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O O-2-5-6-L-19-J-19-L-6-5-2-O O-M-25-21-K-17-16-17-K-21-25-M-O O-M-25-21-K-18-I-15-I-18-K-21-25-M-O O-M-25-21-K-18-I-18-K-21-25-M-O O-M-25-21-K-21-25-M-O 所用时间 （h） 6.43 5.99 6.34 5.85 5.76 5.58 6.15 5.65 5.54 6.15 6.10 5.45 5.99 5.49 5.49 停留地 时间差 点 （h） H 0 3、4、D 0.44 2、3、5、 0.09 M 9、12 0.58 7、10 0.67 G 0.85 F、E 0.28 8、11 0.78 L、20 0.89 13、14 0.28 19、J 16、17 15、18 I 21、K 0.33 0.98 0.44 0.94 0.94

防洪减灾救灾防汛防洪PPT模板

防备要点
防蚊防疫病
洪水后，环境遭到污染，蚊蝇鼠等会大量增加，它们会传播疾病。
感谢您的观看指导
汇报人：XXX
食品
打火机
食品
饮用水
生活用品
储存好各பைடு நூலகம்尚能使用的通讯设施
暴雨洪水发生前后注意事项
进入受洪水浸泡过的室内，不要忽视了病菌、霉变等安全隐患。
防房屋环境卫生
房屋是否坚固日常用品病菌残留
重点关注
对住房质量进行安全性检查，确认坚固性。打开门窗，通风换气，清洗家具，清理室内物品。尽量对房间墙壁和地面进行消毒，消灭室内病菌。衣物要消毒并暴晒后再穿，消毒处理不可少。日常用品根据情形采取煮沸消毒或在日光下暴晒。
张义昌，龙南县东江乡大稳村党支部书记。2006年7月26日，受5号台风“格美”影响，龙南县遭遇严重洪灾。
张义昌不顾自身因腰椎间盘突出导致的左腿疼痛加剧，立刻组织群众转移，不幸被洪水冲走，献出了年仅43岁的宝贵生命。8月中旬，张义昌被省政府追认为革命烈士。
弘扬抗洪精神
一方面是水大势猛、南北为害，对改革开放、经济发展和千百万人民群众生命财产造成的严重威逼；抗洪军民的团结合作，坚强拼搏。
交通出行
雨势不大、路面泥泞、潮湿的湿滑时:道路摩擦系数大幅下降,在途经坡道、弯道时,应"轻打方向、缓踩刹车”
暴雨天气，我们可能会遇到各种各样的麻烦，如果当麻烦自己不能单独解决时，一定要联系相关的人来帮助自己解决，例如遇山洪被困时及时拨打119
外出如遇雷雨，可以蹲下，尽量降低自己的高度，同时将双脚并拢，减少跨步电压带来的危害。因为雷击落地时，会沿着地表逐步向四周开释能量。此时，行走中的人前脚和后脚之间就可能因电位差不同，而在两步间产生一定的电压。
忌挑选金属把的雨伞忌在电器设施周围撑伞忌高处使用雨伞
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1) 用图论软件包求出G中任意两个顶点间的最短路, 构造出完全图 G ( V , E ) ( x , , y ) E ,( x , y ) mdiG (n x,y); 2) 输入图 G 的一个初始H圈； 3) 用对角线完全算法（见[23]）产生一个初始圈;
4) 随机搜索出G中若干个H圈，例如2000个； 5) 对第2)，3)，4)步所得的每个H圈，用二边逐次
1）若分三组（路）巡视，试设计总路程最 短且各组尽可能均衡的巡视路线.
2）假定巡视人员在各乡（镇）停留时间T=2 小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分 几组；给出这种分组下最佳的巡视路线.
公路边的数字为该路段的公里数.
2) 问题分析：
从O点出发去其它点，要使路程较小应尽量走 O点到该点的最短路.
故用软件包求出O点到其余顶点的最短路. 这些最短路构成一棵O为树根的树. 将从O点出发的树枝称为干枝.
准在则由分1 上尽组述量时分使应组同遵准一从则干准，枝则我上：们及找其到分两枝种上分的组点形分式在如同下一：组. 准分则从组2O1点应:（出将⑥发相，到邻①其的）它干，点枝（共上②有的，6点条③分干）在枝，同，（一它⑤组们，；的④名）称 分准分别则组为32尽①:（量，①将②，长，②的③）干，，枝④（与，③短⑤，的，④干⑥）枝. ，分（在⑤同，一⑥组）. 分组1极不均衡,故考虑分组2.
修正法进行优化，得到近似最优H圈；
6) 在第5)步求出的所有H圈中，找出权最小的一个, 此即要找的最优H圈的近似解.
问题一 若分为三组巡视，设计总路程最短且各
组尽可能均衡的巡视路线.
此问题是多个售货员的最佳旅行售货员问题.
即在加权图G中求顶点集V 的划分V1,V2,,Vn，将G
分成n个生成子图G[V1],
总路线 长度
191.1
241.9 125.5
路线的 总长度
558.5
因为该分组的均衡度
0(m C 1) a (C x (C i)2)24.2 9 14.1 912.55 54.2%
.
i1,2,3
所以此分法的均衡性很差.
为改善均衡性，将第Ⅱ组中的顶点C,2,3,D,4
分组2:(①,②),(③,④),(⑤,⑥)
对分组2中每组顶点的生成子图,用算法一求出 近似最优解及相应的巡视路线.
在每个子图所构造的完全图中,取一个尽量包含 上图中树上的边的H圈作为其第2)步输入的初始圈.
分组2的近似解
小组 名称
I II
III
路
线
O—P—28—27—26—N—24—23—22—17—16—I—15— I—18—K—21—20—25—M—O O—2—5—6—L—19—J—11—G—13—14—H—12—F— 10—F—9—E—7—E— 8—4—D—3—C—O O—R—29—Q—30—32—31—33—35—34—A—B—1—O
解决此类问题的一般方法是不现实的，对于规模较大
的问题可使用近似算法来求得近似最优解.
6. 最佳灾情巡视路线的模型的建 立与求解
问题转化为在 给定的加权网 络图中寻找从
给定点O出发, 行遍所有顶点 至少一次再回 回到点O ,使得 总权(路程或时 时间)最小,即 最佳旅行售货 员问题.
近证第因似最能2二)算佳得，边法旅到3逐)求行，较次其售4优修)一货步的正个员分计法近问别算的似题用结结最是三果果优N种. 与P解方—初，法完始来产全圈代生问有替初题关最始,,采故优圈用本解，一算.以种法保 算法一 求加权图的最佳旅行售货员回路近似算法:
本题是旅行售货员问题的延伸－多旅行售货员问题. 本题所求的分组巡视的最佳路线，也就是m条
经过同一点并覆盖所有其他顶点又使边权之和达到 最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四 个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题， 即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此， 一定要针对问题的实际特点寻找简便方法，想找到
1. 问题引入与分析
1) 98年全国大学生数学建模竞赛B题“最佳灾 情巡视路线”中的前两个问题是这样的：
今年(2019年)夏天某县遭受水灾. 为考察灾情、 组织自救，县领导决定，带领有关部门负责人到 全县各乡（镇）、村巡视. 巡视路线指从县政府 所在地出发，走遍各乡（镇）、村，又回到县政 府所在地的路线.
一个均衡分组. 条件 4）表示总巡视路线最短.
此问题包含两方面：a)对顶点分组, b)在每组中
求(单个售货员)最佳旅行售货员回路.
因单个售货员的最佳旅行售货员回路问题不存
故多
也不
存在多项式时间内的精确算法.
而图中节点数较多，为53个，我们只能去寻求 一种较合理的划分准则，对图1进行粗步划分后,求 出各部分的近似最佳旅行售货员回路的权,再进一 进一步进行调整，使得各部分满足均衡性条件3).
本题给出了某县的公路网络图，要求的是在不 同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡 镇、村之间的公路看作此图对应顶点间的边，各条 公路的长度（或行驶时间）看作对应边上的权，所 给公路网就转化为加权网络图，问题就转化图论中 一类称之为旅行售货员问题，即在给定的加权网络 图中寻找从给定点O出发，行遍所有顶点至少一次 再回到点O，使得总权（路程或时间）最小.
G[V2
],,
G[Vn
]，使得
n
1) 顶点O Vi, i 1,2,3,,n. 2) Vi V (G).
max | (Ci ) (C j ) |
i1
3) i, j
max (Ci )
，其中Ci 为Vi的导出
i
子图G[Vi ]中的最佳旅行售货员回路，(Ci )为
Ciபைடு நூலகம்
的权，i,
n
j

1,2,3,..., n.
4) (Ci) min
i1
max | (Ci ) (C j ) |
定义 称0 i, j max (Ci )
为该分组的实际
i
均衡度. 为最大容许均衡度.
显然0 0 1，0越小，说明分组的均衡性越
好. 取定一个 后，0与 满足条件 3）的分组是