《图论模型课件》由会员分享，可在线阅读，更多相关《图论模型课件（67页珍藏版）》请在金锄头文库上搜索。
1、2010数学建模集训班专题讲座-图论模型的建立与分析,有图有真相，有你更精彩,赵承业 2010/7/15,专题,图的表示与锁具问题 最小生成树、TSP和灾区巡视问题 最短路、网络流和运输问题 作业,图的表示与锁具问题,不积硅步，无以至千里 -荀子劝学,图的矩阵表示,邻接矩阵:,1) 对无向图 ，其邻接矩阵 ，其中：,(以下均假设图为简单图).,2) 对有向图 ,其邻接矩阵 ,其中：,其中：,3) 对有向赋权图 , 其邻接矩阵 ,对于无向赋权图的邻接矩阵可类似定义.,关联矩阵,1) 对无向图 ，其关联矩阵 ,其中：,2) 对有向图 ，其关联矩阵 ,其中：,两点间长度为k的路径数目,如果已经一个图
2、的邻接矩阵A，我们想知道任意两个顶点之间长度为k的路径有多少条怎么办？ 一个简单的办法如下 令A=A+I B=A X A X X A （k个A相乘） 那么B中元素bij的值就是从i点出发到j点的路径数目 通过下面的案例我们讨论一下这个方法的应用,1994 年全国大学生数学建模竞赛B 题(锁具装箱),某厂生产一种弹子锁具, 每个锁具的钥匙有5 个槽, 每个槽的高度从1, 2, 3, 4, 5, 6中任取一数. 由于工艺及其它原因, 制造锁具时对5 个槽的高度还有两个限制: (1) 至少有3 个不同的数; (2) 相邻两槽的高度之差不能为5. 满足以上条件制造出来的所有互不相同的锁具称为一批. 我
3、们的问题是如何确定每一批锁具的个数 ?,求解上述问题的一般方法,计算机枚举 排列组合计数 缺点：计算量都比较大,图论方法,易见, x = x 1 - x 2, 其中, x 1= 相邻两槽高度之差不为5 的锁具数, 即: 满足限制条件(2) 的锁具数; x 2= 相邻两槽高度之差不为5 且槽高仅有1 个或2 个的锁具数, 即: 满足限制条件(2)但不满足限制条件(1) 的锁具数. 我们用图论方法计算x 1 和x 2.,图论方法,基本引理 令A k= A A Ak次 = a (k)ij nn , 则a (k )ij = G 中以v i , v j 为端点的长度为k 的道路数. 为利用上述引理计算x
4、 1 和x 2, 我们构造无向图G= (V , E ) (如图1 所示) V = 1, 2, 3, 4, 5, 6, E = ij | i, j V 且| i- j |5.,图论方法,在G 中, 每一条长度为4 的道路对应于一个相邻两槽高度之差不为5 的锁具, 即: 满足限制条件(2) 的锁具. 反之, 亦然. 于是, 可通过G 的邻接矩阵A 计算x 1, 具体步骤如下:,图论方法,因此,又令 x 2= y 1+ y 2+ y 3+ y 4+ y 5+ y 6, 其中, y i= 满足限制条件(2) 但不满足限制条件(1) 且首位为i 的锁具数, ( i= 1, 2, 3, 4, 5, 6).
5、 显然, y 1= y 6, y 3= y 4= y 5= y 2, 我们只需计算y 1 和y 2.,图论方法,计算y 1 可分别考虑槽高只有1, 12, 13, 14, 15 的情形. 若只有1, 这样的锁具数只有1 个; 若只有1 和i ( i= 2, 3, 4, 5) , 这样的锁具数= G 中以1 和i 为顶点, 长度为3 的道路数, 此数可通过A 的子矩阵A 1i= ( i= 2, 3, 4, 5) 计算得到. 事实上, 因为 所以 y 1= 1+ (4+ 4+ 4+ 4- 1) 4= 61.,图论方法,同理, 计算y 2 时应考虑槽高只有2, 21, 22, 23, 24, 25,
6、 26 的情形, 类似计算可得 y 2= 1+ (4+ 4+ 4+ 4+ 4- 1) 5= 76. 于是, x 2= 612+ 764= 426, x = 6306- 426= 5880.,最小生成树、TSP和灾区巡视问题,山穷水尽疑无路，柳暗花明又一村 -陆游游山西村,98年全国大学生数学建模竞赛B题最佳灾情巡视路线,今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.,98年全国大学生数学建模竞赛B题最佳灾情巡视路线,问题1,若分为三组巡视，设计总路
7、程最短且各组尽可能均衡的巡视路线.,分析,本题显然是一个加权图上求最短回路的问题 我们可以借助图论的方法解决 主要考虑两个基本的方法 最小生成树方法 旅行商（TSP）方法,问题1的分析与求解-最小生成树法,问题：如何分成相对均衡的三组？ 先求图的最小生成树，理由如下 最小生成树包含图的所有顶点，且最小生成树的边权是相邻顶点之间的距离，它描述了顶点之间的相近程度，可以考虑利用它来进行分块,问题1的分析与求解-最小生成树法,利用Kruskal算法，求得最小生成树如下,问题1的分析与求解-最小生成树法,对上面的最小生成树分解成三个子树 分解原则 分解点为O点或尽量接近O点 分解得到的子图的顶点数尽可
8、能接近17 尽量使得分解得到的子图为连通图 尽量使子图与点O的最短路的上点在该子图内 尽量使各子图内部的点在内部形成回路,问题1的分析与求解-最小生成树法,分解的结果,问题1的分析与求解-最小生成树法,几个优化原则 扩环原则 子图有孤立枝，扩环后权值应减小 增环原则 环路上某个顶点有两枝，且有使两枝成环的边存在，考虑增环，增环后权值应减小 换枝原则 环路上某顶点长出一条枝，该枝末梢和环路另一顶点接近，可考虑换枝,问题1的分析与求解-最小生成树法,问题1的分析与求解 -TSP方法,公路边的数字为该路段的公里数.,问题分析：,本题给出了某县的公路网络图，要求的是在不,同的条件下，灾情巡视的最佳分组
9、方案和路线.,将每个乡（镇）或村看作一个图的顶点，各乡,镇、村之间的公路看作此图对应顶点间的边，各条,再回到点O，使得总权（路程或时间）最小.,公路的长度（或行驶时间）看作对应边上的权，所,给公路网就转化为加权网络图，问题就转化图论中,一类称之为旅行售货员问题，即在给定的加权网络,图中寻找从给定点O出发，行遍所有顶点至少一次,问题1是三个旅行售货员问题,本题是旅行售货员问题的延伸,多旅行售货员问题.,本题所求的分组巡视的最佳路线，也就是m条,众所周知，旅行售货员问题属于NP完全问题，,显然本问题更应属于NP完全问题. 有鉴于此，,经过同一点并覆盖所有其他顶点又使边权之和达到,最小的闭链（闭迹）
10、.,即求解没有多项式时间算法.,一定要针对问题的实际特点寻找简便方法，想找到,解决此类问题的一般方法是不现实的，对于规模较大,的问题可使用近似算法来求得近似最优解.,最佳灾情巡视路线的模型的建立与求解,问题转化为在,给定的加权网,络图中寻找从,给定点O出发,行遍所有顶点,至少一次再回,回到点O ,使得,总权(路程或时,时间)最小,即,最佳旅行售货,员问题.,最佳旅行售货员问题是NP完全问题,采用一种,近似算法求其一个近似最优解，来代替最优解.,算法一 求加权图的最佳旅行售货员回路近似算法:,1) 用图论软件包求出G中任意两个顶点间的最短路,构造出完全图,2) 输入图 的一个初始H圈；,3) 用
11、对角线完全算法（见3）产生一个初始圈;,4) 随机搜索出 中若干个H圈，例如2000个；,5) 对第2)，3)，4)步所得的每个H圈，用二边逐次,修正法进行优化，得到近似最优H圈；,6) 在第5)步求出的所有H圈中，找出权最小的一个,此即要找的最优H圈的近似解.,因二边逐次修正法的结果与初始圈有关,故本算法,第2)，3)，4)步分别用三种方法产生初始圈，以保,证能得到较优的计算结果.,问题一 若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线. 此问题是多个售货员的最佳旅行售货员问题.,4),此问题包含两方面：a)对顶点分组, b)在每组中求(单个售货员)最佳旅行售货员回路. 因单个售货
12、员的最佳旅行售货员回路问题不存在多项式时间内的精确算法.因此多个售货员的最佳旅行售货员回路问题也不存在多项式时间内的精确算法.,定义 称,为该分组的实际均衡度.,为最大容许均衡度.,而图中节点数较多，为53个，我们只能去寻求,一种较合理的划分准则，对图1进行粗步划分后,求,出各部分的近似最佳旅行售货员回路的权,再进一,进一步进行调整，使得各部分满足均衡性条件3).,从O点出发去其它点，要使路程较小应尽量走,O点到该点的最短路.,故用软件包求出O点到其余顶点的最短路.,这些最短路构成一棵O为树根的树.,将从O点出发的树枝称为干枝.,从O点出发到其它点共有6条干枝，它们的名称,分别为，.,在分组时
13、应遵从准则：,准则1 尽量使同一干枝上及其分枝上的点分在同一组.,准则2 应将相邻的干枝上的点分在同一组；,准则3 尽量将长的干枝与短的干枝分在同一组.,由上述分组准则，我们找到两种分组形式如下：,分组1:（，），（，），（，）,分组2:（，），（，），（，）,分组1极不均衡,故考虑分组2.,分组2:(,),(,),(,),对分组2中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路线.,在每个子图所构造的完全图中,取一个尽量包含上图中树上的边的H圈作为其第2)步输入的初始圈.,分组2的近似解,因为该分组的均衡度,. 所以此分法的均衡性很差.,为改善均衡性，将第组中的顶点C,2,3,D,
14、4,分给第组（顶点2为这两组的公共点），重新分,分组后的近似最优解见表2.,因该分组的均衡度,所以这种分法的均衡性较好.,最短路、网络流和运输问题,天下熙熙皆为利来，天下攘攘皆为利往 -司马迁史记,2000年全国数学建模竞赛B题钢管的订购与运输,钢厂的产量和销价（1单位钢管=1km管道钢管）,钢厂产量的下限：500单位钢管,1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）,（1）制定钢管的订购和运输计划，使总费用最小.,（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？,（3）讨论管道为树形图的情形,问题1的分析与求解,整个
15、铺设管道的工程看似错综复杂, 其实可分为三个部分: 1. 各个工厂(S 点)生产一定数量的钢管 2. 把钢管从工厂(S 点)运送到铺设管道的关节点(A 点) 3. 从关节点(A 点)将管道运至铺设地点 这三个部分是相互依赖的, 不能简单地把三个部分孤立开来讨论. 但是通过仔细观察,我们发现第二部分中的运费事实上只与出发点(S 点)、 目标点(A 点)和运量有关, 并且是运量的线性函数, 具备可叠加性. 运输总费用: 因此, 我们可以简化第二部分的计算, 即先从铁路与公路网络得出SA P 矩阵.,问题的简化,求SA P 矩阵的基本思路是图的最短路算法. 由于铁路的运输费用与线路的长度不是线性关系
16、, 必须对铁路网做一些预处理才能套用图的标准最短路算法.,下面叙述求SA P 矩阵的过程,1. 利用图的标准最短路算法, 从铁路网络得出图中任两个点之间的最短路径表T (如果两个点之间不连通, 认为它们之间的最短路长度为+ ). 2. 利用题中的铁路运价表将T 中的每个元素(即最短距离)转化为运输费用, 将运输费用表记为C. 3. 将公路的长度换算为运输费用, 由公路路程图(包括要沿线铺设管道的公路)得出公路费用图G, 若 i, j 不连通, 则令Gi j= + . 4. 对于任一组( i, j )1, n1, m 如果C ij + , 且小于Gij , 那么就在公路费用图中加一条边. 即令Gi j= m
