- 1、下载文档前请自行甄别文档内容的完整性,平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益,请联系客服反馈,我们会尽快为您处理(人工客服工作时间:9:00-18:30)。
问题1的分析与求解--最小生成树法
最佳灾情巡视路线的模型的建立与求解
问题转化为在 给定的加权网 络图中寻找从 给定点O出发, 行遍所有顶点 至少一次再回 回到点O ,使得 总权(路程或时 时间)最小,即 最佳旅行售货 员问题.
近证第因似最能2二)算佳得,边法旅到3逐)求行,较次其售4优修)一货步的正个员分计法近问别算的似题用结结最是三果果优N种. 与P解方—初,法完始来产全圈代生问有替初题关最始,,采故优圈用本解,一算.以种法保 算法一 求加权图的最佳旅行售货员回路近似算法:
故用软件包求出O点到其余顶点的最短路. 这些最短路构成一棵O为树根的树. 将从O点出发的树枝称为干枝.
准在则由分1 上尽组述量时分使应组同遵准一从则干准,枝则我上:们及找其到分两枝种上分的组点形分式在如同下一:组. 准分则从组2O1点应:(出将⑥发相,到邻①其的)它干,点枝(共上②有的,6点条③分干)在枝,同,(一它⑤组们,;的④名)称 分准分别则组为32尽①:(量,①将②,长,②的③)干,,枝④(与,③短⑤,的,④干⑥)枝. ,分(在⑤同,一⑥组). 分组1极不均衡,故考虑分组2.
因单个售货员的最佳旅行售货员回路问题不存
故多
也不
存在多项式时间内的精确算法.
而图中节点数较多,为53个,我们只能去寻求 一种较合理的划分准则,对图1进行粗步划分后,求 出各部分的近似最佳旅行售货员回路的权,再进一 进一步进行调整,使得各部分满足均衡性条件3).
从O点出发去其它点,要使路程较小应尽量走 O点到该点的最短路.
6) 在第5)步求出的所有H圈中,找出权最小的一个, 此即要找的最优H圈的近似解.
问题一 若分为三组巡视,设计总路程最短且各
组尽可能均衡的巡视路线.
此问题是多个售货员的最佳旅行售货员问题.
即在加权图G中求顶点集V 的划分V1,V2,,Vn,将G
分成 n 个生成子图G[V1], G[V2 ],,
1) 顶点O Vi, i 1,2,3,,n.
本题给出了某县的公路网络图,要求的是在不 同的条件下,灾情巡视的最佳分组方案和路线.
将每个乡(镇)或村看作一个图的顶点,各乡 镇、村之间的公路看作此图对应顶点间的边,各条 公路的长度(或行驶时间)看作对应边上的权,所 给公路网就转化为加权网络图,问题就转化图论中 一类称之为旅行售货员问题,即在给定的加权网络 图中寻找从给定点O出发,行遍所有顶点至少一次 再回到点O,使得总权(路程或时间)最小.
G[Vn
2)
],使得
n 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 ) |
• 最小生成树包含图的所有顶点,且 最小生成树的边权是相邻顶点之间 的距离,它描述了顶点之间的相近 程度,可以考虑利用它来进行分块
问题1的分析与求解--最小生成树法
• 利用Kruskal算法,求得最小生成树如下
问题1的分析与求解--最小生成树法
• 对上面的最小生成树分解成三个子树 • 分解原则 • 分解点为O点或尽量接近O点 • 分解得到的子图的顶点数尽可能接近17 • 尽量使得分解得到的子图为连通图 • 尽量使子图与点O的最短路的上点在该子图
定义 称0 i, j max (Ci )
为该分组的实际
i
均衡度. 为最大容许均衡度.
显然0 0 1,0越小,说明分组的均衡性越
好. 取定一个 后,0与 满足条件 3)的分组是
一个均衡分组. 条件 4)表示总巡视路线最短.
此问题包含两方面:a)对顶点分组, b)在每组中
求(单个售货员)最佳旅行售货员回路.
本题是旅行售货员问题的延伸-多旅行售货员问题. 本题所求的分组巡视的最佳路线,也就是m条
经过同一点并覆盖所有其他顶点又使边权之和达到 最小的闭链(闭迹).
如第一问是三个旅行售货员问题,第二问是四 个旅行售货员问题.
众所周知,旅行售货员问题属于NP完全问题, 即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此, 一定要针对问题的实际特点寻找简便方法,想找到
网络优化的数学模型(2)
回 停
下
灾情巡视路线 二部图的匹配 网络流问题
回
停 下
问题引入与分析
1) 98年全国大学生数学建模竞赛B题“最佳灾 情巡视路线”中的前两个问题是这样的:
今年(1998年)夏天某县遭受水灾. 为考察灾情、 组织自救,县领导决定,带领有关部门负责人到 全县各乡(镇)、村巡视. 巡视路线指从县政府 所在地出发,走遍各乡(镇)、村,又回到县政 府所在地的路线.
1) 用图论软件包求出G中任意两个顶点间的最短路,
构造出完全图 G (V , E),(x, y) E,(x, y)
min dG (x, y);
2) 输入图 G 的一个初始H圈; 3) 用对角线完全算法(见[3])产生一个初始圈;
4) 随机搜索出G中若干个H圈,例如2000个;
5) 对第2),3),4)步所得的每个H圈,用二边逐次 修正法进行优化,得到近似最优H圈;
1)若分三组(路)巡视,试设计总路程最 短且各组尽可能均衡的巡视路线.
2)假定巡视人员在各乡(镇)停留时间T=2 小时,在各村停留时间t=1小时,汽车行驶速度V =35公里/小时. 要在24小时内完成巡视,至少应分 几组;给出这种分组下最佳的巡视路线.
公路边的数字为该路段的公里数.
2) 问题分析:
解决此类问题的一般方法是不现实的,对于规模较大
的问题可使用近似算法来求得近似最优解.
分析
• 本题显然是一个加权图上求最短回路的问题 • 我们可以借助图论的方法解决 • 主要考虑两个基本的方法 • 最小生成树方法 • 旅行商(TSP)方法
问题1的分析与求解--最小生成树法
• 问题:如何分成相对均衡的三组? • 先求图的最小生成树,理由如下
内 • 尽量使各子图内部的点在内部形成回路
问题1的分析与求解--最小生成树法
问题1的分析与求解--最小生成树法
• 几个优化原则 • 扩环原则 子图ຫໍສະໝຸດ Baidu孤立枝,扩环后权值应减小 • 增环原则 环路上某个顶点有两枝,且有使两枝
成环的边存在,考虑增环,增环后权值应减小
• 换枝原则 环路上某顶点长出一条枝,该枝末梢 和环路另一顶点接近,可考虑换枝