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

网络中的最小费用最大流问题二、基本概念与基本定理三、寻求最大流的标号法四、最小费用最大流问题一、引言2网络系统的最大流问题一、引言在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。3网络系统的最大流问题图8.23是一个网络vtv3v2v1v4vs1735108611453Cij每一个弧旁边的权就是对应的容量（即最大通过能力）。要求指定一个运输方案，使得从vs到vt的货运量最大，这是寻求网络系统的最大流问题。4网络系统的最大流问题二、基本概念与基本定理定义8.5设一个赋权有向图D=（V,A）,在v中指定一个发点（或源点）vs和一个收点（或汇点）vt,其他的点叫做中间点。对于D中的每一个弧（vi,vj）∈A,都有一个权cij叫做弧的容量。我们把这样的图D叫做一个网络系统，简称网络，记做D=（V，A，C）。网络D上的流，是指定义在弧集合A上的一个函数f={f(vi,vj)}={fij}f(vi,vj)=fij叫做弧在(vi,vj)上的流量。6网络系统的最大流问题网络系统上流的特点：(1)发点的总流出量和收点的总流入量必相等；(2)每一个中间点的流入量与流出量的代数和等于零；(3)每一个弧上的流量不能超过它的最大通过能力（即容量）。7网络系统的最大流问题定义8.6网络上的一个流f叫做可行流，如果f满足以下条件（1）容量限制条件：对每一弧（vi,vj）∈A,有0fijcij.（2）平衡条件：对于发点vs，有∑fsj-∑fjs=v(f)对于收点vt，有∑ftj-∑fjt=-v(f)对于中间点，有∑fij-∑fji=0式中v(f)叫做这个可行流的流量，即发点的净输出量（或收点的净输入量）8网络系统的最大流问题•任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。•网络系统中最大流问题就是在给定的网络上寻求一个可行流f,使其流量v(f)达到最大值。•设流f={fij}是网络D上的一个可行流，我们把D中fij=cij的弧叫做饱和弧，fijcij的弧叫做非饱和弧，fij0的弧为非零流弧，fij=0的弧叫做零流弧。9网络系统的最大流问题•设μ是网络D中连接发点νs和收点vt的一条链。定义链的方向是从vs到vt，于是链μ上的弧被分为两类：一是弧的方向与链的方向相同，叫做前向弧，前向弧的集合记做μ+。二是弧的方向与链的方向相反，叫做后向弧，后向弧的集合记做μ-。在下图（图8.23与8.24合并图）中，(v4,v3)是饱和弧，其他的弧是非饱和弧，并且都是非零流弧。v3v2v1v4vs（17,2）（3,3）（5,2）（10,5）（8,3）（6,3）（11,6）（4,1）（5,1）（3,2）fij如图，在链（vs,v1,v2,v3,v4,vt)中，μ+={(vs,v1),(v1,v2),(v2,v3),(v4,vt)},μ-={(v4,v3)}.vt网络系统的最大流问题11网络系统的最大流问题增广链，如果链μ满足以下条件：1．在弧（vi,vj）∈μ+上，有0≤fijcij,即μ+中的每一条弧是非饱和弧。2．在弧（vi,vj）∈μ-上，有0fij≤cij,即μ-中的每一条弧是非零流弧。例如在图8.24中，链μ=（vs,v1,v2,v3,v4,vt）就是一条增广链。12网络系统的最大流问题•定义8.8设一个网络D=（V，A，C）。如果点集V被剖分为两个非空集合V1和V1，发点vs∈V1,收点vt∈V1,那么将弧集（V1,V1）叫做是分离vs和vt的截集。•定义8.9设一个截集（V1,V1），将截集（V1,V1）中所有的弧的容量的和叫做截集的截量，记做c(V1,V1),亦即c(V1,V1)=∑cij,(vi,vj)∈(V1,V1)设图D=(V，A，C)，点集S,TV,S∩T=ф中，将起点在S，终点在T的所有弧构成的集合，记做（S，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.8实际上提供了一个寻求网络系统最大流的方法：如果网络D中有一个可行流f，只要判断网络是否存在关于可行流f的增广链。如果没有增广链，那么f一定是最大流。如有增广链，那么可以按照定理8.9，不断改进和增大可行流f的流量，最终可以得到网络中的一个最大流。15网络系统的最大流问题三、寻求最大流的标号法•从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。•用给顶点标号的方法来定义V1*.在标号过程中，有标号的顶点是V1*中的点，没有标号的点不是V1*中的点。如果vt有了标号，表示存在一条关于f的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f的增广链。这样，就得到了网络中的一个最大流和最小截集。16网络系统的最大流问题1．标号过程在标号过程中，网络中的点或者是标号点（分为已检查和未检查两种）或者是未标号点。每个标号点的标号包含两部分：第一个标号表示这个标号是从哪一点得到的，以便找出增广链。第二个标号是为了用来确定增广链上的调整量θ。标号过程开始，先给vs标号（0，+∞）。这时，vs是标号而未检查的点，其他都是未标号点。一般地，取一个标号未检查点vi，对一切未标号点vj：17网络系统的最大流问题1)如果在弧（vi,vj）上，fijcij,那么给vj标号（vi,l(vj)），其中l(vj)=min[l(vi),cij-fij].这时，vj成为标号未检查的点。(考虑前向弧)2)如果在弧（vj,vi）上，fji0,那么给vj标号（-vi,l(vj)）,其中l(vj)=min[l(vi),fji].这时，vj成为标号未检查点。(考虑后向弧)于是vi成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。但是，如果vt被标上号，表示得到一条增广链μ，转入下一步调整过程。182.调整过程首先按照vt和其他点的第一个标号，利用“反向追踪”的办法，找出增广链。例如，令vt的第一个标号是vk，则弧（vk,vt）在μ上。再看vk的第一个标号，若是vi，则弧(vi,vk)都在μ上。依次类推，直到vs为止。这时，所找出的弧就成为网络D的一条增广链μ。取调整量θ=l(vt),即vt的第二个标号，网络系统的最大流问题19fij+θ，当(vi,vj)∈μ+令f'ij=fij-θ，当(vi,vj)∈μ-fij,当(vi,vj)|μ•再去掉所有的标号，对新的可行流f'={f'ij},重新进行标号过程，直到找到网络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=1cs1=5,故给v1标号(vs,l(v1)),其中l(v1)=min[l(vs),(cs1-fs1)]=min[+∞,5-1]=4.（3）检查v1:在弧（v1,v3）上,f13=c13=2,不具备标号条件.在弧(v2,v1)上,f21=10,故给v2标号（-v1,l(v2)）,其中l(v2)=min[l(v1),f21]=min[4,1]=1.网络系统的最大流问题22（4）检查v2:在弧（v2,v4）上，f24=3c24=4,故给v4标号（v2,l(v4)），其中l(v4)=min[l(v2),(c24-f24)]=min[1,1]=1.在弧（v3,v2)上，f32=10,故给v3标号（-v2，l(v3)),其中l(v3)=min[l(v2),f32]=min[1,1]=1。（5）在v3,v4中任意选一个，比如v3,在弧（v3,vt）上，f3t=1c3t=2,故给vt标号(v3,l(vt)),其中l(vt)=min[l(v3),(c3t-f3t)]=min[1,1]=1.因为vt被标上号，根据标号法，转入调整过程。网络系统的最大流问题232.调整过程。从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(f'ij-fij)-∑bij(f'ij-fij)=∑bij-∑bijμ+μ-μ+μ-将∑bij-∑bij叫做这条增广链的费用。μ+μ-网络系统的最小费用最大流问题30网络系统的最小费用最大流问题如果可行流在流量为v(f)的所有可行流中的费用最小，并且是关于f的所有增广链中的费用最小的增广链，那么沿增广链μ调整可行流f，得到的新可行流f'，也是流量为v(f')的所有可行流中的最小费用流。依次类推，当f'是最大流时，就是所要求的最小费用最大流。31•显然，零流f={0}是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f={0}开始。下面的问题是：如果已知f是流量为v(f)的最小费用流，那么就要去寻找关于f的最小费用增广链