11第十一章 图与网络模型电子课件.pptx

管理运筹学第十一章第十一章 图与网络模型图与网络模型北京理工大学 韩伯棠 教授 1图图与网络的基本概念与网络的基本概念2最短路问题最短路问题354最小生成树问题最小生成树问题最大流问题最大流问题最小最小费用最大流问题费用最大流问题本章内容本章内容 图论中图是由点和边构成，可以反映一些对象之间的关系。例如：一个人群中，相互认识关系可以用图表示，如图11-1 所示。 11.1 图与网络的基本概念图与网络的基本概念 图 11-1 1 11.1 图与网络的基本概念图与网络的基本概念 图 11-2 1 图论不仅描述对象之间关系，还研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间连线的长短曲直，对于反映对象之间的关系并不重要，如对赵等七人的相互认识关系可用图 11-2 表示，可见图论的图与几何图、工程图是不一样的。 如果把上例中的“相互认识”关系改为“认识”关系，那么用两点之间的连线很难刻画他们之间关系，这时引入一个带箭头的连线，称为弧。图 11-3 就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。 11.1 图与网络的基本概念图与网络的基本概念 图 11-3 1 11.1 图与网络的基本概念图与网络的基本概念 1 无向图无向图： 点和边构成的图，记作 G =(V, E)。有向图：有向图： 点和弧构成的图，记作 D =(V, A)。连通图连通图： 对无向图 G，若任何两个不同的点之间，至少存在一条链，则 G 为连通图。回路：回路： 若路的第一个点和最后一个点相同，则该路为回路。赋权图：赋权图： 对无向图 G 的每一条边(vi,vj)，相应有一个数 wij，则称图 G 为赋权图，wij 称为边(vi,vj)上的权。网络：网络： 在赋权的有向图 D 中指定一点，称为发点(记为 vs)，指定另一点为收点(记为 vt)，其余点称为中间点，并把 D 中的每一条弧的赋权数 cij 称为弧(vi,vj)的容量，这样的赋权有向图 D 称为网络。 1图图与网络的基本概念与网络的基本概念2最短路问题最短路问题354最小生成树问题最小生成树问题最大流问题最大流问题最小最小费用最大流问题费用最大流问题本章内容本章内容11.2 最短路问题最短路问题 u 最短路问题：最短路问题：对一个赋权的有向图 D 中的指定的两个点 vs 和 vt 找到一条从 vs 到vt 的路，使这条路上所有弧的权数的总和最小，这条路被称之为从 vs 到 vt 的最短路。这条路上所有弧的权数的总和被称为从 vs 到 vt 的距离。u 求解最短路的求解最短路的 Dijkstra 算法（双标号法算法（双标号法）u 步骤步骤：1给出点 v1 以标号（0,s）2找出已标号的点的集合 I，没标号的点的集合 J 及弧的集合(vi , v j ) | vi I , v j J 3如果上述弧的集合是空集，则计算结束。如果 vt 已标号(lt,kt)，则 vs 到 vt 的距离为 lt，而从 vs 到 vt 的最短路径，则可以从 vt 反向追踪到起点 vs 而得到。如果 vt 未标号，则可以断言不存在从 vs 到 vt 的有向路。如果上述的弧的集合不是空集，则转下一步。4对上述弧的集合中的每一条弧，计算 sij = li + cij。在所有的 sij 中，找到其值为最小的弧。不妨设此弧为(vc,vd)，则给此弧的终点以双标号(scd,c)，返回步骤 2。 211.2 最短路问题最短路问题 例例1 求图 11-4 中 v1 到 v6 的最短路解：采用 Dijkstra 算法，解得最短路径为 v1v3v4v6各点的标号如图 11-5 所示。 图 11-5 图 11-4 211.2 最短路问题最短路问题 求解求解过程如过程如下：下：（1）给定起始点 v1 标以(0，s)，表示从 v1 到 v1 的距离为 0，v1 为起始点。（2）这时已标定点集合 I=v1，未标定点的集合 J=v2,v3,v4,v5,v6，弧集合(vi , v j ) |vi I , v j J = (v1 , v2 ), (v1 , v3 ), (v1 , v4 ) , 则有 min(s12, s13, s14)=s13=2，这样，给弧( v1 , v3 ) 的终点 v3 标以（2，1），表示从 v1 到 v3 的距离为 2.（3）这时 I = v1 , v3, J = v2 , v4 , v5 , v6 ，则min(s12,s14,s34)=s12=s34=3。给弧 ( v1 , v2 ) 的终点 v2 标以 (3，1)，表示从 v1 到 v2 的距离为 3；我们给弧 ( v3 , v4 ) 的终点 v4 标以 (3,3)，表示从 v1 到 v4 的距离为 3.（4）这时 I = v1 , v2 , v3 , v4 , J = v5 , v6 ，则有 min (s26,s46)=s46=8,这样给点 v6 标以 (8,4)，表示从 v1 到 v6 的距离是 8.（5）这时 I = v1 , v2 , v3 , v4 , v6 , J = v5 ，而弧集合为空，计算结束。也即 v5 还未标号，说明从 v1 到 v5 没有有向路.（6）得到一组最优结果。从终点 v6 的标号倒推到起点 v1，得到此最短路径为 v1 - v3- v4- v6 . 211.2 最短路问题最短路问题 例 2电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：km）。解：求无向图的最短路问题。把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用 Dijkstra 算法来求解。 图 11-6 211.2 最短路问题最短路问题 例例 2 求解过程如求解过程如下下（1）给起始点 v1，标号为（0,s）。（2）I=v1,J=v2,v3,v4,v5,v6,v7。边的集合为v1,v2,v1,v3，则s12=15,s13=10,min(s12,s13)=s13=10。给边v1, v3中未标号点 v3 标以（10，1）表示从 v1 到 v3 的距离为 10。（3）这时 I=v1,v3,J=v2,v4,v5,v6,v7。边集合为v1, v2,v3, v2, v3, v5，则有min(s12,s32,s35)=s32=13。给边v3, v2中未标号点 v2 标以（13,3）。（4）这时 I=v1,v3,v2, J=v4,v5,v6,v7.边集合为v3, v5,v2,v4,v2,v7，则有min（s35,s24,s27）= s35=14。给边v3, v5中未标号点 v5 标以 (14,3)。（5）这时 I=v1,v2,v3,v5, J=v4,v6,v7. 边集合为v2,v4,v5,v4,v2,v7,v5,v6, 则有min(s24,s54,s27,s56)=s56=16。给边v5,v6中未标号点 v6 标以 (16,5)。（6）这时 I=v1,v2,v3,v5,v6, J=v4,v7。边集合为v2,v4,v2,v7,v5 ,v4,v6,v7，则有min (s24,s27, s54,s67) =s54=18。给边v5,v4中未标号点 v4 标以 (18,5)。 211.2 最短路问题最短路问题 例例 2 求解过程如求解过程如下下（7）这时 I=v1,v2,v3,v4,v5,v6, J=v7。边集合为v2, v7,v4 , v7,v6, v7，并有 min(s27,s47,s67)=s67=22。给边v6, v7中未标号点 v7 标以（22，6）。（8）此时 I=v1,v2,v3,v4,v5,v6,v7, J 为空集，计算结束。（9）得到最短路。最短路径 v1v3v5v6v7，每点的标号如图 11-7 所示。 图 11-7 211.2 最短路问题最短路问题 例例 3 设备更新问题设备更新问题 某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格如表 11-1 所示。表 11-1 表 11-2设备维修费如表 11-2 所示。 2年份年份12345年初价格年初价格1111121213使用年数使用年数0112233445 每年维修费每年维修费568111811.2 最短路问题最短路问题 例例 3 求解如下求解如下：将问题转化为最短路问题，如图 11-8 所示。用 vi 表示“第 i 年年初购进一台新设备”，弧（vi,vj）表示第 i 年年初购进的设备一直使用到第 j 年年初。 图 11-8把所有弧的权数计算如下表 212345611622304159216223041317233141723518611.2 最短路问题最短路问题 (继上页）把权数赋到图11-18中，得图11-19，再用 Dijkstra 算法求最短路。 求解求解过程如过程如下：下：(1)给定起始点 v1 标以（0，s)。(2)这时 I=v1,J=v2, v3, v4, v5 , v6。弧集合为(v1, v2),(v1 ,v3),(v1 ,v4),(v1 , v5 ) , (v1 , v6 ) ，则 min(s12, s13, s14, s15, s16)=s12=16，给弧（v1, v2）的终点 v2 标以（16，1）。(3)这时 I=v1, v2, J=v3, v4, v5 , v6。弧集合为(v1, v3),(v1, v4),(v1, v5), (v1, v6), (v2, v3),(v2, v4),(v2, v5), (v2, v6)，有min(s13,s14,s15,s16,s23,s24,s25,s26)=s13=22，给弧(v1, v3)的终点 v3 标以（22，1）。 2 图11-1911.2 最短路问题最短路问题 （4）这时 I=v1, v2, v3,J=v4, v5, v6。则min (s14, s15, s16, s24, s25, s26, s34, s35, s36) =s14=30。给弧（v1, v4）的终点 v4 标以（30，1）。（5）这时 I=v1, v2, v3, v4, J=v5, v6。则min(s15,s16,s25,s26,s35,s36,s45,s46)=s15=41。给弧（v1,v5）的终点 v5 标以（41，1）。（6）这时 I =v1, v2, v3, v4, v5, J=v6。则min(s16,s26,s36,s46,s56)=s36=s46=53。给弧（v3 , v6）和（v4,v6）的终点v6标以（53,3）和（53,4），最终得到图 11-10，可知，v1 到 v6 的距离是 53，最短路径有两条：v1v3v6 和 v1v4v6。 图 11-10 2 1图图与网络的基本概念与网络的基本概念3最短路问题最短路问题54最小生成树问题最小生成树问题最大流问题最大流问题最小最小费用最大流问题费用最大流问题本章内容本章内容211.3 最小生成树问题最小生成树问题 树是图论中的重要概念，所谓树就是一个无圈的连通图。 图 11-11图 11-11 中，（a）就是一个树，而（b）因为图中有圈,所以就不是树，（c）因为不连通所以也不是树。 311.3 最小生成树问题最小生成树问题 给了一个无向图 G=(V,E)，我们保留 G 的所有点，而删掉部分 G 的边或者说保留一部分 G 的边，所获得的图 G，称之为 G 的生成子图。在图 11-12 中，（b）和（c）都是（a）的生成子图。 如果图 G 的一个生成子图还是一个树，则称这个生成子图为生成树，在图 11-12中（c）就是（a）的生成树。 最小生成树问题就是指在一个赋权的连通的无向图 G 中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。 图 11-12 311.3 最小生成树问题最小生成树问题 算法算法的步骤的步骤如下：如下：（1）在给定的赋权的连通图上任找一个圈。（2）在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。（3）如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第（1）步。 求解最小生成树的破圈算法求解最小生成树的破圈算法 311.3 最小生成树问题最小生成树问题 例 4用破圈算法求图11-13（a）中的一个最小生成树。 图 11-13 311.3 最小生成树问题最小生成树问题 3 (1)在G中找一个圈（v1，v7，v6，v1），去掉权数最大的边v1,v6，得图G1，如图11-13（b)。 (2)在G1中找一个圈（v3，v4，v5，v7,v3），去掉权数最大的边v4,v5，得图G2，如图11-13（c)。 (5)在G4中找一个圈（v2，v3，v7，v2），去掉权数最大的边v3,v7，得图G5，如图11-13（f)。（6）在G5已找不到任何一个圈，即G5为图G的最小生成树，其总权数为3+3+3+1+2+7=19 (4)在G3中找一个圈（v3，v5，v6，v7，v3），去掉权数最大的边v5,v6或v3,v7 ，得图G4，如图11-13（e)。 (3)在G2中找一个圈（v2，v3，v5，v7，v2），去掉权数最大的边v5,v7， 得图G3，如图11-13（d)。 例例4 解法如下解法如下11.3 最小生成树问题最小生成树问题 例 5某大学准备对其所属的 7 个学院办公室进行计算机联网，这个网络可能联通的途径如图 11-14 所示，图中 v1,v7 表示 7 个学院办公室，请设计一个网络能联通 7 个学院办公室，并使总的线路长度最短。 图 11-14解：此问题实际上是求图 11-14 的最小生成树，这在例4中已经求得，即按照图 11-13 的（f）设计，可使此网络的总的线路长度为最短，为19百米。“管理运筹学”软件有专门的子程序可以解决最小生成树问题。 3 1图图与网络的基本概念与网络的基本概念最短路问题最短路问题5最小生成树问题最小生成树问题最大流问题最大流问题最小最小费用最大流问题费用最大流问题本章内容本章内容24311.4 最大流问题最大流问题 最大流问题：最大流问题：给一个带收发点的网络，其每条弧的赋权称为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。一、最大流的数学模型一、最大流的数学模型例 6某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如图 11-15 所示。由于管道直径的变化，它的各段管道（vi,vj）的流量 cij（容量）也是不一样的。cij 的单位为万加仑/小时。如果使用这个网络系统从采地 v1 向销地 v7 运送石油，问每小时能运送多少加仑石油？ 图 11-15 411.4 最大流问题最大流问题 目标函数： max F = f12 + f14 ； 约束条件： f12 = f23 + f25 , f14 = f43 + f46 + f47 , f23 + f43 = f35 + f36 , f25 + f35 = f57 , f36 + f46 = f67 , f57 + f67 + f47 = f12 + f14 , fij cij , (i = 1, 2,.,6; j = 2,7), fij 0, (i = 1,2,. ,6; j = 2,7). 以此例题建立线性规划数学模型：设弧(vi,vj)上流量为 fij，网络上的总的流量为 F 411.4 最大流问题最大流问题 满足守恒条件及流量可行条件的一组网络流fij称之为可行流，（即线性规划的可行解），可行流中一组流量最大（即发点总流出量最大）的称为最大流（即线性规划的最优解）。 例 6 的数据cij代入以上线性规划模型，用“管理运筹学”软件运算，得如下结果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最优值（最大流）=10。 411.4 最大流问题最大流问题 二、最大流问题网络图论的解法二、最大流问题网络图论的解法 对网络上弧容量的表示作改进。对一条弧（vi,vj）的容量我们用一对数 cij,0 标在弧（vi,vj）上，cij 靠近 vi 点，0靠近 vj 点，表示从 vi 到 vj 容许通过的容量为 cij，而从vj 到 vi 容许通过的容量为 0，这样可以省去弧的方向。如图 11-16 （a）和（b）所示。对于存在两条相反的弧（vi,vj）和（vj,vi）也可以用一条边和一对数组cij，cji表示它们的容量。如图11-16（c）和（d）所示。 图 11-18。用以上方法对例 6 的图11-15的容量标号作改进，得到图 11-18。 图 11-16 411.4 最大流问题最大流问题 求求最大流的基本最大流的基本算法算法:（1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的最小的顺流容量 pf，通过这条路增加网络的流量 pf。（3）在这条路上，减少每一条弧的顺流容量 pf，同时增加这些弧的逆流容量 pf，返回步骤（1）。用用此方法对例此方法对例 6 求解：求解：第一次迭代：选择路为 v1v4v7。弧（v4 , v7）的顺流容量为 2，决定了 pf=2，改进的网络流量如图 11-19所示。 图 11-19 411.4 最大流问题最大流问题 图 11-20 第二次迭代：选择路为 v1v2v5v7。弧（v2, v5）的顺流容量为 3，决定了 pf =3，改进的网络流量图如图 11-20 所示。 411.4 最大流问题最大流问题 第三次迭代：选择路为 v1v4v6v7。弧（v4, v6）的顺流容量为 1，决定了 pf =1，改进的网络流量图如图 11-21 所示。 图 11-21 411.4 最大流问题最大流问题 第四次迭代：选择路为 v1v4v3v6v7。弧（v3, v6）的顺流容量为 2，决定了 pf = 2，改进的网络流量图如图 11-22 所示。 图 11-22 411.4 最大流问题最大流问题 第五次迭代：选择路为 v1v2v3v5v7。弧（v2, v3）的顺流容量为 2，决定了 pf = 2，改进的网络流量图如图 11-23 所示。 图 11-23 411.4 最大流问题最大流问题 经过第五次迭代后已经找不到从发点到收点的一条路上的每一条弧顺流容量都大于零，运算停止。最大流量为 10。最大流量图如图 11-25 所示。 图 11-25 4 1图图与网络的基本概念与网络的基本概念最短路问题最短路问题4最小生成树问题最小生成树问题最大流问题最大流问题最小最小费用最大流问题费用最大流问题本章内容本章内容25311.5 最小费用最大流问题最小费用最大流问题 最小费用最大流问题：最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi,vj），除了给出容量 cij 外，还给出了这条弧的单位流量的费用 bij，要求一个最大流 F，并使得总运送费用最小。一、最小费用最大流的数学模型一、最小费用最大流的数学模型例 7由于输油管道的长短不一，所以在例 6 中每段管道（vi,vj）除了有不同的流量限制 cij 外，还有不同的单位流量的费用 bij，cij 的单位为万加仑/小时，bij 的单位为百元/万加仑。如图 11-26所示。从采地 v1 向销地 v7 运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出每小时的最大流量及最大流量的最小费用。 图 11-26 511.5 最小费用最大流问题最小费用最大流问题 这个这个最小费用最大流问题也是一个线性规划问题。最小费用最大流问题也是一个线性规划问题。 解：我们用线性规划来求解此题，可以分两步走。 第一步，先求出此网络图中的最大流量 F，这已在例 6 中建立了线性规划的模型，通过“管理运筹学”软件已经获得结果。 第二步，在最大流量 F 的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型。 设弧（vi,vj）上的流量为 fij，已知网络中最大流量为 F，只要在例 6 的约束条件上，再加上总流量必须等于 F 的约束条件：f12 + f14 = F，即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用 fij bij 。(vi ,v j )A由此得到线性规划模型如下。 511.5 最小费用最大流问题最小费用最大流问题 5min=fijbij=6f12+3f14+4f25+5f23+2f43+4f35+7f57+(vi,vj)A 3f36+3f46+8f47+4f67.s.t. f12+f14=F=10， f12=f23+f25, f14=f43+f46+f47, f23+f43=f35+f36, f25+f35=f57, f36+f46=f67, f57+f67+f47=f12+f14, fijcij,(i=1,2,6;j=2,3,7), fij0,(i=1,2,6;j=2,3,7).11.5 最小费用最大流问题最小费用最大流问题 管理运筹学软件，求得如下结果：f12=4, f14=6, f25=3, f23=1, f43=3,f57=5, f36=2, f46=1, f47=2, f67=3, f35=2。其最优值（最小费用）为 145。 如果例 7 的问题改为：每小时运送 6 万加仑的石油从采地v1 到销地 v7 最小费用是多少？应怎样运送？这就变成了一个最小费用流问题。求最小费用流问题的线性规划模型只要把最小费用最大流模型中的约束条件中的发点流量 F 改为 f 即可。在例 7 中只要把 f12+f14=F 改为 f12+f14=f=6，可得到最小费用流的线性规划模型。 511.5 最小费用最大流问题最小费用最大流问题 二、最小费用最大流的网络图论二、最小费用最大流的网络图论解法解法1、对网络上弧（vi ,vj ）的（cij,bij ）的表示作如下改进，用（b）来表示（a），用（d）来表示（c）。 图 11-27 511.5 最小费用最大流问题最小费用最大流问题 用上述方法对图11-26 中的弧标号进行改进，得图11-28 2、求、求最小费用最大流的基本算法最小费用最大流的基本算法 在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流的基本算法完全一样，不同的只是在步骤（1）中要选择一条总的单位费用最小的路，而不是包含边数最少的路。 图 11-28 511.5 最小费用最大流问题最小费用最大流问题 用上述方法对例 7 求解： 第一次迭代：最短路 v1v4v6v7。第一次迭代后总流量为 1，总费用 101=10。 图 11-29。 511.5 最小费用最大流问题最小费用最大流问题 第二次迭代：最短路 v1v4v7。第二次迭代后总流量为 3，总费用10+112= 32。 图 11-30 511.5 最小费用最大流问题最小费用最大流问题 第三次迭代：找到最短路 v1v4v3v6v7。第三次迭代后总流量为 5，总费用32+122= 56。 图 11-31 511.5 最小费用最大流问题最小费用最大流问题 第四次迭代：找到最短路 v1v4v3v5v7。第四次迭代后总流量为 6，总费用56+161= 72。 图 11-32 511.5 最小费用最大流问题最小费用最大流问题 图 11-33 第五次迭代：找到最短路 v1v2v5v7。第五次迭代后总流量为 9，总费用 72+317=123 511.5 最小费用最大流问题最小费用最大流问题 图 11-34 第六次迭代：找到最短路 v1v2v3v5v7。第六次迭代后总流量为 10，总费用123+22= 145。 511.5 最小费用最大流问题最小费用最大流问题 图 11-35 第六次迭代后，已找不到从v1到v7的每条弧容量都大于零的路了，故求得最小费用最大流。得到其最小费用最大流的流量图如11-35所示。其总流量为10，即每小时最多运10万加仑石油，其最小总费用为145百元。 511.5 最小费用最大流问题最小费用最大流问题 图 11-36 如果对例 7 求一个最小费用流的问题：每小时运送 6 万加仑石油从 v1 到 v7 的最小费用是多少？我们可以从第四次迭代及图 11-32 即可得到运送 6万加仑最小费用 72 百元，其运送方式如图 11-36 所示。 511.5 最小费用最大流问题最小费用最大流问题 图 11-37注：管理运筹学软件有专门的子程序用于解决这类问题 5 如果每小时运送 7 万加仑，我们可以在图 11-36 的基础上，再按第五次迭代所选的最短路运送 1 万加仑即得最小费用：72+1 17 = 89 百元，其运送方式如图 11-37 所示。谢谢 谢！谢！