数模专题-图论模型iii

《数模专题-图论模型iii》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模–图论模型(3)7.灾情巡视路线问题引入与分析1)98年全国大学生数学建模竞赛B题“最佳灾今年(1998年)夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.情巡视路线”中的前两个问题是这样的：1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线.2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，至少

2、应分几组；给出这种分组下最佳的巡视路线.公路边的数字为该路段的公里数.2)问题分析：本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条再回到点O，使得总权（路程或时间）最小.公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次如第一问是三个旅行售货员问题，第二问是四本题是旅行售货员问题

3、的延伸－多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是m条众所周知，旅行售货员问题属于NP完全问题，显然本问题更应属于NP完全问题.有鉴于此，经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.个旅行售货员问题.即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.分析本题显然是一个加权图上求最短回路的问题我们可以借助图论的方法解决主要考虑两个基本的方法最小生成树方法旅行商（TSP）方法问题1的分析与求

4、解--最小生成树法问题：如何分成相对均衡的三组？先求图的最小生成树，理由如下：最小生成树包含图的所有顶点，且最小生成树的边权是相邻顶点之间的距离，它描述了顶点之间的相近程度，可以考虑利用它来进行分块问题1的分析与求解--最小生成树法利用Kruskal算法，求得最小生成树如下问题1的分析与求解--最小生成树法对上面的最小生成树分解成三个子树分解原则分解点为O点或尽量接近O点分解得到的子图的顶点数尽可能接近17尽量使得分解得到的子图为连通图尽量使子图与点O的最短路的上点在该子图内尽量使各子图内部的点在内部形成回路问题1的分析

5、与求解--最小生成树法问题1的分析与求解--最小生成树法几个优化原则扩环原则子图有孤立枝，扩环后权值应减小增环原则环路上某个顶点有两枝，且有使两枝成环的边存在，考虑增环，增环后权值应减小换枝原则环路上某顶点长出一条枝，该枝末梢和环路另一顶点接近，可考虑换枝问题1的分析与求解--最小生成树法最佳灾情巡视路线的模型的建立与求解问题转化为在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次再回回到点O,使得总权(路程或时时间)最小,即最佳旅行售货员问题.最佳旅行售货员问题是NP—完全问题,采用一种近似算法求其一个近似最

6、优解，来代替最优解.算法一求加权图的最佳旅行售货员回路近似算法:1)用图论软件包求出G中任意两个顶点间的最短路,构造出完全图2)输入图的一个初始H圈；3)用对角线完全算法（见[3]）产生一个初始圈;4)随机搜索出中若干个H圈，例如2000个；5)对第2)，3)，4)步所得的每个H圈，用二边逐次修正法进行优化，得到近似最优H圈；6)在第5)步求出的所有H圈中，找出权最小的一个,此即要找的最优H圈的近似解.因二边逐次修正法的结果与初始圈有关,故本算法第2)，3)，4)步分别用三种方法产生初始圈，以保证能得到较优的计算结果.问

7、题一若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线.此问题是多个售货员的最佳旅行售货员问题.4)此问题包含两方面：a)对顶点分组,b)在每组中求(单个售货员)最佳旅行售货员回路.因单个售货员的最佳旅行售货员回路问题不存存在多项式时间内的精确算法.故多也不而图中节点数较多，为53个，我们只能去寻求一种较合理的划分准则，对图1进行粗步划分后,求出各部分的近似最佳旅行售货员回路的权,再进一进一步进行调整，使得各部分满足均衡性条件3).从O点出发去其它点，要使路程较小应尽量走O点到该点的最短路.故用软件包求出O点到其余

8、顶点的最短路.这些最短路构成一棵O为树根的树.将从O点出发的树枝称为干枝.从O点出发到其它点共有6条干枝，它们的名称分别为①，②，③，④，⑤，⑥.在分组时应遵从准则：准则1尽量使同一干枝上及其分枝上的点分在同一组.准则2应将相邻的干枝上的点分在同一组；准则3尽量将长的干枝与短的干枝分在同一组.由上述分组准则，我们找到