最大流问题

第1页第八章图与网络分析•图的基本概念与模型•树图和图的最小部分树•最短路问题•网络最大流问题•最小费用最大流问题第2页第八章图与网络分析•图的基本概念与模型•树图和图的最小部分树•最短路问题•网络最大流问题•最小费用最大流问题第3页网络最大流问题50年代福特（Ford）、富克逊（Fulkerson）建立的“网络流理论”，是网络应用的重要组成部分。如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径，我们也可以将一个有向图看作一个流网络来解决另一类型的问题。流网络比较适合用来模拟液体流经管道、电流在电路网络中的运动、信息网络中信息的传递等等类似的过程。第4页问题的提出在一个输油管网中，有生产石油的油井、储存石油的油库、转运石油的中间泵站，同时，还有各种口径不同的输油管。当一个输油管网给定后，单位时间内最多可把多少石油从油井输送到油库？具体方案如何？分析：就输油管网络问题，可用顶点表示油井、油库和中间泵站，用有向边表示输油管，用有向边上的权表示单位时间沿相应的输油管可以输送石油的最大数量（容量）。第5页如果我们把图看做输油管道网，为起点，为终点，为中转站，边上的数表示该管道的最大输油能力，问应该如何安排各管道输油量，才能使从到的总输油量最大？tvsv1234,,,vvvvtvsv问题的提出管道网络中每边的最大通过能力即容量是有限的，实际流量也不一定等于容量，上述问题就是要讨论如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通常称为最大流问题。vsv1v3vtv2v48799562510第6页容量发点（源）收点（汇）中间点容量网络(,)ijDvv的每条弧上有非负数的点一个入次为0sv的点一个出次为0tv其余点(,,)DVACijc网络有向图D=（V，A，C）网络上流的基本概念vsv1v3vtv2v48799562510流(,)ijijvvf对D中任一弧都给定一个实际流量}{ijff集合(1)(2)满足下面条件的流：容量限制条件中间点平衡条件ijijcf0jijkkiff输出量中间点的输入量()()sjjtjjvfstvfff用表示网络中从的流量vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)0{0}f任何网络必存在可行流，如流量为的可行流：运输问题中，每个运输方案就是一个流可行流第8页()ijfvf在容量网络中，寻求一个流使其流量最大网络最大流问题ijijcf0()0()ijjivfffvf(,)tjvvA()is(,)ist()it且满足此为一个特殊的线性规划问题，将会看到利用图的特点，解决这个问题的方法要比单纯形法较为直观方便。第9页设是网络D=（V，A，C）的一个可行流（v1，v2）是饱和的2、如果0≤fijcij，该弧是非饱和弧；（v1，v2）是不饱和的间隙为12=c12-f12=5-3=21、如果fij=cij，该弧是饱和弧；弧关于流的分类{}ijfffij=5cij=5v1v2fij=3cij=5v1v2第10页设是网络D=（V，A，C）的一个可行流（v1，v2）是0流弧4、如果fij0，该弧是非0弧；（v1，v2）是非0弧3、如果fij=0，该弧是0流弧；弧关于流的分类{}ijfffij=0cij=5v1v2fij0cij=5v1v2第11页链及可增广链•链在最大流问题中，研究的是有向网络图。但是在求最大流的方法中，则要使用无向网络中的链。,ststvvvvD中，若为从到的一条链，给定向为从到前向弧集：与同向后向弧集：与反向，vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)(,)'(,)ijijijijijfvvffvvf非增广链上的弧(,)(,)min{}0ijijijijijijijcfvvfvv(')()vfvf11fc30f22fc0(,)0(,)ijijijijijijstffcvvfcvvfvv是可行流，每一个若每一个则称为关于可行流的从到的可增广链。非0流弧•可增广链10nfnnfcvsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)非饱和弧第13页11VV割集和割集的容量)\(111VVVV和11,VvVvts1V1V),(11VV设有网络D={V，A，C}，点vs与点vt的是集合V中的任意两点，若点集V被剖分成两个非空集合，使，记以中的点为始点，的A中弧的集合记为则称这个弧的集合是分离点vs与点vt的割集（又称截集）。中的点为终点割集的容量是割集中各弧的容量之和，用表示。11(,)cVV1324{(,),(,)}vvvv112134{,,},{,,}tVsvvVvvv割集的容量为9+9=18割集KK割集的意义：若把某一割集的弧从网络中丢去，则从vs到vt便不存路，即割集是从vs到vt的必经之道！这里(v3,v2)不属于此割集vsv1v3vtv2v48(8)7(5)9(4)5(5)6(1)2(0)5(4)10(8)9(9)考虑KK的不同画法vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)1234,,,,vvvvt34{(,),(,)}vtvt12(,),(,)svsv1{,}sv{}s2{,}sv12{,,}svv13{,,}svv24{,,}svv123{,,,}svvv124{,,,}svvv1234{,,,,}svvvv234,,,vvvt134,,,vvvt134,,,vvvt24,,vvt13,,vvt1234,,,,vvvvt4,vtt21213(,),(,),(,)svvvvv124(,),(,)svvv1324(,),(,)vvvv212323(,),(,),(,),(,)svvvvvvt1434(,),(,),(,)svvvvt243(,),(,)vvvt13434(,),(,),(,)vvvvvt152117181924142515VV割集割集容量由于有限网络的割集只有有限多个，则截集容量的集合是有限的实数集合，令称割集容量为C0的割集为D的最小割集。（瓶颈）11(,)CVV011{(,)}CminCVV第15页111111(,,),(),(,),(,)()(,)ststfDVACvvWfVVvvVVWfCVV设为网络的任一可行流(为发点为收点），流量为是分离的任一割集，割集容量为C则有基本定理(可行流与割集的关系)最大流-最小割定理：的最小割的容量分离的最大流的流量到从中，任一个网络tstsvvvvG,的可增广链到不存在从是最大流可行流tsvvf构造法证明第16页这样就得到了一个寻求最大流的方法(算法思想)：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到了最大流。沿着这条链从vs到vt输送流，还有潜力可挖，只需按照调整方法，就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。可增广链的实际意义求解最大流的标号算法：1.()1(,)2,:(),min{,},(,)()0,min{,},(,)(3)(2siijjiijijjijijiijjijijjiiijvvvvavvfccfvbvvffv标号过程寻找可增广链：（）给以标号（）对已标号的考虑的所有未标号的邻接点若是发出的前向非饱和弧的终点，即令标号为；否则不标号对是发出的后向非零弧的起点，即令标号为；否则不标号重复')2.121'tstijtijijtijvvvfffff直到若未得到标号，说明不存在到的增广链；否则按如下方法调整。调整过程（增加流量）：增广链上的前向弧（）令增广链上的后向弧不在增广链上（）去掉所有标号，回到第步，对可行流重新标号。(')()twfwf则有1v2v3vb)接着检查与相邻接的点1v3v2v4v5vsvtv6v)5,5()2,3()2,4()2,5()2,4()4,5()3,3()3,3()0,3()2,2()2,2(),(已饱和，流量不可再增。再检查，可调整量为4-2=2，可提供量+∞，取调整量1v2v2min{42,}2a)先给标号（∆，+∞）1）寻找可增广链：sv1v3v2v4v5vsvtv6v)5,5()2,3()2,4()2,5()2,4()4,5()3,3()3,3()0,3()2,2()2,2(),(同理，给标号3v)1,(svc)下对已标号点（可望调整点）接着向下检查。已饱和。再检查与相邻接且未标号的点6v2v,5v6v给标号，其中表示的所调整量2来自，且为正向流（向前流）。)2,(svsv2vsv2v)2,(sv)1,(sv调整量为1v3v2v4v5vsvtv6v)5,5()2,3()2,4()2,5()2,4()4,5()3,3()3,3()0,3()2,2()2,2(),()2,(sv)1,(sv5min{30,2}2)2,(2v5v给标号为)2,(2v1v3v2v4v5vsvtv6v)5,5()2,3()2,4()2,5()2,4()4,5()3,3()3,3()0,3()2,2()2,2(),()2,(sv)1,(sv)2,(2v可令调整量为1min{3,2}2)2,(5v给标号为)2,(5v1v表示可控量，反方向流量。5v,015fd)检查与相邻接且未标号的点，。而对来讲是流入，现欲增加流出量，应该压缩的流入量，只要的流入量1vtv1v5v1v1v3v2v4v5vsvtv6v)5,5()2,3()2,4()2,5()2,4()4,5()3,3()3,3()0,3()2,2()2,2(),()2,(sv)1,(sv)2,(2v)2,(5vf)下面检查与相邻接且未标号的点，同理，调整量：1v4v4min{52,2}2给标号为).2,(1v4v)2,(1v)2,(4vg)最后，给标号tv).2,(4vmin{42,2}2t1v3v2v4v5vsvtv6v)5,5()2,3()2,4()2,5()2,4()4,5()3,3()3,3()0,3()2,2()2,2(),()2,(sv)1,(sv)2,(2v)2,(5v)2,(1v)2,(4v2）调整流量：从到所画出的红线即为可增广链。沿该可增广链，从倒推，标“＋”号的在实际流量上加上该调整量，标“－”符号的在实际流量上减去该调整量。完成调整过程。svtvtv反向追踪1v3v2v4v5vsvtv6v)5,5()2,3()2,4()2,5()2,4()4,5()3,3()3,3()0,3()2,2()2,2(),()2,(sv)1,(sv)2,(2v)2,(5v)2,(1v)2,(4v1v3v2v4v5vsvtv6v)5,5()2,3()4,4()4,5()4,4()4,5()3,3()1,3()2,3()2,2()2,2(),()2,(sv)1,(sv)2,(2v)2,(5v)2,(1v)2,(4v1v3v2v4v5vsvtv6v)5,5()2,3()4,4()4,5()4,4()4,5()3,3()1,3()2,3()2,2()2,2(),()1,(sv当标到时，与，相邻接的点，，都不满足标号条件，标号无法继续，且没有完成标号。此时最大流量即为所求。)1,(svsv3v1v2v6vtv***12354211ssswf