数学建模--图论模型(3).ppt

《数学建模--图论模型(3).ppt》由会员分享，可在线阅读，更多相关《数学建模--图论模型(3).ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数学与统计学院 李书选 2012/07/18下下回回停停 7. 灾情巡视路线灾情巡视路线 8.二部图的匹配二部图的匹配 9. 网络流问题网络流问题问题引入与分析问题引入与分析 1) 98 1) 98年全国大学生数学建模竞赛年全国大学生数学建模竞赛B B题题“最佳灾最佳灾 今年今年(1998年年)夏天某县遭受水灾夏天某县遭受水灾. 为考察灾情、为考察灾情、组织自救，县领导决定，带领有关部门负责人到组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视全县各乡（镇）、村巡视. 巡视路线指从县政府巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政所在地出发，走遍各乡（镇）、村，

2、又回到县政府所在地的路线府所在地的路线.情巡视路线情巡视路线”中的前两个问题是这样的：中的前两个问题是这样的： 1）若分三组（路）巡视，试设计总路程最）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线短且各组尽可能均衡的巡视路线. 2）假定巡视人员在各乡（镇）停留时间）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间小时，在各村停留时间t=1小时，汽车行驶速度小时，汽车行驶速度V=35公里公里/小时小时. 要在要在24小时内完成巡视，至少应分小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线几组；给出这种分组下最佳的巡视路线.公路边的数字为该路段的公里数公路边的

3、数字为该路段的公里数.2) 2) 问题分析：问题分析：本题给出了某县的公路网络图，要求的是在不本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线同的条件下，灾情巡视的最佳分组方案和路线. 将每个乡（镇）或村看作一个图的顶点，各乡将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条镇、村之间的公路看作此图对应顶点间的边，各条再回到点再回到点O，使得总权（路程或时间）最小，使得总权（路程或时间）最小.公路的长度（或行驶时间）看作对应边上的权，所公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中给公路

4、网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点图中寻找从给定点O出发，行遍所有顶点至少一次出发，行遍所有顶点至少一次 如第一问是三个旅行售货员问题，第二问是四如第一问是三个旅行售货员问题，第二问是四本题是旅行售货员问题的延伸本题是旅行售货员问题的延伸多旅行售货员问题多旅行售货员问题. 本题所求的分组巡视的最佳路线，也就是本题所求的分组巡视的最佳路线，也就是m条条众所周知，旅行售货员问题属于众所周知，旅行售货员问题属于NP完全问题，完全问题，显然本问题更应属于显然本问题更应属于NP完全问题完全问题.

5、有鉴于此，有鉴于此，经过同一点并覆盖所有其他顶点又使边权之和达到经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）最小的闭链（闭迹）.个旅行售货员问题个旅行售货员问题.即求解没有多项式时间算法即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法，想找到一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解的问题可使用近似算法来求得近似最优解.分析分析 本题显然是一个加权图上求最短回路的问题本题显然是一个加权图上求最短回路的问题 我们可以借助图论的方法解决我

6、们可以借助图论的方法解决 主要考虑两个基本的方法主要考虑两个基本的方法 最小生成树方法最小生成树方法 旅行商（旅行商（TSP）方法）方法问题问题1的分析与求解的分析与求解-最小生成树法最小生成树法 问题：如何分成相对均衡的三组？问题：如何分成相对均衡的三组？ 先求图的最小生成树，理由如下先求图的最小生成树，理由如下 最小生成树包含图的所有顶点，且最小生成树包含图的所有顶点，且最小生成树的边权是相邻顶点之间最小生成树的边权是相邻顶点之间的距离，它描述了顶点之间的相近的距离，它描述了顶点之间的相近程度，可以考虑利用它来进行分块程度，可以考虑利用它来进行分块问题问题1的分析与求解的分析与求解-最小生

7、成树法最小生成树法 利用利用Kruskal算法，求得最小生成树如下算法，求得最小生成树如下问题问题1的分析与求解的分析与求解-最小生成树法最小生成树法 对上面的最小生成树分解成三个子树对上面的最小生成树分解成三个子树 分解原则分解原则 分解点为分解点为O点或尽量接近点或尽量接近O点点 分解得到的子图的顶点数尽可能接近分解得到的子图的顶点数尽可能接近17 尽量使得分解得到的子图为连通图尽量使得分解得到的子图为连通图 尽量使子图与点尽量使子图与点O的最短路的上点在该子图的最短路的上点在该子图内内 尽量使各子图内部的点在内部形成回路尽量使各子图内部的点在内部形成回路问题问题1的分析与求解的分析与求解

8、-最小生成树法最小生成树法问题问题1的分析与求解的分析与求解-最小生成树法最小生成树法 几个优化原则几个优化原则 扩环原则扩环原则 子图有孤立枝，扩环后权值应减小子图有孤立枝，扩环后权值应减小 增环原则增环原则 环路上某个顶点有两枝，且有使两枝环路上某个顶点有两枝，且有使两枝成环的边存在，考虑增环，增环后权值应减小成环的边存在，考虑增环，增环后权值应减小 换枝原则换枝原则 环路上某顶点长出一条枝，该枝末梢环路上某顶点长出一条枝，该枝末梢和环路另一顶点接近，可考虑换枝和环路另一顶点接近，可考虑换枝问题问题1的分析与求解的分析与求解-最小生成树法最小生成树法最佳灾情巡视路线的模型的建立与求解最佳灾

9、情巡视路线的模型的建立与求解问题转化为在问题转化为在给定的加权网给定的加权网络图中寻找从络图中寻找从给定点给定点O出发出发,行遍所有顶点行遍所有顶点至少一次再回至少一次再回回到点回到点O ,使得使得总权总权(路程或时路程或时时间时间)最小最小,即即最佳旅行售货最佳旅行售货员问题员问题.最佳旅行售货员问题是最佳旅行售货员问题是NP完全问题完全问题,采用一种采用一种近似算法求其一个近似最优解，来代替最优解近似算法求其一个近似最优解，来代替最优解.算法一算法一 求加权图的最佳旅行售货员回路近似算法求加权图的最佳旅行售货员回路近似算法: 1) 用图论软件包求出用图论软件包求出G中任意两个顶点间的最短路

10、中任意两个顶点间的最短路, 构造出完全图构造出完全图),(,),(),(yxEyxEVG);,(minyxdG2) 输入图输入图 的一个初始的一个初始H圈；圈；G3) 用对角线完全算法（见用对角线完全算法（见3）产生一个初始圈）产生一个初始圈;4) 随机搜索出随机搜索出 中若干个中若干个H圈，例如圈，例如2000个；个；G5) 对第对第2)，3)，4)步所得的每个步所得的每个H圈，用二边逐次圈，用二边逐次修正法进行优化，得到近似最优修正法进行优化，得到近似最优H圈；圈；6) 在第在第5)步求出的所有步求出的所有H圈中，找出权最小的一个圈中，找出权最小的一个, 此即要找的最优此即要找的最优H圈的

11、近似解圈的近似解.因二边逐次修正法的结果与初始圈有关因二边逐次修正法的结果与初始圈有关,故本算法故本算法第第2)，3)，4)步分别用三种方法产生初始圈，以保步分别用三种方法产生初始圈，以保证能得到较优的计算结果证能得到较优的计算结果. 问题一问题一 若分为三组巡视，设计总路程最短且各若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线组尽可能均衡的巡视路线. 此问题是多个售货员的最佳旅行售货员问题此问题是多个售货员的最佳旅行售货员问题.4)min)(1niiC 此问题包含两方面：此问题包含两方面：a)对顶点分组对顶点分组, b)在每组中在每组中求求(单个售货员单个售货员)最佳旅行售货员回路

12、最佳旅行售货员回路. 因单个售货员的最佳旅行售货员回路问题不存因单个售货员的最佳旅行售货员回路问题不存存在多项式时间内的精确算法存在多项式时间内的精确算法.故故多多也不也不 而图中节点数较多，为而图中节点数较多，为53个，我们只能去寻求个，我们只能去寻求一种较合理的划分准则，对图一种较合理的划分准则，对图1进行粗步划分后进行粗步划分后,求求出各部分的近似最佳旅行售货员回路的权出各部分的近似最佳旅行售货员回路的权,再进一再进一进一步进行调整，使得各部分满足均衡性条件进一步进行调整，使得各部分满足均衡性条件3). 从从O点出发去其它点，要使路程较小应尽量走点出发去其它点，要使路程较小应尽量走O点到

13、该点的最短路点到该点的最短路. 故用软件包求出故用软件包求出O点到其余顶点的最短路点到其余顶点的最短路. 这些最短路构成一棵这些最短路构成一棵O为树根的树为树根的树.将从将从O点出发的树枝称为点出发的树枝称为干枝干枝.从从O点出发到其它点共有点出发到其它点共有6条干枝，它们的名称条干枝，它们的名称分别为分别为，. 在分组时应遵从准则：在分组时应遵从准则： 准则准则1 尽量使同一干枝上及其分枝上的点分在同一组尽量使同一干枝上及其分枝上的点分在同一组.准则准则2 应将相邻的干枝上的点分在同一组；应将相邻的干枝上的点分在同一组； 准则准则3 尽量将长的干枝与短的干枝分在同一组尽量将长的干枝与短的干枝

14、分在同一组.由上述分组准则，我们找到两种分组形式如下：由上述分组准则，我们找到两种分组形式如下：分组分组1:（，），（），（，），（），（，）分组分组2:（，），（），（，），（），（，）分组分组1极不均衡极不均衡,故考虑分组故考虑分组2.分组分组2:(,),(,),(,) 对分组对分组2中每组顶点的生成子图中每组顶点的生成子图,用算法一求出用算法一求出近似最优解及相应的巡视路线近似最优解及相应的巡视路线. 在每个子图所构造的完全图中在每个子图所构造的完全图中,取一个尽量包含取一个尽量包含上图中树上的边的上图中树上的边的H圈作为其第圈作为其第2)步输入的初始圈步输入的初始圈.分组分组2的近似解

15、的近似解 因为该分组的均衡度因为该分组的均衡度54.2%9 .2415 .1259 .241)(max)()(3 , 2 , 1210iiCCC.所以此分法的均衡性很差所以此分法的均衡性很差. 为改善均衡性，将第为改善均衡性，将第组中的顶点组中的顶点C,2,3,D,4分给第分给第组（顶点组（顶点2为这两组的公共点），重新分为这两组的公共点），重新分分组后的近似最优解见表分组后的近似最优解见表2.%.69.114 .2161 .1914 .216)(max)()(3 , 2 , 1130iiCCC因该分组的均衡度因该分组的均衡度 所以这种分法的均衡性较好所以这种分法的均衡性较好. 问题二问题二

16、当巡视人员在各乡（镇）、村的停留当巡视人员在各乡（镇）、村的停留停留时间一定停留时间一定,汽车的行驶速度一定汽车的行驶速度一定,要在要在24小时内小时内完成巡视完成巡视,至少要分几组及最佳旅行的巡视路线至少要分几组及最佳旅行的巡视路线. 由于由于T=2小时小时,t=1小时小时,V=35公里公里/小时小时,需访问需访问的乡镇共有的乡镇共有17个，村共有个，村共有35个个. 计算出在乡计算出在乡(镇镇)及及村的总停留时间为村的总停留时间为17 2+35=69小时，要在小时，要在24小时小时内完成巡回，若不考虑行走时间，有内完成巡回，若不考虑行走时间，有: 69/i24(i为为分的组数分的组数).

17、得得i最小为最小为4，故，故至少要分至少要分4组组. 由于该网络的乡由于该网络的乡(镇镇)、村分布较为均匀、村分布较为均匀,故有可故有可能找出停留时间尽量均衡的分组能找出停留时间尽量均衡的分组,当分当分4组时各组停组时各组停停留时间大约为停留时间大约为69/4=17.25小时，则每组分配在路小时，则每组分配在路路途上的时间大约为路途上的时间大约为24-17.25=6.75小时小时.而前面讨而前面讨论过论过,分三组时有个总路程分三组时有个总路程599.8公里的巡视路线，公里的巡视路线，分分4组时的总路程不会比组时的总路程不会比599.8公里大太多公里大太多,不妨以不妨以599.8公里来计算公里来

18、计算.路上约用路上约用599.8/35=17小时小时,若平若平均分配给均分配给4个组个组,每个组约需每个组约需17/4=4.25小时小时6.75小小小时小时,故分成故分成4组是可能办到的组是可能办到的. 现在尝试将顶点分为现在尝试将顶点分为4组组.分组的原则：除遵从分组的原则：除遵从前面准则前面准则1、2、3外，还应遵从以下准则：外，还应遵从以下准则：准则准则4 尽量使各组的停留时间相等尽量使各组的停留时间相等. 用上述原则在下图上将图分为用上述原则在下图上将图分为4组，同时计算组，同时计算各组的停留时间各组的停留时间,然后用算法一算出各组的近似最然后用算法一算出各组的近似最最佳旅行售货员巡回

19、，得出路线长度及行走时间最佳旅行售货员巡回，得出路线长度及行走时间,从而得出完成巡视的近似最佳时间从而得出完成巡视的近似最佳时间. 用算法一计用算法一计计算时，初始圈的输入与分三组时同样处理计算时，初始圈的输入与分三组时同样处理.这这4组的近似最优解见表组的近似最优解见表3.表表3符号说明：加有底纹的表示前面经过并停留过符号说明：加有底纹的表示前面经过并停留过,此次只经过不停留此次只经过不停留;加框的表示此点只经过不停留加框的表示此点只经过不停留. 可看出可看出,表表3分组的均衡度很好分组的均衡度很好,且完全满足且完全满足24小时完成巡视的要求小时完成巡视的要求. 该分组实际均衡度该分组实际均

20、衡度 4.62% 74.2269.2174.2201v2v3v4v5v64686865505061456054例例9：如下图：如下图G，求最小生成树：，求最小生成树：Kruskal算法：从最小边开始按最小权加边，算法：从最小边开始按最小权加边，有圈去掉。有圈去掉。最小生成树最小生成树称称G = ( X, Y, E )为为二部图二部图. 如果如果X中的每个点都与中的每个点都与Y中的中的每个点邻接每个点邻接, 则称则称G = ( X, Y, E )为为完备二部图完备二部图. 若若 F：E R +, 则称则称G = ( X, Y, E, F )为为二部赋权图二部赋权图. 定义定义1 设设X , Y都

21、是非空有限顶点集都是非空有限顶点集, 且且X Y = ,YyXxxyE, 的一个匹配。的一个匹配。是是中均不邻接，则称中均不邻接，则称边在边在中任意两条中任意两条若若设图设图定义定义GMGMEM,EV,G 2 二部图的匹配及其应用二部图的匹配及其应用定义定义3 若匹配若匹配M的某条边与点的某条边与点v关联关联, 则称则称M饱和饱和点点v, 并且称并且称v是是M的的饱和点饱和点, 否则称否则称v是是M的的非饱非饱和点和点. 定义定义4 设设M是图是图G的一个匹配的一个匹配, 如果如果G的每一个点的每一个点都是都是M的饱和点的饱和点, 则称则称M是是完美匹配完美匹配；如果；如果G中中没有另外的匹配

22、没有另外的匹配M0, 使使 | M0 | M |, 则称则称M是是最最大匹配大匹配. 每个完美匹配都是最大匹配每个完美匹配都是最大匹配, 反之不一定成立反之不一定成立. 二部图的匹配及其应用二部图的匹配及其应用例例16： 判断下图的匹配判断下图的匹配最大匹配最大匹配非完美匹配非完美匹配完美匹配完美匹配二部图的匹配及其应用二部图的匹配及其应用定义定义5 设设M是图是图G的的一个匹配的的一个匹配, 其边在其边在EM和和M 中交错出现的路中交错出现的路, 称为称为G的一条的一条M交错路交错路. 起点起点和终点都不是和终点都不是M的饱和点的的饱和点的M 交错路交错路, 称为称为M 增广路增广路. 定理

23、定理1 G的一个匹配的一个匹配M是最大匹配的是最大匹配的充要条件充要条件是是G不包含不包含M 增广路增广路. 二部图的匹配及其应用二部图的匹配及其应用定理定理2 设设G = ( X, Y, E )为二部图为二部图, 则则 G存在存在饱和饱和X的每个点的匹配的充要条件是的每个点的匹配的充要条件是对任意对任意S ,有有 | N (S ) | | S | .其中其中, N (S ) = v | uS, v与与u相邻相邻. G存在完美匹配的充要条件是存在完美匹配的充要条件是对任意对任意S 或或S 有有 | N (S ) | | S | . X XY二部图的匹配及其应用二部图的匹配及其应用工作安排问题之

24、一工作安排问题之一 给给n个工作人员个工作人员x1, x2, , xn安排安排n项工作项工作y1, y2, , yn. . n个工作人员中每个人能胜任一项或几项工作个工作人员中每个人能胜任一项或几项工作, 但并但并不是所有工作人员都能从事任何一项工作不是所有工作人员都能从事任何一项工作. 比如比如x1能做能做y1, y2工作工作, x2能做能做y2, y3, y4工作等工作等. 这样便提出一个问题这样便提出一个问题, 对所有的工作人员能不能都对所有的工作人员能不能都分配一件他所能胜任的工作？分配一件他所能胜任的工作？ 二部图的匹配及其应用二部图的匹配及其应用 我们构造一个二部图我们构造一个二部

25、图G = ( X, Y, E ), 这里这里X = x1, x2, , xn,Y = y1, y2, , yn, 并且当且仅当工作人员并且当且仅当工作人员xi胜任工作胜任工作yj时时, xi与与yj才相邻才相邻. 于是于是, 问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配. 因为因为 |X|=|Y|, 所以完美匹配即为最大匹配所以完美匹配即为最大匹配. 二部图的匹配及其应用二部图的匹配及其应用1x2x3x4x5x1y2y3y4y5y例例17：求下图完美匹配：求下图完美匹配Hungarian算法：算法： 时终止。时终止。STSN 二部图的匹配及其应用二部图的匹配及其应用例例18

26、：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法： 解解 取初始匹配取初始匹配M0 = x2 y2 , x3 y3 , x5 y5 给给X中中M0的两个非饱和点的两个非饱和点x1, ,x4都给以标号都给以标号0 0和和标记标记* * ( (如下图所示如下图所示). ). 00*二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：00 去掉去掉x1的标记的标记*, 将与将与x1邻接的两个点邻接的两个点y2, y3都给以都给以标号标号1.1. 因为因为y2, y3都是都是M0的两个饱和点的两个饱和点, ,所以将它们在所以将它

27、们在M0中邻接的两个点中邻接的两个点x2, x3都给以相应的标号和标记都给以相应的标号和标记*. *11*23*二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：00*11*23* 去掉去掉x2的标记的标记*, 将与将与x2邻接且尚未给标号的三邻接且尚未给标号的三个点个点y1, y4, y5都给以标号都给以标号2. 222二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：00*1123*222 因为因为y1是是M0的非饱和点的非饱和点, 逆向返回逆向返回, 直到直到x1为

28、为0为为止止. .于是得到于是得到M0的增广路的增广路x1 y2x2 y1, 记记P = x1 y2 , y2x2 , x2 y1. 取取M1 = M0P = x1 y2 , x2 y1 , x3 y3 , x5 y5, 则则M1是比是比M多一边的匹配多一边的匹配. 二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：0* 再给再给X中中M1的非饱和点的非饱和点x4给以标号给以标号0和标记和标记*, 然后然后去掉去掉x4的标记的标记*, 将与将与x4邻接的两个点邻接的两个点y2, y3都给以标号都给以标号4. 44二部图的匹配及其应用

29、二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：044 因为因为y2, y3都是都是M1的两个饱和点的两个饱和点, , 所以将它们在所以将它们在M1中邻接的两个点中邻接的两个点x1, x3都给以相应的标号和标记都给以相应的标号和标记*.*23二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：044*23 去掉去掉x1的标记的标记*, 因为与因为与x1邻接的两个点邻接的两个点y2, y3都有标号都有标号4, 所以去掉所以去掉x3的标记的标记*. 而与而与x3邻接的两个点邻接的两个点y2, y

30、3也都有标号也都有标号4, 此时此时X中所中所有有标号的点都已去掉了标记有有标号的点都已去掉了标记*(如下图所示如下图所示), 因此因此M1是是G的最大匹配的最大匹配.没有完美匹配。没有完美匹配。 二部图的匹配及其应用二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：注意到注意到S=x1,x3,x4时，时，N(S)=y1,y3, ,N SS 所以没有完美匹配。所以没有完美匹配。二部图的匹配及其应用二部图的匹配及其应用定义定义6 设设G = ( X, Y, E , F )为完备的二部赋权为完备的二部赋权图图, 若若L：X Y R + 满足：满足：对任意对

31、任意xX, yY , L (x) + L ( y ) F (x y), 则称则称L为为G的一个的一个可行点标记可行点标记, 记相应的生成记相应的生成子图为子图为GL = ( X, Y, EL , F ), 这里这里EL = x yE | L ( x ) + L ( y ) = F (x y). 定理定理3 设设L是完备的二部赋权图是完备的二部赋权图G = ( X, Y, E , F )的可行点标记的可行点标记, 若若M *是是GL的完美匹配的完美匹配, 则则M *是是G的最佳匹配的最佳匹配. (权数最大的匹配权数最大的匹配) 二部图的匹配及其应用二部图的匹配及其应用工作安排问题之二工作安排问题

32、之二 给给n个工作人员个工作人员x1, x2, , xn安排安排n项工作项工作y1, y2, , yn. . 如果每个工作人员工作效率不同如果每个工作人员工作效率不同, 要求工作分配的要求工作分配的同时考虑同时考虑总效率最高总效率最高. 二部图的匹配及其应用二部图的匹配及其应用 我们构造一个二部赋权图我们构造一个二部赋权图G = ( X, Y, E , F ), 这里这里X = x1, x2, , xn,Y = y1, y2, , yn, F(xi yj )为工作人员为工作人员xi胜胜任工作任工作yj时的工作效率时的工作效率. 则问题转化为：求二部赋权图则问题转化为：求二部赋权图G的最佳匹配的

33、最佳匹配. 在求在求G 的最佳匹配时的最佳匹配时, 总可以假设总可以假设G为完备二部赋权为完备二部赋权图图. .若若xi与与yj不相邻不相邻, 可令可令F(xi yj )=0. 同样地同样地, 还可虚设点还可虚设点x或或y, ,使使|X|=|Y|. .如此就将如此就将G 转化为完备二部赋权图转化为完备二部赋权图, ,而且而且不会影响结果不会影响结果. 二部图的匹配及其应用二部图的匹配及其应用引例：车辆调度问题123456781302518322719222622931191821203019328293019192223264293019242519182152120181716141618车

34、地点MATLAB程序Kuhn-munkras算法function sumw=kuhngong(A)n=size(A,1); w=A; l=zeros(n,2);for i=1:n for j=1:n if l(i,1)temp al=temp; end, end, end, end for i=1:n if FLAG_S(i) l(i,1)=l(i,1)-al; end, end for j=1:n if FLAG_T(j) l(j,2)=l(j,2)+al; end, end FLAG_AGL=zeros(n,n); for i=1:n for j=1:n if l(i,1)+l(j,2)=

35、w(i,j) FLAG_AGL(i,j)=i; end, end, end, end for x=1:n for y=1:n if (FLAG_S(x)&(FLAG_T(y) &(FLAG_AGL(x,y)=x) f(y,2)=x; if M(y,2) %1start for z=1:n if (FLAG_AGL(z,y)=z) &(M(y,2)=z) FLAG_S(z)=1; FLAG_T(y)=1; f(z,1)=y; FLAG4=1; break; end, end else %1end stop=0; searched=zeros(n,2); while stop for i=1:n

36、if (f(y,2)=i) M(y,2)=i;M(i,1)=i; if i=u stop=1; break; end for k=1:n if (f(i,1)=k) M(k,2)=0; y=k; break; end, end if stop=0 break end, end, end, end MATLAB程序Kuhn-munkras算法（续）引例的求解：车辆调度问题引例的求解：车辆调度问题引例的求解：车辆调度问题 在加权二部图在加权二部图G中，设顶点中，设顶点x xi i与顶点与顶点y yj j之间的边权为之间的边权为a aijij, ,引引入入0-10-1决策变量决策变量z zj j,

37、,当匹配含边当匹配含边(x(xi i,y,yj j) )时时, ,z zijij=1,=1,否则否则z zijij=0.=0.因此，相应的线性规划模型为因此，相应的线性规划模型为 1111min1,1,2,(1,1,2, ,()01,1,2, .mnijijijnijjnijiija zzin Xzjn Yjn； s.t.， 部中每个点只与一条匹配边关联) 部中每个点只与一条匹配边关联 z或 例（指派问题）设有例（指派问题）设有n n个人个人, , 计划作计划作n n项工作项工作, , 第第i i个个人做第人做第j j项工作的收益如下表项工作的收益如下表, , 现求一种工作分配现求一种工作分配

38、方式，使得每个人完成一项工作，且使总收益最大方式，使得每个人完成一项工作，且使总收益最大. . 解：解：给出给出LINGO程序程序MODEL: 1! Assignment Problem Model; 2sets: 3 Flight/1.6/; 4 Assign(Flight, Flight): c, x; 5endsets 6! Here is income matrix; 7data: 8 c = 20 15 16 5 4 7 9 17 15 33 12 8 6 10 9 12 18 16 30 13 11 12 8 11 27 19 14 12 -99 7 10 21 10 32 13

39、-99 -99 -99 6 11 13; 14enddata 15 16! Maximize valve of assignments; 17max = sum(Assign: c*x); 18for(Flight(i): 19! Each i must be assigned to some j; 20 sum(Flight(j): x(i,j) = 1; 21! Each i must receive an assignment; 22 sum(Flight(j): x(j,i) = 1; 23); END 程序中第程序中第12 , 13行中的行中的-99, 是因为某人无法做某是因为某人无

40、法做某项工作项工作,可以认为某人做该项工作的收益是可以认为某人做该项工作的收益是 -inf , 在计算中在计算中通常取一个较大的负数就可以通常取一个较大的负数就可以. LINGO软件计算结果软件计算结果如下（只列出非零变量）如下（只列出非零变量）:Global optimal solution found at iteration: 0 Objective value: 135.0000 Variable Value Reduced Cost X( 1, 1) 1.000000 0.000000 X( 2, 3) 1.000000 0.000000 X( 3, 2) 1.000000 0.00

41、0000 X( 4, 4) 1.000000 0.000000 X( 5, 6) 1.000000 0.000000 X( 6, 5) 1.000000 0.0000009. 网络流问题网络流问题 现实生活中现实生活中,人们经常见到一些网络人们经常见到一些网络,如铁路网、公如铁路网、公路网、通信网、运输网等等。这些网络有一个共路网、通信网、运输网等等。这些网络有一个共同的特点，就是在网络中都有物资、人或信息等同的特点，就是在网络中都有物资、人或信息等某种量从一个地方流向另一个地方，如何安排这某种量从一个地方流向另一个地方，如何安排这些量的流动以便取得最大效益是一个很有意义的些量的流动以便取得最

42、大效益是一个很有意义的实际问题。实际问题。50年代福特（年代福特（Ford）、富克逊）、富克逊（Fulkerson）建立的）建立的“网络流理论网络流理论”，是网络应，是网络应用的重要组成部分。用的重要组成部分。 例：单源单汇网络和多元多汇网络。例：单源单汇网络和多元多汇网络。 sbacdt3,35,43,34,45,12,03,35,41,11x2x4v1v1y3vs3y2y6,15,12,21,12,23,23,05,34,01,01,02,16,04,46,43,11x2x4v1v1y3vs3y2y6,15,12,21,12,23,23,05,34,01,01,02,16,04,46,43

43、,1图13v3y3,21x1v1y6,15,12x4vs2y2,21,12,23,05,34,01,01,02,16,04,46,43,1s,2,4t,0,0图2, 6二、最大流与最小割二、最大流与最小割例例2：求图：求图3中网络的最大流。中网络的最大流。 sbacdt353452351图3sbacdt3,05,03,045,02,03,05,01,0(,)s (,3)s(,4)s( )asbacdt3,05,03,04,05,02,03,05,01,0(,)s (,3)s(,4)s( )b(,3)a(,3)b(,3)csbacdt3,35,33,34,05,02,03,04,01,0(,)s

44、 (,4)s( )csbacdt3,35,33,34,05,02,03,04,01,0(,)s (,4)s( )d(,3)b(,3)dsbacdt3,35,33,34,35,02,03,34,31,0(,)s (,4)s( ) esbacdt3,35,33,34,35,02,03,35,31,0(,)s (,1)s( )f(,1)b(,1)a(,1)d(,1)csbacdt3,35,43,34,45,12,03,35,41,1( )g三、最小费用最大流三、最小费用最大流sbact15,417,316,111,213,68,214,1图5sbact15,417,316,111,213,68,214,1( )asbact15,417,35,111, 213,68,23,1( )bsbact12,417,35,111, 28,20,( )c13,6sbact12,412,30,11, 23,20,( )d13,6sbact9,49,30,8, 213,6( ) e0,0,sbact681680814( )fsbact9,49,30,8, 213,6( ) e0,0,