运筹学课件第四节最大流问题

运筹学课件第四节最大流问题第一页，共二十八页，2022年，8月28日

引言在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。第二页，共二十八页，2022年，8月28日图是联结某个起始地vs和目的地vt的交通运输网，每一条弧vi

旁边的权cij表示这段运输线的最大通过能力，货物从vs运送到vt.要求指定一个运输方案，使得从vs到vt的货运量最大，这个问题就是寻求网络系统的最大流问题。一、最大流有关概念

连通网络G(V,E)有m个节点,n条弧,弧eij上的流量上界为cij,求从起始节点vs到终点vt的最大流量。vtv3v2v1v4vs1735108611453Cij第三页，共二十八页，2022年，8月28日

定义20

设一个赋权有向图G=（V,E）,对于G中的每一个边（弧）（vi,vj）∈E,都有一个非负数cij叫做边的容量。在V中一个入次为零的点称为发点vs，一个出次为零的点称为收点vt,其它的点叫做中间点。我们把这样的图G叫做一个容量网络，记做G=（V，E，C）。

网络G上的流，是指定义在边(vi,vj)上有流量fij，称集合f={fij}为网络G上的一个流，f为可行流。第四页，共二十八页，2022年，8月28日网络上的一个流f

叫做可行流，如果f满足以下条件：

（1）容量条件：对于每一个弧（vi,vj）∈E,有0fij

cij

.

（2）平衡条件：对于发点vs,收点vt有对于中间点，有第五页，共二十八页，2022年，8月28日

任意一个网络上的可行流总是存在的。例如零流w(f)=0,就是满足以上条件的可行流。网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量w(f)达到最大值。设流f={fij}是网络G上的一个可行流。我们把G中fij=cij的弧叫做饱和弧，fij<cij的弧叫做不饱和弧，fij>0的弧为非零流弧，fij=0的弧叫做零流弧.

最大流问题实际是个线性规划问题。

其中发点的总流量（或收点的总流量）

w

叫做这个可行流的总流量。第六页，共二十八页，2022年，8月28日v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt网络上的一个流（运输方案），每一个弧上的流量fij就是运输量。例如fs1=5,fs2=3,f13=2等等。第七页，共二十八页，2022年，8月28日定义21

设一个网络G=（V，E，C），vs、vt为发和收点，边集为E的子集，将G分成2个子图G1,G2;其顶点集合分别为:,发点vs∈S,收点vt∈

/S

,满足1.G=（V，E-）不连通；2.为的真子集，而G=（V，E-）连通；那么为G的割集，记为=(S,)。割集(S,)所有始点在S，终点在的容量之和，称为(S,)的割集容量，记为C(S,)。第八页，共二十八页，2022年，8月28日vtvsv1v2v3v442443322231边集{(vs,v1),(vs,v3),(vs,v4)}边集{(vs,v1),(v1,v3),(v2,v3),(v3,vt)}为图的割集，割集容量分别为11，9第九页，共二十八页，2022年，8月28日二、最大流-最小割定理定理10：设f为网络G=（V，E，C）的任一个可行流，流量为W,(S,)是分离vsvt的任一个割集，则有WC(S,).定理11：最大流-最小割定理:任一个网络G=（V，E，C）,从vs到vt的最大流的流量等于分离vsvt的最小割的容量。定义22：设μ是网络G中连接发点νs和收点vt的一条链。定义链的方向是从νs到

vt

，于是链μ上的边被分为两类：一类是边的方向与链的方向相同，叫做前向边，前向边的集合记做μ+。二类是边的方向与链的方向相反，叫做后向边，后向边的集合记做μ–。第十页，共二十八页，2022年，8月28日

如果链μ满足以下条件：

1．在边（vi,vj）∈μ+上，有0fij<cij。

2．在边（vi,vj）∈μ–上，有0<fijcij,。则称μ为从νs到

vt可增广链。在链（vs,v1,v2,v3,v4,vt)中，μ+={(vs,v1),(v1,v2),(v2,v3),(v4,vt)},μ–

={(v4

,v3)}.vtvsv1v2v3v442443322231第十一页，共二十八页，2022年，8月28日定理11提供了一个寻求网络系统最大流的方法。如果网络G中有一个可行流f，只要判断网络是否存在关于可行流f的增广链。如果没有增广链，那么f一定是最大流。如有增广链，那么可以按照定理中必要性，不断改进和增大可行流f的流量，最终可以得到网络G中的一个最大流。推论：网络中的一个可行流f*是最大流的充分必要条件是，不存在关于f*的增广链。在一个网络G中，最大流的流量等于分离vs和vt

的最小割集的割量。第十二页，共二十八页，2022年，8月28日

三、标号法

从网络中的一个可行流f出发（如果G中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。如果vt有了标号，表示存在一条关于f的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f的增广链。这样，就得到了网络中的一个最大流和最小割集。第十三页，共二十八页，2022年，8月28日1．

标号过程在标号过程中，网络中的每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的，以便找出增广链；第二个标号是为了用来确定增广链上的调整量δ

。标号过程开始，先给vs标号（∆，+∞），一般地，取一个标号顶点vi，对vi所有未标号的邻接点vj按照下面条件进行处理：第十四页，共二十八页，2022年，8月28日

（1）如果在弧（vi,vj）上，fij<cij,那么给vj标号（+vi,δ(vj)

）.其中δ(vj)=min[cij–fij,δ(vi)]。（2）如果在弧（vj,vi）上，fji>0,那么给vj标号（-vi,δ(vj)

）.其中δ

(vj)=min[fji,

δ(vi)]。重复以上步骤，如果收点Vt被标号或不再有顶点可标号为止，则标号法结束。这时的可行流就是最大流。第十五页，共二十八页，2022年，8月28日

2.调整过程令

但是，如果vt被标上号，表示得到一条增广链μ，转入下一步调整过程。3.再去掉所有的标号，对新的可行流f’={f’ij},重新进行标号过程，直到找到网络G的最大流为止。第十六页，共二十八页，2022年，8月28日vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)例求图的网络最大流，弧旁的权数表示（cij,fij）。第十七页，共二十八页，2022年，8月28日vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)解：用标号法。

1.标号过程。

（1）首先给vs标号（∆，+∞）

（2）检查vs邻接点v1,v2,v3:v2点满足（vs,v2)∈E,且fs2=2<cs2=4,δv2=min[2,+∞]=2,给v2以标号(+vs,2);v3点满足（vs,v3)∈E,且fs3=2<cs3=3,δv3=min[1,+∞]=1,给v3以标号(+vs,1);(∆，+∞)(+vs,2)(+vs,1)第十八页，共二十八页，2022年，8月28日（3）检查v2邻接点v5,v6:v5点满足（v2,v5)∈E,且f25=0<c25=3,δv5=min[3,2]=2,给v5以标号(+v2,2);

vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)(∆，+∞)(+vs,2)(+vs,1)(+v2,2)第十九页，共二十八页，2022年，8月28日（4）检查v5邻接点v1,vt:v1点满足（v1,v5)∈E,且f15=3>c15=0,δv1=min[3,2]=2,给v1以标号(-v5,2);vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)(∆，+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)第二十页，共二十八页，2022年，8月28日（5）检查v1邻接点v4:v4点满足（v1,v4)∈E,且f14=2<c14=5,δv4=min[3,2]=2,给v4以标号(+v1,2);vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)(∆，+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)第二十一页，共二十八页，2022年，8月28日（6）检查v4邻接点vt:vt点满足（v4,vt)∈E,且f4t=2<c4t=4,δvt=min[2,2]=2,给vt以标号(+v4,2);Vt得到标号，说明已经得到一条可增广链，标号过程结束。vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)(∆，+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)(+v4,2)第二十二页，共二十八页，2022年，8月28日开始调整vsv2v5vtv4v1v6v3(5,5)(3,2)(3,3)(4,2)(5,4)(3,3)(2,2)(5,2)(4,2)(2,2)(∆，+∞)(+vs,2)(+vs,1)(+v2,2)(-v5,2)(+v1,2)(+v4,2)第二十三页，共二十八页，2022年，8月28日2.调整过程从vt开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从vs到vt的增广链μ，如图G中虚线所示。不难看出,μ+={(vs

,v2),(v1

,v4),(v4

,vt)},μ–

={(v5

,v1)},取δ

=δvt=2

，在μ上调整f，得到f*=f4t+δvt=2+2=4

在μ+上f14+δvt=2+2=4

在μ+上f25+δvt=0+2=2

在μ+上fs2+δvt=2+2=4

在μ+上

f15–δvt=3–2=1

在μ-上其它的不变第二十四页，共二十八页，2022年，8月28日vsv2v5vtv4v1v6v3(5,5)(3,2)(3,1)(4,4)(5,4)(3,3)(2,2)(5,4)(4,4)(2,2)（

∆，+∞）（

+vs

，1）(3,2)重新开始标号，寻找可增广链，当标到V3，与VS,V3相连的V1,V2,V6不满足标号条件，标号无法进行，vt得不到标号。流量：w=fs1+