14-图与网络规划.ppt

第十章第十章 图与网络优化图与网络优化主要内容主要内容:图论的基本概念图论的基本概念最小支撑树问题最小支撑树问题最短路问题最短路问题最大流问题最大流问题最小费用最大流问题最小费用最大流问题一、基本概念与定理1、容量网络与流定义 给定一个有向图D=（V，A），在V中指定一个 发点vs，和一个收点vt，其余点称中间点。对任 意弧(vi，vj)A，有权Cij0，称为弧的容量。称 D为一个容量网络。记为：D=（V，A，C）。如如(a)图是一个容量网络图是一个容量网络v2v5348v3v1v4v65106111735（a）弧旁数字：弧旁数字：容量容量第四节第四节 网络最大流问题网络最大流问题网络D中的任一条弧(vi,vj)的流量记为f(vi,vj)，(简记fij)，显然，fijCij；一系列流量的集合f=f(vi,vj)构成网络D上的流（运输方案）。如如(b)图是网络上的图是网络上的一个流（运输方案）一个流（运输方案）v2v5313v3v1v4v61563222（b）弧旁数字：弧旁数字：流量流量例 连接某产品产地v1和销地v6的交通网如下：v2v5348v3v1v4v65106111735（a）弧（vi，vj）：从vi到vj的运输路线，弧旁数字：这条运输路线的最大通过能力。第四节第四节 网络最大流问题网络最大流问题目标：制定一个运输方案，使从v1到v6的产品运量最大。2、可行流与最大流、可行流与最大流 满足下述条件的流满足下述条件的流 f 称为称为可行流可行流:1)容量限制条件容量限制条件:对每一弧对每一弧(vi,vj)A 0fijCij2)平衡条件平衡条件:对对中间点中间点vj(js,t),有有 V(f)称为可行称为可行流流 f 的流量的流量,即发点的净输出量。即发点的净输出量。对对发点发点对对收点收点00如如(b)图是网络上的一图是网络上的一个可行流（运输方案）个可行流（运输方案）弧旁数字：弧旁数字：流量流量可行流总是存在的，例如所有弧的流量可行流总是存在的，例如所有弧的流量fij=0零流。零流。所谓最大流问题就是寻找流量最大的可行流。所谓最大流问题就是寻找流量最大的可行流。v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.23、增广链增广链对可行流对可行流f=fij的弧有的弧有 非饱和弧非饱和弧：0fijCij饱和弧饱和弧：fij=Cij 非零流弧非零流弧：0fij Cij 零流弧零流弧：fij=0 链的方向链的方向：若：若是联结是联结vs和和vt的一条链，定义链的的一条链，定义链的方向是从方向是从vs到到vt。前向弧前向弧：与链的方向一致的弧。前向弧：与链的方向一致的弧。前向弧全体全体记为记为+。后向弧后向弧：与链的方向相反的弧。后向弧：与链的方向相反的弧。后向弧全体全体记为记为-。v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2=(v1,v2,v3,v4,v5,v6)+=(v1,v2),(v2,v3),(v3,v4),(v5,v6)-=(v5,v4)后向弧后向弧v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2定义定义3 设设f是一个可行流是一个可行流,是从是从vs到到vt的一条链的一条链,若若满满 足下列条件足下列条件,称之为称之为(关于可行流关于可行流f的的)一条一条增广链增广链。(vi,vj)-0 fij CijCij.fijV3V1V2V4V58.45.03.35.4(vi,vj)+0fijCij前向弧是前向弧是 非饱和弧，非饱和弧，后向弧后向弧 是非零流弧，是非零流弧，4、截集与截量截集与截量定义定义4：网络：网络D=（V，A，C），），若点集若点集V被剖分为两个非被剖分为两个非 空集合空集合V1 和和 V1，使使vsV1，vt V1，V1 V1=，则把则把所有始点在所有始点在V1中，中，终终点在点在V1中的中的弧弧构成的构成的集合集合 （V1，V1）称为是分离）称为是分离vs和和vt的的截集截集。V1V1v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2=(v1,v2,v3)V11=(v4,v5,v6)截集为红色弧集；截集为红色弧集；由图可见，截集不是唯一的。由图可见，截集不是唯一的。每个截集相当于从发点每个截集相当于从发点vs到收点到收点vt的的必经之路必经之路，去掉截，去掉截集所有的弧，就不存在集所有的弧，就不存在从从发发点点vs到收点到收点vt的路的路。定义5 给定截集（V1，V1），把截集（V1，V1）中所 有弧的容量之和称为这个截集的容量（简称为截 量），记为C（V1，V1），即 v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2C（V1，V1）=5+3+5+6=19不难证明，任何一个可行流的流量V(f)都不会超过任一截集的容量。即v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2定理1 最大流最小截定理。任一个网络D中，从vs到 vt的最大流的流量等于分离vs，vt的最小截集 的容量。最小截集的容量是网络中的瓶颈容量。1、从一个可行流、从一个可行流f开始，寻找关于开始，寻找关于f的增广链；的增广链；2、如果不存在关于、如果不存在关于f的增广链，可行流的增广链，可行流f就是最大流就是最大流f*；3、如果存在关于、如果存在关于f的增广链，则以适当的调整量的增广链，则以适当的调整量 对对可行流可行流f进行调整，得到一个流量更大的可行流，不断进行调整，得到一个流量更大的可行流，不断重复调整过程，直到不再存在增广链时，就得到了最大流。重复调整过程，直到不再存在增广链时，就得到了最大流。由定理2可得到寻找最大流的方法：定理2 可行流f*是最大流 不存在关于f*的增广链。二、寻求最大流的标号法 从任一个可行流f出发，若网络中没有给定f，则从零流开始。（一）标号过程。通过标号来寻找增广链。每个标号点vj的标号包含两部分(vi，l(vj)：第一个标号vi表示标号点的前一点，以便找出增广链；第二个标号l(vj)是为了确定增广链的调整量用的。标号过程首先给vs标号（0，+），此时vs是未检查的标号点，其余各点都是未标号点。取一个未检查的标号点vi进行检查，给与vi相邻的所有未标号点vj标号：（1）如果在前向弧（vi，vj）上，有fij0，则给vj标号 （-vi，l(vj)）。其中l(vj)=minl(vi)，fji，此时新标 号点vj成为未检查的标号点。至此，点vi成为已检查过的标号点。重复标号过程，一旦vt被标号，即得到一条从vs到vt的增广链，转入调整过程。（二）调整过程。找出增广链，并沿增广链调整流量。（1）找增广链：从vt开始，反向追踪，找出增广链，如vt的第一个标号为k（或-k），则得到前向弧（vk，vt）或后向弧（vt，vk)。检查vk的第一个标号，若为i（或-i），又得到前向弧(vi,vk)或后向弧(vk,vi)。再检查vi的第一个标号,依此找下去,直到vs。被找出的弧构成了增广链。（2）调整流量令调整量=l(vt)，沿增广链构造新的可行流f，去掉所有的标号，对新的可行流f=f ij，重新进行标号。重复标号过程和调整过程，直到标号过程进行不下去且vt未获得标号为止，说明当前可行流不存在增广链，即得到了最大的可行流。例 用标号法求下图网络的最大流。弧旁的数字是（Cij,fij)。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)解：（一）标号过程（1）给vs标号（0，）；（2）检查vs，在vs的前向弧（vs，v1）上，fs1=1，Cs1=5，fs10，给v2标号(-1,l(v2),这里继续检查v1，在v1的前向弧（v1，v3）上，f13=C13=2，不满足标号条件。此时，未检查的标号点为v2（-1，1）v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，）（s，4）（-1，1）（4）检查v2，在v2的后向弧（v3，v2）上，f32=10，给v3标号(-2,l(v3),这里（-2，1）（2，1）继续检查v2，在v2的前向弧（v2，v4）上，f24C24，给v4标号(2,l(v4),这里 此时，未检查的标号点为v3和v4，在v3和v4中可任选一点进行检查，不妨检查v3。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，）（s，4）（-1，1）（-2，1）（5）检查v3，在v3的前向弧（v3，vt）上，f3t=1，C3t=2，f3tC3t，给vt标号(3,l(vt),这里至此，vt得到标号，转入调整过程。（3，1）（2，1）（二）调整过程:从vt开始逆向追踪，找到增广链。（vs,v1,v2,v3,vt）=l(vt)=1，在上进行流量=1的调整，v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，）（s，4）（-1，1）（2，1）（-2，1）（3，1）得可行流f 如右图所示：去掉各点标号，从vs开始，重新标号。v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)（0，）（s，3）点v1：标号过程无法进行，所以f 即为最大流。vs的净输出量=最大流量V（f）=3+2=5=vt的净输入量与此同时，可找到最小截集（V1,V1）截集：（V1，V1）=（vs，v2），（v1，v3）最大流量 V（f）=最小截量C（V1，V1）=5标号点集V1=(vs,v1)未标号点集V1=(v2,v3,v4,vt)v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)（0，）（s，3）第五节 最小费用最大流问题 网络网络D=（V，A，C）,每一弧（每一弧（vi，vj）A，给出给出（vi，vj）上单位流量的费用上单位流量的费用b(vi，vj)0，（，（简记简记bij）。）。最小费用最大流问题：最小费用最大流问题：求一个最大流求一个最大流 f，且使流的总费用，且使流的总费用取最小值。取最小值。一、求解原理一、求解原理 设对可行流设对可行流 f 存在增广链存在增广链，当沿，当沿 以以=1调整调整f，得新的可行流得新的可行流 f 时，时，(显然显然 V(f)=V(f)+1)，两流两流的费用之差的费用之差 b(f)-b(f)=？为增广链为增广链 的费用。的费用。b(f)-b(f)+1-1例：例：.vsv1v2v3v4v5vt354176增广增广链链 的的费费用用=(3+4+1+6)-(5+7)=2不同的增不同的增广广链链的的费费用是不同的用是不同的求最小费用最大流的原理：求最小费用最大流的原理：在网络在网络D中，若中，若f 是是流量流量为为V(f)的的费用最小的可行流费用最小的可行流,而而 是关于是关于f 的所有增广链中的所有增广链中费用最小的增广链费用最小的增广链,则沿则沿费费用用最小的增广最小的增广链链 以以 去调整去调整 f,得到新可行流得到新可行流 f ，f 就是就是流量为流量为V(f)+的费用最小的可行流。当的费用最小的可行流。当 f 是最大流时，是最大流时，f 就是流量最大的最小费用流，即最小费用最大流。就是流量最大的最小费用流，即最小费用最大流。由于单位流量的费用由于单位流量的费用bij0，所以流量，所以流量=0的可行流的可行流f必是必是费费用最小的可行流用最小的可行流，这样这样剩下的剩下的问题问题就是去就是去寻寻找找关关于于f的的费费用最小的增广用最小的增广链链。为为此，需要根据网此，需要根据网络络D构造一构造一个个赋权赋权有向有向图图W(f)。构造赋权有向图构造赋权有向图W(f)方法如下：方法如下：它的它的顶点顶点就是网络就是网络D的顶点的顶点,W(f)中中弧弧及其及其权权wij 按弧按弧（vi，vj）在）在D中的情形分为：中的情形分为：则构造同向弧（则构造同向弧（vi，vj）,且且wij=bij则构造反向弧（则构造反向弧（vj，vi）,且且wji=-bijvjvi4vj4vi3.0vjvi5.53vivj-3若弧（若弧（vi，vj）的最小费用流量）的最小费用流量fij=0(零零流流弧）弧）若弧若弧(vi，vj）的最小费用流量）的最小费用流量fij=cij(饱和弧饱和弧),费用费用若弧（若弧（vi，vj）的最小费用流量）的最小费用流量0fijcij(非非饱饱和弧和弧)vj4vi3.2则同时构造同向弧（则同时构造同向弧（vi，vj），），且且wij=bij 及及反向弧反向弧 (vj，vi)，且，且wji=-bijvjvi4vivj-4 赋权有向图赋权有向图W（f）的权是单位流量的费用，故）的权是单位流量的费用，故W（f）成为流成为流f 的费用网络图。的费用网络图。如果把费用理解为长度，可知这实际是一个如果把费用理解为长度，可知这实际是一个在在赋权赋权有有向向图图W（f）中）中求最短路的问题。求最短路的问题。寻求寻求关于费用最小的可行流关于费用最小的可行流f 的的费用费用最小的最小的增广链增广链，等价于等价于在在赋权赋权有向有向图图W（f）中寻求从中寻求从vs到到vt的一个最的一个最小费用链。小费用链。二、最小费用最大流算法二、最小费用最大流算法算法步骤：算法步骤：第第1步：确定初始费用最小的可行流步：确定初始费用最小的可行流f 0=0，令，令k=0；第第2步：构造赋权有向图步：构造赋权有向图W（f k）；）；第第3步：在步：在W（f k）中，寻找中，寻找vs到到vt的最短路。的最短路。（1）若不存在最短路（即最短路路长是）若不存在最短路（即最短路路长是），），则则f k 就是最小费用最大流；就是最小费用最大流；（2）若存在最短路，则此最短路即为原网络若存在最短路，则此最短路即为原网络D中中 相应的最小费用增广链相应的最小费用增广链，转入第，转入第4步。步。第第4步：在增广链步：在增广链上对可行流上对可行流f k 进行调整，调整量进行调整，调整量 为为 =min令令得新的可行流得新的可行流f k+1,令令k=k+1，返回第，返回第2步。步。vsv2v34v1vt621132(a)w(f0)例例 求下图所示网络的最小费用最大流。弧旁数字为求下图所示网络的最小费用最大流。弧旁数字为 （bij，cij）。）。v2v3（4，10）v1vsvt（6，2）（2，5）(1，8)（1，7）（3，10）(2，4)解：（解：（1）取初始）取初始可行流可行流f 0=0；（2）按算法要求构造）按算法要求构造长度网络长度网络W（f 0），），求出从求出从vs到到vt的最短路。的最短路。（3）在原网络）在原网络D中，与这中，与这条最短路对应的增广链为条最短路对应的增广链为 =（vs，v2，v1，vt）。）。（3）在原网络）在原网络D中，中，与这条最短路对应与这条最短路对应 的增广链为的增广链为:（4）在）在上进行调整，上进行调整，=5，得，得f 1，如图（如图（b）所示。所示。v2v3（10，0）v1vsvt（2，0）（5，0）(8，0)（7，0）（10，0）(4，0)=（vs，v2，v1，vt）v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)（7，5）（10，0）(4，0)(b)f 1 按照上述算法依次得按照上述算法依次得f 1，f 2，f 3，f 4，流量依次流量依次为为V(f 1)=5，V(f 2)=7，V(f 3)=10，V(f 4)=11，构造相构造相应的增量网络为应的增量网络为W(f 1)，W(f 2)，W(f 3)，W(f 4),如图如图(a),(e),(g),(i)所示。所示。vsv2v34v1vt621132(a)w(f0)v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)（7，5）（10，0）(4，0)(b)f 1V(f 1)=5v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)（7，5）（10，0）(4，0)(b)f 1v2v3（10，2）v1vsvt（2，0）（5，5）(8，5)（7，7）（10，0）(4，0)(d)f 2 V(f 2)=7vt2v2v3v1vs6-2-1-13（c）W（f（1）411v2v3（10，2）v1vsvt（2，0）（5，5）(8，5)（7，7）（10，0）(4，0)(d)f 2 V(f 2)=7 w(f 2)(e)v1vs-1v2v3-46-2-1341vt2v2v3（10，2）v1vsvt（2，0）（5，5）(8，8)（7，7）（10，3）(4，3)(f)f 3 V(f 3)=10v2v3（10，2）v1vsvt（2，0）（5，5）(8，8)（7，7）（10，3）(4，3)(f)f 3 V(f 3)=10vt2v2v3-4v1vs6-2-1-13(g)W(f 3)4-3-2v2v3（10，3）v1vsvt（2，0）（5，4）(8，8)（7，7）（10，4）(4，4)(h)f 4 V(f 4)=11 图（图（i）中，不存在从中，不存在从vs到到vt的最短路，所以的最短路，所以f 4为为最小费用最大流。最小费用最大流。v2v3（10，3）v1vsvt（2，0）（5，4）(8，8)（7，7）（10，4）(4，4)(h)f 4 V(f 4)=11vt-2v2v3-4v1vs6-2-1-13（i）W（f 4）4-32