《2010集训专题三图论模型.ppt》由会员分享，可在线阅读，更多相关《2010集训专题三图论模型.ppt（67页珍藏版）》请在金锄头文库上搜索。
1、20102010数学建模集训班专题数学建模集训班专题讲座讲座-图论模型的建立与分析图论模型的建立与分析赵承业赵承业 2010/7/1 2010/7/15 5专题v图的表示与锁具问题v最小生成树、TSP和灾区巡视问题v最短路、网络流和运输问题v作业图的表示与锁具问题图的表示与锁具问题不积硅步，无以至千里-荀子劝学Page 4图的矩阵表示图的矩阵表示 邻接矩阵邻接矩阵:1) 对无向图对无向图 ，其邻接矩阵，其邻接矩阵 ，其中：，其中： (以下均假设图为简单图以下均假设图为简单图).Page 52) 对有向图对有向图 ,其邻接矩阵其邻接矩阵 ,其中：其中： Page 6其中：其中：3) 对有向赋权图
2、对有向赋权图 , 其邻接矩阵其邻接矩阵 ,对于无向赋权图的邻接矩阵可类似定义对于无向赋权图的邻接矩阵可类似定义. Page 7关联矩阵关联矩阵关联矩阵关联矩阵 1) 对无向图对无向图 ，其关联矩阵，其关联矩阵 ,其中：其中：Page 82) 对有向图对有向图 ，其关联矩阵，其关联矩阵 ,其中：其中：Page 9两点间长度为两点间长度为k的路径数目的路径数目如果已经一个图的邻接矩阵A，我们想知道任意两个顶点之间长度为k的路径有多少条怎么办？一个简单的办法如下令A=A+IB=A X A X . X A （k个A相乘）那么B中元素bij的值就是从i点出发到j点的路径数目通过下面的案例我们讨论一下这个
3、方法的应用Page 101994 年全国大学生数学建模竞赛年全国大学生数学建模竞赛B 题题(锁具装箱锁具装箱) 某厂生产一种弹子锁具, 每个锁具的钥匙有5 个槽, 每个槽的高度从1, 2, 3, 4, 5, 6中任取一数. 由于工艺及其它原因, 制造锁具时对5 个槽的高度还有两个限制: (1) 至少有3 个不同的数;(2) 相邻两槽的高度之差不能为5. 满足以上条件制造出来的所有互不相同的锁具称为一批. 我们的问题是如何确定每一批锁具的个数 ?Page 11求解上述问题的一般方法计算机枚举排列组合计数缺点：计算量都比较大Page 12图论方法图论方法易见, x = x 1 - x 2, 其中,
4、 x 1= 相邻两槽高度之差不为5 的锁具数, 即: 满足限制条件(2) 的锁具数; x 2= 相邻两槽高度之差不为5 且槽高仅有1 个或2 个的锁具数, 即: 满足限制条件(2)但不满足限制条件(1) 的锁具数.我们用图论方法计算x 1 和x 2.Page 13图论方法图论方法基本引理基本引理令A k= A A Ak次= a (k)ij nn ,则a (k )ij = G 中以v i , v j 为端点的长度为k 的道路数.为利用上述引理计算x 1 和x 2, 我们构造无向图G= (V , E ) (如图1 所示)V = 1, 2, 3, 4, 5, 6, E = ij | i, j V 且
5、| i- j |5.Page 14图论方法图论方法在G 中, 每一条长度为4 的道路对应于一个相邻两槽高度之差不为5 的锁具, 即: 满足限制条件(2) 的锁具. 反之, 亦然. 于是, 可通过G 的邻接矩阵A 计算x 1, 具体步骤如下:Page 15图论方法图论方法因此又令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).显然, y 1= y 6, y 3= y 4= y 5= y 2, 我们只需计算y 1 和y 2.Page 16图论方法图
6、论方法计算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.Page 17图论方法图论方法同理, 计算y 2 时应考虑槽高只有2, 21, 22, 23, 24, 25, 26 的情形, 类似计算可得y 2= 1+ (4+ 4+ 4+ 4+ 4- 1) 5= 76.于是,
7、x 2= 612+ 764= 426, x = 6306- 426= 5880.最小生成树、最小生成树、TSP和灾区巡视问题和灾区巡视问题山穷水尽疑无路，柳暗花明又一村-陆游游山西村Page 199898年全国大学生数学建模竞赛年全国大学生数学建模竞赛B B题最佳灾情巡视路线题最佳灾情巡视路线今年今年(1998年年)夏天某县遭受水灾夏天某县遭受水灾. 为考察为考察灾情、组织自救，县领导决定，带领有灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡关部门负责人到全县各乡（镇）、村巡视视. 巡视路线指从县政府所在地出巡视路线指从县政府所在地出发发，走，走遍各乡（镇）、村，又回到县
8、政府所在遍各乡（镇）、村，又回到县政府所在地的路线地的路线.Page 209898年全国大学生数学建模竞赛年全国大学生数学建模竞赛B B题最佳灾情巡视路线题最佳灾情巡视路线Page 21问题问题1若分为三组巡视，设计总路程最短且各若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线组尽可能均衡的巡视路线.Page 22分析分析本题显然是一个加权图上求最短回路的问题我们可以借助图论的方法解决主要考虑两个基本的方法最小生成树方法旅行商（TSP）方法Page 23问题问题1的分析与求解的分析与求解-最小生成树法最小生成树法问题：如何分成相对均衡的三组？先求图的最小生成树，理由如下最小生成树包含图
9、的所有顶点，且最小生成树的边权是相邻顶点之间的距离，它描述了顶点之间的相近程度，可以考虑利用它来进行分块Page 24问题问题1的分析与求解的分析与求解-最小生成树法最小生成树法利用Kruskal算法，求得最小生成树如下Page 25问题问题1的分析与求解的分析与求解-最小生成树法最小生成树法对上面的最小生成树分解成三个子树分解原则分解点为O点或尽量接近O点分解得到的子图的顶点数尽可能接近17尽量使得分解得到的子图为连通图尽量使子图与点O的最短路的上点在该子图内尽量使各子图内部的点在内部形成回路Page 26问题问题1的分析与求解的分析与求解-最小生成树法最小生成树法分解的结果分解的结果Pag
10、e 27问题问题1的分析与求解的分析与求解-最小生成树法最小生成树法几个优化原则扩环原则 子图有孤立枝，扩环后权值应减小增环原则 环路上某个顶点有两枝，且有使两枝成环的边存在，考虑增环，增环后权值应减小换枝原则 环路上某顶点长出一条枝，该枝末梢和环路另一顶点接近，可考虑换枝Page 28问题问题1的分析与求解的分析与求解-最小生成树法最小生成树法Page 29问题问题1的分析与求解的分析与求解-TSP方法方法Page 30公路边的数字为该路段的公里数公路边的数字为该路段的公里数.Page 31问题分析：问题分析：本题给出了某县的公路网络图，要求的是在不本题给出了某县的公路网络图，要求的是在不同
11、的条件下，灾情巡视的最佳分组方案和路线同的条件下，灾情巡视的最佳分组方案和路线. 将每个乡（镇）或村看作一个图的顶点，各乡将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条镇、村之间的公路看作此图对应顶点间的边，各条再回到点再回到点O，使得总权（路程或时间）最小，使得总权（路程或时间）最小.公路的长度（或行驶时间）看作对应边上的权，所公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络一类称之为旅行售货员问题，即在给定的加权网络图中寻找从
12、给定点图中寻找从给定点O出发，行遍所有顶点至少一次出发，行遍所有顶点至少一次Page 32 问题问题1是三个旅行售货员问题是三个旅行售货员问题本题是旅行售货员问题的延伸本题是旅行售货员问题的延伸多旅行售货员问题多旅行售货员问题. 本题所求的分组巡视的最佳路线，也就是本题所求的分组巡视的最佳路线，也就是m条条众所周知，旅行售货员问题属于众所周知，旅行售货员问题属于NP完全问题，完全问题，显然本问题更应属于显然本问题更应属于NP完全问题完全问题. 有鉴于此，有鉴于此，经过同一点并覆盖所有其他顶点又使边权之和达到经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）最小的闭链（闭迹）.即求解
13、没有多项式时间算法即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法，想找到一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解的问题可使用近似算法来求得近似最优解.Page 33最佳灾情巡视路线的模型的建立与求解最佳灾情巡视路线的模型的建立与求解问题转化为在问题转化为在给定的加权网给定的加权网络图中寻找从络图中寻找从给定点给定点O出发出发,行遍所有顶点行遍所有顶点至少一次再回至少一次再回回到点回到点O ,使使得得总权总权(路程或时路程或时时间时间)最小最小,即即
14、最佳旅行售货最佳旅行售货员问题员问题.Page 34最佳旅行售货员问题是最佳旅行售货员问题是NP完全问题完全问题,采用一种采用一种近似算法求其一个近似最优解，来代替最优解近似算法求其一个近似最优解，来代替最优解.算法一算法一 求加权图的最佳旅行售货员回路近似算法求加权图的最佳旅行售货员回路近似算法: 1) 用图论软件包求出用图论软件包求出G中任意两个顶点间的最短路中任意两个顶点间的最短路, 构造出完全图构造出完全图2) 输入图输入图 的一个初始的一个初始H圈；圈；3) 用对角线完全算法（见用对角线完全算法（见3）产生一个初始圈）产生一个初始圈;4) 随机搜索出随机搜索出 中若干个中若干个H圈，
15、例如圈，例如2000个；个；5) 对第对第2)，3)，4)步所得的每个步所得的每个H圈，用二边逐次圈，用二边逐次修正法进行优化，得到近似最优修正法进行优化，得到近似最优H圈；圈；6) 在第在第5)步求出的所有步求出的所有H圈中，找出权最小的一个圈中，找出权最小的一个, 此即要找的最优此即要找的最优H圈的近似解圈的近似解.因二边逐次修正法的结果与初始圈有关因二边逐次修正法的结果与初始圈有关,故本算法故本算法第第2)，3)，4)步分别用三种方法产生初始圈，以保步分别用三种方法产生初始圈，以保证能得到较优的计算结果证能得到较优的计算结果.Page 35 问题一问题一 若分为三组巡视，设计总路程最短且
16、各组若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线尽可能均衡的巡视路线. 此问题是多个售货员的最此问题是多个售货员的最佳旅行售货员问题佳旅行售货员问题.4)Page 36 此问题包含两方面：此问题包含两方面：a)对顶点分组对顶点分组, b)在每组中在每组中求求(单个售货员单个售货员)最佳旅行售货员回路最佳旅行售货员回路. 因单个售货员的最佳旅行售货员回路问题不存在多因单个售货员的最佳旅行售货员回路问题不存在多项式时间内的精确算法项式时间内的精确算法.因此多个售货员的最佳旅行售因此多个售货员的最佳旅行售货员回路问题也不存在多项式时间内的精确算法货员回路问题也不存在多项式时间内的精确算法
17、.定义定义 称称为该分组的为该分组的实际均衡度实际均衡度. 为最大容许均衡度为最大容许均衡度. Page 37 而图中节点数较多，为而图中节点数较多，为53个，我们只能去寻求个，我们只能去寻求一种较合理的划分准则，对图一种较合理的划分准则，对图1进行粗步划分后进行粗步划分后,求求出各部分的近似最佳旅行售货员回路的权出各部分的近似最佳旅行售货员回路的权,再进一再进一进一步进行调整，使得各部分满足均衡性条件进一步进行调整，使得各部分满足均衡性条件3). 从从O点出发去其它点，要使路程较小应尽量走点出发去其它点，要使路程较小应尽量走O点到该点的最短路点到该点的最短路. 故用软件包求出故用软件包求出O
18、点到其余顶点的最短路点到其余顶点的最短路. 这些最短路构成一棵这些最短路构成一棵O为树根的树为树根的树.将从将从O点出发的树枝称为干枝点出发的树枝称为干枝.Page 38从从O点出发到其它点共有点出发到其它点共有6条干枝，它们的名称条干枝，它们的名称分别为分别为，. 在分组时应遵从准则：在分组时应遵从准则： 准则准则1 尽量使同一干枝上及其分枝上的点分在同一组尽量使同一干枝上及其分枝上的点分在同一组.准则准则2 应将相邻的干枝上的点分在同一组；应将相邻的干枝上的点分在同一组； 准则准则3 尽量将长的干枝与短的干枝分在同一组尽量将长的干枝与短的干枝分在同一组.由上述分组准则，我们找到两种分组形式
19、如下：由上述分组准则，我们找到两种分组形式如下：分组分组1:（，），（），（，），（），（，）分组分组2:（，），（），（，），（），（，）分组分组1极不均衡极不均衡,故考虑分组故考虑分组2.Page 39分组分组2:(,),(,),(,) 对分组对分组2中每组顶点的生成子图中每组顶点的生成子图,用算法一求出近似最优用算法一求出近似最优解及相应的巡视路线解及相应的巡视路线. 在每个子图所构造的完全图中在每个子图所构造的完全图中,取一个尽量包含上图中树取一个尽量包含上图中树上的边的上的边的H圈作为其第圈作为其第2)步输入的初始圈步输入的初始圈.Page 40分组分组2的近似解的近似解 Page
20、41因为该分组的均衡度因为该分组的均衡度.所以此分法的均衡性很差所以此分法的均衡性很差. 为改善均衡性，将第为改善均衡性，将第组中的顶点组中的顶点C,2,3,D,4分给第分给第组（顶点组（顶点2为这两组的公共点），重新分为这两组的公共点），重新分分组后的近似最优解见表分组后的近似最优解见表2.Page 42Page 43因该分组的均衡度因该分组的均衡度 所以这种分法的均衡性较好所以这种分法的均衡性较好.最短路、网络流和运输问题最短路、网络流和运输问题天下熙熙皆为利来，天下攘攘皆为利往-司马迁史记Page 45由钢管厂订购钢管，经铁路、公路由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道运输
21、，铺设一条钢管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1S7 钢管厂火车站450 里程（km)（沿管道建有公路）2000年全国数学建模竞赛年全国数学建模竞赛B题钢管的订购与运输题钢管的订购与运输Page 46钢厂的产量和销价（1单位钢管=1
22、km管道钢管）钢厂产量的下限：500单位钢管1单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）Page 47（1）制定钢管的订购和运输计划，使总费用最小）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？钢厂钢管产量上限的变化影响最大？A13258010103120124270108810706270302020304501043017506061942
23、05201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）讨论管道为树形图的情形）讨论管道为树形图的情形Page 48问题问题1的分析与求解的分析与求解整个铺设管道的工程看似错综复杂整个铺设管道的工程看似错综复杂, 其实可分为三个部分其实可分为三个部分:1. 各个工厂各个工厂(S 点点)生产一定数量的钢管生产一定数量的钢管2.
24、把钢管从工厂把钢管从工厂(S 点点)运送到铺设管道的关节点运送到铺设管道的关节点(A 点点)3. 从关节点从关节点(A 点点)将管道运至铺设地点将管道运至铺设地点这三个部分是相互依赖的这三个部分是相互依赖的, 不能简单地把三个部分孤立开来不能简单地把三个部分孤立开来讨论讨论. 但是通过仔细观察但是通过仔细观察,我们发现第二部分中的运费事实上我们发现第二部分中的运费事实上只与出发点只与出发点(S 点点)、 目标点目标点(A 点点)和运量有关和运量有关, 并且是运量的并且是运量的线性函数线性函数, 具备可叠加性具备可叠加性.运输总费用运输总费用: 因此因此, 我们可以简化第二部分的计算我们可以简化
25、第二部分的计算, 即先从铁路与公路网络即先从铁路与公路网络得出得出SA P 矩阵矩阵.Page 49问题的简化问题的简化求SA P 矩阵的基本思路是图的最短路算法.由于铁路的运输费用与线路的长度不是线性关系, 必须对铁路网做一些预处理才能套用图的标准最短路算法.Page 50下面叙述求下面叙述求SA P 矩阵的过程矩阵的过程1. 利用图的标准最短路算法, 从铁路网络得出图中任两个点之间的最短路径表T (如果两个点之间不连通, 认为它们之间的最短路长度为+ ).2. 利用题中的铁路运价表将T 中的每个元素(即最短距离)转化为运输费用, 将运输费用表记为C.3. 将公路的长度换算为运输费用, 由公
26、路路程图(包括要沿线铺设管道的公路)得出公路费用图G, 若 i, j 不连通, 则令Gi j= + .4. 对于任一组( i, j )1, n1, m 如果C ij = 500 这个条件. 求解过程分为三步:A . 假设工厂的产量只有上限, 下面的三个流网络模型都是针对这种情况的.B. 假设工厂的产量有上下限C. 工厂的产量0, 500,L i 我们这里只讨论A的情况Page 54线性费用流网络模型一线性费用流网络模型一Page 55线性费用流网络模型一线性费用流网络模型一图中边上的(A ,B ) ,A 表示边的流量限制,B 表示边的单位流量的费用, 下同.1) 网络有一个源点Sou rce,
27、 从 Sou rce 到每个S 点有一条边, 边的流量限制为S i 的最大产量L i, 单位费用为S i 生产钢管的单价R i .2) 从S i 到A j 有一条边, 边的流量限制为+ , 单位费用为SA P ij , 即从S i 到A j 运输单位长度钢管的费用.3) 对于每一条要铺设的管道P , 设其长度为L en, 两端点为A j ,A k , 则P 对应着L en 个点, 分别表示要铺设的一个单位长度的钢管(如图中P 11, P 12, P 13) , 从A j 到这L en 个点各有一条边, 边的流量限制为 1, 单位费用分别为 1, 2, 3,L en, 从A k 到这L en 个
28、点也各有一条边, 边的流量限制为1, 单位费用分别为L en, L en- 1, 3, 2, 1.Page 56线性费用流网络模型一线性费用流网络模型一4) 从 3)中的点(代表每单位长度的钢管的点)到图的汇点Target 各有一条边, 流量限制为1, 单位费用为0.这种流网络模型最简单, 效率也较低. 设铺设的管道共有T l 公里, 显然T l n 与m.网络中的点数大约为T l 个, 边数大约为 3T l, 最大流量为T l . 标准的网络流算法的时间复杂度为O (V 3M ax F low ) , 因此, 这个模型的复杂度为O (T l4). 对于题中的数据, T l 大约在5000 左
29、右, T l4 1015不可承受.优点：可用标准的最小费用最大流算法（如最小费用路算法）来求解.Page 57最小费用路算法最小费用路算法标准的最小费用最大流算法最小费用路算法:Step 0: 取零流f 为初始可行流.Step 1: 如果v (f ) = 最大流量vmax , 则f 为D 中流值为vmax的最小费用流; 否则转Step 2;Step 2: 构造增量网络D (f ). 如果D (f )中不存在(Sou rce, Target)路, 则D (f )中没有流值为vmax的可行流, 停止, 否则在D (f )中找一条最小费用路U , 转Step 3.Step 3: 用c (U )表示U
30、 的容量, 对 f 沿U 增广流值, 增广量为 c (U ) , 得到新流 f , 转Step 1.Page 58线性费用流网络模型二线性费用流网络模型二模型一之所以效率低, 最主要的问题是流网络中的点太多了. 通过点的合并, 可以大幅减小流网络中点的个数. 将线性费用流网络模型一中对应同一段要铺设的管道的点合并成一个点(即模型一图中的P 11, P 12, P 13合并为P 1) , 从A 点到这些点的边现在全部转到一个点上(如图) , 从这些点到T a rg et 的边合并为流量限制为P i (P i 即要铺设的管道的长度) , 单位费用为0 的一条边.Page 59线性费用流网络模型二线
31、性费用流网络模型二Page 60线性费用流网络模型二线性费用流网络模型二模型二中的点数为n+ m + P coun t+ 2, 边数大约为 2T l 个. 均比模型一有了大幅减小. 然而边数仍然太多, 而且这张流网络不是一张简单图(A 层与P 层中两个点之间的边数 1) , 因此, 不能直接套用标准最小费用最大流的复杂度计算公式.Page 61非线性费用流网络模型非线性费用流网络模型Page 62非线性费用流网络模型非线性费用流网络模型第三种模型是非线性费用网络流模型.1) 模型中所有的点与模型二相同;2) 模型中除了A 层与P 层之间的边以外, 均与模型二相同;3) A 层与P 层之间的边的
32、流量限制与模型二相同, 但是没有单位费用的概念, 因为费用是非线性的, 费用= 流量(流量+ 1)/ 2.Page 63非线性费用流网络模型非线性费用流网络模型最小费用路算法在找最小费用路时要用到边的单位费用, 而非线性模型中的非线性费用边没有单位费用的概念. 为此, 将最小费用路算法做一点修改:上边际费用 定义为: 流量增加1, 非线性费用边的费用的增加值下边际费用定义为: 流量减小1, 非线性费用边的费用的减小值当最小费用路算法查询正向流过这条边的单位费用时, 用上边际费用作为单位费用;当最小费用路算法查询负向流过这条边的单位费用时, 用下边际费用作为单位费用;经过这个修改, 最小费用路算
33、法就能应用于本题的非线性模型了.练习练习学而时习之，不亦说乎-论语学而Page 65练习练习1 求下图的求下图的Hamilton回路回路Page 66某工厂使用一台设备，每年年初工厂要作出决定：继续使某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购买新的？如果继续使用旧的，要用，购买新的？如果继续使用旧的，要付付维修费；若要购买维修费；若要购买一套新的，要一套新的，要付付购买费。试确定一个购买费。试确定一个5年计划，使总支出最年计划，使总支出最小。小。 若已知设备在各年的购买费，及不同机器役龄时的残值与若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如表维修费，如表1所示所示项目第1年第2年第3年第4年第5年购买费1111121213机器役龄0-11-22-33-44-5维修费5681118残值43210 练习练习2 设备更新问题设备更新问题提示：建立图模型求最短路提示：建立图模型求最短路
