运输网络最大流问题

运输网络最大流问题一、引言1.应用背景在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题,控制系统中的信息流问题，常见的人流，物流，水流，气流，电流，现金流等。在一定条件下,求解给定系统的最大流量,就是网络最大流问题.2.问题描述连通网络G(V,A)中有m个节点,n条弧,弧eij上的流量上界为cij,求从起始节点vs到终点vt的最大流量的问题就是最大流问题。引例：如下输水网络，南水北调工程，从v1到v6送水，弧旁数字为管道容量，问应当如何输水使得流量最大？v2v451v1v6v3v5108533171131、网络与流设一个赋权有向图D=（V,A）,在V-----图中的节点，中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于A-----图中的弧，D中的每一个弧（vi,vj）∈A,都有一个非负数cij,叫做弧的容量---cij。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，A，C）。弧的容量：是对网络上的每条弧(vi,vj)都给出一个最大的通过能力，记为c(vi,vj)或简写为cij。二、基本概念sts’t’对有多个发点和多个收点的网络,可以另外虚设一个总发点和一个总收点,并将其分别与各发点、收点连起来（见图），就可以转换为只含一个发点和一个收点的网络。所以一般只研究具有一个发点和一个收点的网络•流：加在网络各条弧上的一组负载量,即弧线上的流量•f(vi,vj)：加在弧(vi,vj)上的负载量简记为fij，fij=0.网络上的流：是指定义在弧集合上的一个函数f={f(vi,vj)},注意：弧的流量f(vi,vj)：表示弧(vi,vj)上每单位时间内的实际通过能力弧的容量c(vi,vj)：表示弧（vi,vj)上每单位时间内的最大通过能力零流：网络上所有的fij=0例如下图表示的就是这个网络上的一个流（运输方案），每一个弧上的流量fij就是运输量。例如：f12=1,f13=2,f24=3等等。v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvtv3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt对于实际的网络系统上的流，有几个显著的特点：(1)发点的净流出量和收点的净流入量必相等。(2)每一个中间点的流入量与流出量的代数和等于零。(3)每一个弧上的流量不能超过它的最大通过能力（即容量）称满足下列条件的流为可行流：（1）容量限制条件：对于每一个弧（vi,vj）∈A有0f(vi,vj)c(vi,vj)（简记为0fijcij）A)v,v(A)v,v(tjjtjttj)f(vff2、可行流与最大流（2）平衡条件：总流量v(f)=发点的净输出量v(f)=收点的净输入量-v(f)容量网络的可行流总是存在的，如当所有弧的流均取零，即对所有的i,j,有f(vi,vj)=0就是一个可行流可行流中fij＝cij的弧叫做饱和弧，fij＜cij的弧叫做非饱和弧。fij＞0的弧为非零流弧，fij＝0的弧叫做零流弧。2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)图中谁是零流弧，谁是饱和弧？就是要求一个流{fij},使其流量v(f)达到最大,并且满足0fijcijtiv(f)ts,i0siv(f)ffjiij网络的最大流:•求网络的最大流，即是指满足容量限制条件和平衡条件的条件下，使v(f)值达到最大.容量网络D，若给μ定向为从vs到vt，图上的弧分为两类：凡与μ方向相同的称为前向弧，凡与μ方向相反的称为后向弧，其集合分别用μ+和μ-表示。链的方向：若µ是联结vs和vt的一条链，定义链的方向是从vs到vt。3、增广链stf1c1f4c4f5c5f20f30增广链：一条链中的可行流，如果满足：中的每一条弧都是非饱和弧μ中的每一条弧都是非零流弧μ则称μ为从vs到vt的关于f的一条增广链。stf1c1f4c4f5c5f20f30v2v53-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)}后向弧2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)7766633232211v),v,(v,v),v,(v,v),v,(v,v),v,(v,vμ)v,(v),v,(v),v,(vμ766321)v,(vμ23μ是一个增广链显然图中增广链不止一条4、截集与截量我们在图中画一条线，使所有始点属于Vs，而终点属于Vt，v2v53(3)4（1）8(3）v3v1v4v65（1）10（5)11(66（3017(2)3（2）5（2）=(v1,v2,v3)V1V1=(v4,v5,v6)=(v1,v2,v3)V1V1=(v4,v5,v6)截集为所有被割断的弧线，黄色弧集：)v,v(,)v,v(,)v,v(,)v,v()V,V(5343425211v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2vsv1v2v4v3vt374556378V1)v,v(V2s1)v,v,v,v(Vt4311)v,v(,)v,v(,)v,v()V,V(32421s1118567)V,V(C23241s11截集为所有被割断的弧线，弧线上的容量之和，称作截量。2v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1))v,v(),v,v(),v,v()V,V(75423121设5211,,vvvV则截集为：76432,,,vvvvV不是该集中的弧和而)v,v()v,v(5423截量为242v1v3v4v5v6v7v13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)设，211,vvV则截集为765432,,,,vvvvvV),(),,(),(),(52423121vvvvvvVV截量为20VV截集截集的容量sv1,v2,v3,v4,t(s,1)(s,2)15s,v1v2,v3,v4,t(s,2)(1,2)(1,3)21s,v2v1,v3,v4,t(s,1)(2,4)17s,v1,v2v3,v4,t(1,3)(2,4)18s,v1,v3v2,v4,t(s,2)(1,2)(3,2)(3,t)19s,v2,v4v1,v3,t(s,1)(4,3)(4,t)24s,v1,v2,v3v4,t(2,4)(3,t)14s,v1,v2,v4v3,t(1,3)(4,3)(4,t)25s,v1,v2,v3,v4t(3,t)(4,t)15sv2v4v3v1t7(5)8(8)9(4)5(4)2(0)9(9)6(1)10(8)5(5)对应的截量也不相同，其中截量最小的截集称为最小截集。由于V与V的分解方法不同，所以截集就不相同截集与可行流无关，而只与网络本身有关最小截量是个定值结论2：可行流f*＝{fij*}是最大流，当且仅当D中不存在关于f*的增广链。结论1：即任何一个可行流的流量都不会超过任一截集的容量总结：对最大流问题有下列结论和定理：三、最大流问题的标号法步骤：判断是否存在增广链,并设法把增广链找出来,并予以调整,最终使图中无增广链.此算法从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，最终可以得到网络中的一个最大流。在标号过程中，网络中的点分为两种：已标号的点（分为已检查和未检查）和未标号的点。每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的，以便找出增广链。第二个标号是从上一个标号点到这个标号点的流量的最大允许调整值，是为了用来确定增广链上的调整量θ。1．标号过程标号过程开始，先给vs标号（0，+∞）。这时，vs是标号未检查的点，其它都是未标号点。如果vt有了标号，表示存在一条关于f的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f的增广链。此时，就得到了网络中的一个最大流。例求图10-25的网络最大流，弧旁的权数表示（cij,fij）。解：1.标号过程。1）首先给vs标号（0，+∞）2）看vs:在弧(vs,v2)上,fs2=cs3=3,不具备标号条件。在弧(vs,v1)上,fs1=1cs1=5,故给v1标号（vs,l(v1)),其中l(v1)表示最大可调整量=min[+∞,5–1]=4.v1标号为：（vs,4），此时vs为已检查的标号点。vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(vs,4)(0,+)。（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.v2标号（-v1,1），此时v1为已检查的标号点vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(vs,4)(0,+)(–v1,1)（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(l(v3)=min[l(v2),f32]=min[1,1]=1。(0,+)vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(vs,4)(–v1,1)(-v2,1)(v2,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被标上号，根据标号法，转入调整过程。vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)(1,1)(2,2)(3,0)(5,3)(2,1)(0,+)(vs,4)(–v1,1)(v2,1)(-v2,1)(v3,1)（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被标上号，表示得到一条增广链μ，转入下一步调整过程。2.调整过程利用反向追踪找增广链，调整增广链的流量，去掉旧的标号，对新的可行流重新进行标号。具体做法如下：（1）按照vt和其它已检查的标号点的第一个标号，反向追踪，找出增广链μ，确定调整量θ。（2)得新的可行流。(3)再去掉所有的标号，对新的可行流f’={f’ij},重新进行标号过程，直到找到网络D的最大流为止。iiif,ff,f,所有再令　所有非增广链上的弧vsv1v2v3v4vt(3,3)(5,1)(4,3)(1,1)