网络系统的最小费用最大流问题.ppt

网络中的最小费用最大流问题网络中的最小费用最大流问题二、基本概念与基本定理二、基本概念与基本定理三、寻求最大流的标号法三、寻求最大流的标号法四、最小费用最大流问题四、最小费用最大流问题一、引言一、引言2 网络系统的最大流问题 一、引言 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。3 网络系统的最大流问题图8.23是一个网络vtv3v2v1v4vs1735108611453C Cijij每一个弧旁边的权就是对应的容量（即最大通过能力）。要求指每一个弧旁边的权就是对应的容量（即最大通过能力）。要求指定一个运输方案，使得从定一个运输方案，使得从v vs s到到v vt t的货运量最大，这是寻求网络系的货运量最大，这是寻求网络系统的最大流问题统的最大流问题。4 网络系统的最大流问题二、基本概念与基本定理 定定义义8.5 8.5 设设一一个个赋赋权权有有向向图图D D=（V,AV,A）,在在v v中中指指定定一一个个发发点点（或或源源点点）v vs s和和一一个个收收点点（或或汇汇点点）v vt t,其其他他的的点点叫叫做做中中间间点点。对对于于D D中中的的每每一一个个弧弧（v vi i,v,vj j）A A,都都有有一一个个权权 c cij ij 叫叫做做弧弧的的容容量量。我我们们把把这这样样的的图图 D D 叫叫做做一一个个网网络络系系统统，简简称称网络，记做网络，记做D D=（V V，A A，C C）。）。网网 络络D D上上 的的 流流，是是 指指 定定 义义 在在 弧弧 集集 合合 A A上上 的的 一一 个个 函函 数数f f=f f(v vi i,v,vj j)=)=f fijij f f(v vi i,v,vj j)=)=f fijij叫做弧在叫做弧在(v vi i,v,vj j)上的流量上的流量。6 网络系统的最大流问题网络系统上流流的特点：(1)发点的总流出量和收点的总流入量必相等；(2)每一个中间点的流入量与流出量的代数和等于零；(3)每一个弧上的流量不能超过它的最大通过能力（即容量）。7 网络系统的最大流问题 定定义义8.6 8.6 网络上的一个流 f 叫做可行流，如果 f 满足以下条件 （1）容量限制条件：对每一弧（vi,vj）A,有 0 0 f fij ij c cijij.（2）平衡条件：对于发点vs，有fsj -fjs=v(f)对于收点vt，有ftj -fjt=-v(f)对于中间点，有fij -fji=0 式中v v(f f)叫做这个可行流的流量，即发点的净输出量（或收点的净输入量）8 网络系统的最大流问题任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。网络系统中最大流问题就是在给定的网络上寻求一个可行流f,使其流量v(f)达到最大值。设流f=fij是网络D上的一个可行流，我们把D中fij=cij的弧叫做饱和弧，fij0的弧为非零流弧，fij=0的弧叫做零流弧。9 网络系统的最大流问题设是网络D中连接发点s和收点vt的一条链。定义链的方向是从vs到vt，于是链上的弧被分为两类：一是弧的方向与链的方向相同，叫做前向弧，前向弧的集合记做+。二是弧的方向与链的方向相反，叫做后向弧，后向弧的集合记做-。10 在下图（图在下图（图8.238.23与与8.248.24合并图）中，合并图）中，(v(v4 4,v,v3 3)是是饱和饱和弧弧，其他的弧是，其他的弧是非饱和弧非饱和弧，并且都是，并且都是非零流弧非零流弧。v3v2v1v4vs（17,2）（3,3）（5,2）（10,5）（8,3）（6,3）（11,6）（4,1）（5,1）（3,2）f fijij如图，在链（v vs s,v,v1 1,v,v2 2,v,v3 3,v,v4 4,v,vt t)中，+=(=(v vs s,v,v1 1),(),(v v1 1,v,v2 2),(),(v v2 2,v,v3 3),(),(v v4 4,v,vt t),),-=(=(v v4 4,v,v3 3).).vt 网络系统的最大流问题11 网络系统的最大流问题增广链，如果链 满足以下条件：1在弧（vi,vj）+上，有0fijcij,即+中的每一条弧是非饱和弧。2在弧（vi,vj）-上，有0fij cij,即-中的每一条弧是非零流弧。例如在图8.24中，链=（vs,v1,v2,v3,v4,vt）就是一条增广链。12 网络系统的最大流问题定义8.8 设一个网络D=（V，A，C）。如果点集V被剖分为两个非空集合V1和V1，发点vsV1,收点vtV1,那么将弧集（V1,V1）叫做是分离vs和vt的截集。定义8.9 设一个截集（V1,V1），将截集（V1,V1）中所有的弧的容量的和叫做截集的截量，记做c(V1,V1),亦即c(V1,V1)=cij ,(vi,vj)(V1,V1)设图设图D D=(=(V V，A A，C C)，点集，点集S,T S,T V,S V,S T T=中，将起中，将起点在点在S S，终点在，终点在T T 的所有弧构成的集合，记做（的所有弧构成的集合，记做（S S，T T）。）。13 网络系统的最大流问题 下面的事实是显然的：一个网络D 中，任何一个可行流f的流量v(f)都小于或等于这个网络中任何一个截集(V1,V1)的截量。并且，如果网络上的一个可行流f*和网络中的一个截集（V1*,V1*），满足条件v*(f*)=c(V1*,V1*),那么f*一定是D上的最大流，而（V1*,V1*）一定是D的所有的截集中截量最小的一个（即最小截集）。14 网络系统的最大流问题定理8.8 网络中的一个可行流f*是最大流的充要条件是不存在关于f*的增广链。定理8.9 在一个网络D 中，最大流的流量等于分离vs 和vt 的最小截集的截量。定理定理8.88.8实际上提供了一个实际上提供了一个寻求网络系统最大流的方法寻求网络系统最大流的方法：如：如果网络果网络D D 中有一个可行流中有一个可行流f f，只要判断网络是否存在关于可行流，只要判断网络是否存在关于可行流f f 的增广链的增广链 。如果没有增广链，那么。如果没有增广链，那么f f一定是最大流。如有增广链，一定是最大流。如有增广链，那么可以按照定理那么可以按照定理8.98.9，不断改进和增大可行流，不断改进和增大可行流f f的流量，最终可以的流量，最终可以得到网络中的一个最大流。得到网络中的一个最大流。15 网络系统的最大流问题三、寻求最大流的标号法 从网络中的一个可行流f 出发（如果D中没有f，可以令f 是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。用给顶点标号的方法来定义V1*.在标号过程中，有标号的顶点是V1*中的点，没有标号的点不是V1*中的点。如果vt有了标号，表示存在一条关于f 的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f 的增广链。这样，就得到了网络中的一个最大流和最小截集。16 网络系统的最大流问题 1标号过程 在标号过程中，网络中的点或者是标号点（分为已检查和未检查两种）或者是未标号点。每个标号点的标号包含两部分：第一个标号表示这个标号是从哪一点得到的，以便找出增广链。第二个标号是为了用来确定增广链上的调整量。标号过程开始，先给vs标号（0，+）。这时，vs是标号而未检查的点，其他都是未标号点。一般地，取一个标号未检查点vi，对一切未标号点vj：17 网络系统的最大流问题 1)如果在弧（vi,vj）上，fij0,那么给vj标号（-vi,l(vj)）,其中l(vj)=minl(vi),fji.这时，vj成为标号未检查点。(考虑后向弧)于是vi成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。但是，如果vt被标上号，表示得到一条增广链，转入下一步调整过程。18 2.调整过程 首先按照vt和其他点的第一个标号，利用“反向追踪”的办法，找出增广链。例如，令vt的第一个标号是vk，则弧（vk,vt）在上。再看vk的第一个标号，若是vi，则弧(vi,vk)都在上。依次类推，直到vs为止。这时，所找出的弧就成为网络D的一条增广链。取调整量=l(vt),即vt的第二个标号，网络系统的最大流问题19 fij+，当(vi,vj)+令fij=fij-，当(vi,vj)-fij ,当(vi,vj)|再去掉所有的标号，对新的可行流f=fij,重新进行标号过程，直到找到网络D 的最大流为止。网络系统的最大流问题20 网络系统的最大流问题V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）(Cij,fij)Vt图8.2121例8.8 求图8.21的网络最大流，弧旁的权数表示（cij,fij）。解：用标号法。1.标号过程。（1）首先给vs标号（0，+）（2）检查vs:在弧(vs,v2)上,fs2=cs2=3,不具备标号条件。在弧(vs,v1)上,fs1=10,故 给v2标 号（-v1,l(v2)）,其 中l(v2)=minl(v1),f21=min4,1=1.网络系统的最大流问题22 （4）检查v2:在弧（v2,v4）上，f24=30,故给v3标号（-v2，l(v3),其中l(v3)=minl(v2),f32=min1,1=1。（5）在v3,v4中任意选一个，比如v3,在弧（v3,vt）上，f3t=1c3t=2,故 给vt标 号(v3,l(vt),其 中l(vt)=minl(v3),(c3t-f3t)=min1,1=1.因为vt 被标上号，根据标号法，转入调整过程。网络系统的最大流问题23 2.调整过程。从vt 开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从vs 到vt 的增广链=vs,v1,v2,v3,vt，如图8.22中双箭线所示。不难看出,+=(vs,v1),(v3,vt),-=(v2,v1),(v3,v2),取=l(vt)=1，在上调整f，得到 在+上，fs1+=1+1=2 在+上，f3t+=1+1=2 在-上，f21-=1-1=0 在-上，f32-=1-1=0 其他的fij 不变。网络系统的最大流问题25调整后的可行流f*，如图8.23所示，再对这个可行流重新进行标号过程，寻找增广链：首先给vs标号（0，+），检查vs,给v1标号（vs,3）。检查v1,在弧（v1,v3）上，f13=c13,弧（v2,v1）上，f21=0,均不符合标号过程(1)的条件。因此标号过程无法进行下去，不存在从VS到Vt的增广链，算法结束。这时，网络中的可行流f*即是最大流，最大流的流量V(f*)=fs1+fs2=5.同时，也找出D的最小截集（V1，V1），其中V1是标号的集合，V1是未标号的集合。网络系统的最大流问题26 网络系统的最大流问题V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,2）（2,2）（5,3）（1,0）Vt(0，+)(vs,3)图8.23(Cij,fij)（1,0）27四、最小费用最大流问题 在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。网络系统的最小费用最大流问题28 设一个网络D=（V，A，C），对于每一个弧(vi,vj)A,给定一个单位流量的费用bij 0，网络系统的最小费用最大流问题，是指要寻求一个最大流f，使流的总费用b(f)=bijfij 达到最小。（Vi,Vj）A 网络系统的最小费用最大流问题29在一个网络D中，当沿可行流f 的一条增广链，以调整量=1改进f，得到的新可行流f 的流量，有v(f)=v(f)+1，而此时总费用b(f)比b(f)增加了 b(f)-b(f)=bij(fij-fij)-bij(fij-fij)=bij-bij +-+-将bij-bij 叫做这条增广链的费用。+-网络系统的最小费用最大流问题30网络系统的最小费用最大流问题 如果可行流在流量为v(f)的所有可行流中的费用最小，并且是关于f 的所有增广链中的费用最小的增广链，那么沿增广链调整可行流f，得到的新可行流f，也是流量为v(f)的所有可行流中的最小费用流。依次类推，当f是最大流时，就是所要求的最小费用最大流。31 显然，零流f=0是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f=0开始。下面的问题是：如果已知f是流量为v(f)的最小费用流，那么就要去寻找关于f 的最小费用增广链。对此，重新构造一个赋权有向图W(f)，其顶点是原网络D 的顶点，而将D中的每一条弧(vi,vj)变成两个相反方向的弧（vi,vj）和(vj,vi)，并且定义W(f)中弧的权wij为：网络系统的最小费用最大流问题32 bij ,当fij0wji=+,当fij=0(将权为+的弧从W(f)中略去)即当 0 fij cij 时，成为2条方向相反，权绝对值相等的弧。否则不变。网络系统的最小费用最大流问题33 这样，在网络D中寻找关于f 的最小费用增广链就等于价于在W(f)中寻求从vs到vt的最短路。算法如下：算法开始，取零流f(0)=0.一般地，如果在第K-1步得到最小费用流f(K-1),则构造图W（f(K-1)）。在图W（f(K-1)）中，寻求从vs到vt的最短路。如果不存在最短路(即最短路权是+)，则f(K-1)就是最小费用最大流。如果存在最短路，则在原网络D中得到相对应（一一对应）的增广链，在增广链上对f(K-1)进行调整，取调整量 =minmin(cij-f(k-1)ij),min(f(k-1)ij).+-网络系统的最小费用最大流问题34令 f(k-1)ij+，当(vi,vj)+f(k)ij=f(k-1)ij-，当(vi,vj)-f(k-1)ij ，当(vi,vj)|得到一个新的可行流f(k)，在对f(k)重复以上的步骤，直到D中找不到相对应的增广链时为止。网络系统的最小费用最大流问题35 例8.9 求图8-24 所示网络中的最小费用最大流，弧旁的权是（bij,cij）.网络系统的最小费用最大流问题(bij,Cij)(1,8)vtv3v2vsv1(3,10)(2,4)(6,2)(1,7)(4,10)(2,5)36 解：（1）取初始可行流为零流f(0)=0,构造赋权有向图W(f(0),求出从vs到vt 的最短路(vs,v2,v1,vt),如图8.25a中双箭头所示即为最短路。网络系统的最小费用最大流问题(1)VtV3V2VsV1(3)(2)(6)(1)(4)(2)W(f(0)图8.25a37 （2）在原网络D中，与这条最短路相对应的增广链为=（vs,v2,v1,vt）。（3）在上对f(0)=0进行调整，取=5，得到新可行流f(1)。类似地，按照以上的算法，依次类推，可以得到f(1)，f(2)，f(3)，f(4)，流量分别为5，7，10，11，并且分别构造相对应的赋权有向图W(f(1),W(f(2),W(f(3),W(f(4)。由于在W(f(4)中已经不存在从vs到vt的最短路，因此，可行流f(4)，v(f(1)=11是最小费用最大流。网络系统的最小费用最大流问题vsvtv2v3v1(10,4)(7,1)(8,1)(10,3)(4,2)(5,2)(2,6)(5,2,5)(7,1,5)vsvtv2v3v1(10,4,0)(8,1,5)(10,3,0)(4,2,0)(2,6,0)第第 1 次次 迭迭 代代原图全部是零流弧原图全部是零流弧,保持原边不变保持原边不变,单位费用为权；单位费用为权；所有的权均大于零，所有的权均大于零，构造赋权有向构造赋权有向图并图并求出最短路：求出最短路：恰也是恰也是最小费用增广链最小费用增广链最小费用增广链最小费用增广链。流量调整量流量调整量1 1=min8-0,5-0,7-0=5=min8-0,5-0,7-0=5 总流量总流量f f1 1=5=5最小费用增广链的费用最小费用增广链的费用bbijij=1+2+1=4=1+2+1=4总费用总费用C C1 1=45=20=45=20(容量费用图容量费用图(cij,bij)第第 2 次次 迭迭 代代(3,1)v1vt(5,-2)(2,6)v2v3(10,4)(5,-1)(10,3)(4,2)（2,1）vs（5，-1）(7,1,7)vsvtv2v3v1(10,4,2)(8,1,5)(10,3,0)(4,2,0)(2,6,0)(5,2,5)零流弧保持原边零流弧保持原边,非饱和弧和非零流弧非饱和弧和非零流弧(v(vs s,v,v2 2)和和(v(v1 1,v,vt t)增添反向弧增添反向弧,将饱和弧将饱和弧(v(v2 2,v,v1 1)变成反向弧；变成反向弧；继续继续构造赋权有向图并构造赋权有向图并求出最短路求出最短路:恰也是最小费用增广链恰也是最小费用增广链。流量调整量流量调整量2 2=min10-0,7-5=2=min10-0,7-5=2，总流量总流量=原流量原流量+新增流量新增流量 =5+2=7=5+2=7；最小费用增广链的费用最小费用增广链的费用 bbijij=4+1=5=4+1=5总费用总费用C C2 2=原费用原费用+新增费用新增费用=20+52=30=20+52=30 vsvtv2v3v1(8,4)（2,-4）(5,-1)(7,-1)(10,3)(4,2)(2,6)(5,-2)(3,1)零流弧保持原边，此外的非饱和弧增零流弧保持原边，此外的非饱和弧增添反向弧，饱和弧去掉原边增添反向虚添反向弧，饱和弧去掉原边增添反向虚线弧，变成反向弧线弧，变成反向弧继续继续构造赋权有向图并构造赋权有向图并求出最短路求出最短路:恰也是最小费用增广链。恰也是最小费用增广链。流量调整量流量调整量3 3=min8-5,10-0,4-0=3=min8-5,10-0,4-0=3，总流量总流量=原流量原流量+新增流量新增流量 =7+3=10=7+3=10；最小费用增广链的费用最小费用增广链的费用 bbijij=1+3+2=6=1+3+2=6总费用总费用C C3 3=原费用原费用+新增费用新增费用=30+63=48=30+63=48 第第 3 次次 迭迭 代代(7,1,7)vsvtv2v3v1(10,4,2)(8,1,8)(10,3,3)(4,2,3)(2,6,0)(5,2,5)(2,6)(7,3)(8,4)vsvtv2v3v1(3,-3)(7,-1)(8,-1)(3,-2)（1,2）(2,-4)（5,-2）零流弧保持原边，此外的非饱零流弧保持原边，此外的非饱和弧增添反向弧，饱和弧去掉原和弧增添反向弧，饱和弧去掉原边增添反向虚线弧，变成反向弧；边增添反向虚线弧，变成反向弧；继续继续构造赋权有向图并构造赋权有向图并求出最求出最短路短路:对应的最小费用增广链是对应的最小费用增广链是流量调整量流量调整量4 4=min10-2,5,10-=min10-2,5,10-3,4-3=13,4-3=1，总流量总流量=原流量原流量+新增流量新增流量=10+1=11=10+1=11；最小费用增广链的费用最小费用增广链的费用 bbijij=4-2+3+2=7=4-2+3+2=7总费用总费用C C4 4=原费用原费用+新增费用新增费用 =48+71=55=48+71=55。由于总流量由于总流量1111已达到最大流量，故停已达到最大流量，故停止迭代，止迭代，当前的可行流图即最大流图。当前的可行流图即最大流图。第第 4 次次 迭迭 代代(7,1,7)vsvtv2v3v1(10,4,3)(8,1,8)(10,3,4)(4,2,4)(2,6,0)(5,2,4)例题总结：例题总结：1、将饱和弧反向；、将饱和弧反向；2、将非饱和非零流弧加一反向弧；、将非饱和非零流弧加一反向弧；3、零流弧不变；、零流弧不变；4、所有正向弧的权为该弧的费用，反向弧、所有正向弧的权为该弧的费用，反向弧的权为该弧费用的相反数。的权为该弧费用的相反数。求最小费用求最小费用-最大流问题最大流问题求下图中网络从 到 的最小费用最大流，图中弧上的数字为 。vsv2v3v4v5vt练习作业练习作业 vsv2v3v4v5vt(0)求网络的最大流量由前面计算知，。将0流作为初始可行流。扩展费用网络与原网络相同(1)第一次迭代：用Ford算法求最短增广链，路线是vsv3v5vtvsv2v3v4v5vt调整流量：在增广链上有：在初始可行流的基础上调整流量得到新的可行流，刷新网络图(2)第二次迭代扩展费用网络vsv2v3v4v5vt饱和弧只能减小流量，单位费用减少3（1）流量还可增加3，单位费用6；（2）流量也可减小，当前流量为6，每减单位流量，费用节省6。（1）流量还可增加4，单位费用1；（2）流量也可减小，当前流量为6，每减单位流量，费用节省1。用Ford算法求最短增广链，路线是vsv2v5vtvsv2v3v4v5vt在原可行流基础上调整流量得到新的可行流，刷新网络图(3)第三次迭代扩展费用网络vsv2v3v4v5vt用Ford算法求最短增广链，路线是vsv2v4vt调整流量：在增广链上有：在初始可行流的基础上调整流量得到新的可行流，刷新网络图vsv2v3v4v5vt(3)第四次迭代扩展费用网络用Ford算法求最短增广链，路线是vsv3v4vtvsv2v3v4v5vtvsv2v3v4v5vt调整流量：在增广链上有：在初始可行流的基础上调整流量得到新的可行流，刷新网络图