求解网络最大流问题的数值算法

求解网络最大流问题的数值算法

0最大流问题的求解许多文献详细讨论了网络最大流的问题，并提供了解决方案，如“标准法”、格式法、sd-kapp算法和迪卡算法。然而，这些算法很难实现编程。文给出了一个典则型运输网络中求最小费用最大流的数值算法X6。网络最大流问题并没有“费用”的要求,可以通过把每条弧单位流量的费用人为地定义为零的办法,把它转化为典则型运输网络中求最小费用最大流问题,再利用文中的算法X6求解。这样处理尽管易于编程实现,但是当给定网络不是典则型运输网络(特别是无向网络)时,首先得采用添加虚顶点的办法把它转化为典则型运输网络,这就大大增加了计算机的计算量和初始准备的工作量,而其中一些计算和准备工作完全可以避免。本文利用文中(p191)定理8.9、最大流量最小截量定理以及文中的算法X2,通过改进[7,8,9,10,11,12,13,14]建立了求解网络最大流问题的数值算法X5,避免了多余的计算和初始准备工作,易于编程实现,且有很好的收敛性。本文作者已将算法X5用VisualBasic5.0在计算机上实现,成为本文作者设计的名为《规划系统》的应用软件的名叫《网络最大流问题》的功能模块;利用它,只要输入按本文定义的容量矩阵及相关信息,就能方便快捷地求出网络最大流和最小截。文中有关概念和记号参见文献[1,2,3,4,5,6,7,8,9,10,11,12,13,14]。1运输网络的计算定义1把简单赋权连通有向图N=(V,A,C)称为运输网络,其中V={1,2,…,n}为N中顶点的集合,顶点s是N的源(发点),顶点t是N的沟(收点),A={aij|弧aij=(i,j)存在}为N中弧的集合,C=(Cij)n×n为N的容量矩阵,Cij表示从顶点i到顶点j的直接运输通过能力。当i=j时,规定Cij=+∞。当i≠j时,如果不存在弧aij=(i,j),规定Cij=0;否则规定Cij=C(aij)>0,其中C(aij)表示弧aij的容量。定义2对于运输网络N=(V,A,C),每一条弧(i,j)∈A都给定一个非负数fij(称为弧(i,j)的流量),这一组数满足下面三个条件时,称为N的可行流,用f表示它。(1)每一弧有fij≤Cij。(2)除发点s和收点t以外所有的中间点i必有∑jfij=∑kfki(3)对于源s和沟t有∑ifsi-∑ifis=∑jfjt-∑jftj=v(f)这个数v(f)叫做f的流量,且从发点s发出的量等于进入收点t的量。最大流就是使N中从发点s送往收点t的流量v(f)达到最大的可行流f。定义3给定运输网络N=(V,A,C),若顶点集V被剖分为两个非空集合V1和¯V1,使s∈V1‚t∈¯V1,则把始点在V1终点在¯V1中的所有弧构成的集合(记为(V1‚¯V1))称为(分离s和t的)截集。给一截集(V1‚¯V1),把截集(V1‚¯V1)中所有弧的容量之和称为这个截集的容量(简称为截量),记为C(V1‚¯V1)。把容量最小的截集称为最小截。定义4设N=(V,A,C)是运输网络,其中V={1,2,…,n}。f={fij}是N的一个可行流。定义N的流矩阵F=(Fij)n×n如下:当i=j时,令Fij=0。当i≠j时,如果不存在弧aij=(i,j),令Fij=0;否则令Fij=fij。引理1可以按以下算法求运输网络N=(V,A,C)中从顶点s到顶点t的最大容量路或判定这样的路不存在:step1(准备)令Uij:=Cij,Sij:=j(i,j=1,2,…,n),k:=1。step2(迭代)对1≤i,j≤n。如果Uij<min{Uik,Ukj},则令Uij:=min{Uik,Ukj},Sij:=Sik;否则Uij、Sij保持不变。step3(循环判定)如果k=n,转step4;否则,令k:=k+1,转step2。step4(求出N中从顶点s到顶点t的最大容量路或判定N中这样的路不存在)如果Ust=0,则N中从顶点s到顶点t的最大容量路不存在,停止;否则令1:=s,r:=Sst,Pst:=ϕ。step5令Pst:=Pst∪(1,r)。step6如果r=t,则N中从顶点s到顶点t的最大容量路为Pst,且最大容量路Pst的容量为Ust,停止;否则令1:=r,r:=Srt,转step5。引理2设f*是运输网络N=(V,A,C)中的最大流。利用下面的方法来定义V*1:令s∈V*1;若i∈V*1,且f*ij<Cij,则令j∈V*1;若i∈V*1,且f*ji>0,则令j∈V*1。则t∉V*1,截集(V*1‚¯V*1)为N的最小截,其中¯V*1=V\V*1。定理1给定运输网络N=(V,A,C),则可按以下算法求N的最大流和最小截:step1给定初始可行流f=0(零流),取N关于流f的伴随网络N(f)=N,设W=(Wij)n×n为N(f)的容量矩阵。step2利用引理1判定N(f)是否有从顶点s到顶点t的最大容量路Pst。如果存在Pst,利用引理1求出Pst的容量θ(θ>0),转step3;否则f就是N的最大流,转step4。step3利用引理1沿Pst按以下方法调整N的流f和修正N(f)的容量:对任意弧(1,r)∈Pst,如果Fr1=0,令W1r:=W1r-θ,Wr1:=Wr1+θ,F1r:=F1r+θ;否则,令W1r:=W1r-θ+min{θ,Fr1},Wr1:=Wr1+min{θ,Fr1},F1r:=F1r+θ-min{θ,Fr1},Fr1:=Fr1-min{θ,Fr1}。于是得到N的流量增加的新流f和新N(f),转step2。step4利用引理2求N的最小截。证明算法中的step1到step3实际上是N中的可行流从零流开始依次按N(f)的从s到t的最大容量路增大流量直到使流加大到N的最小截量为止的过程,由最大流量最小截量定理、文中(p191)定理8.9、以及引理1和引理2易知结论成立。2关于修正nf的容量定理1是以下运输网络中求最大流和最小截量的算法X5的理论依据。运输网络N中求最大流和最小截量的算法X5如下:step1(准备)写出N的容量矩阵C=(Cij)n×n,令Fij:=0,Wij:=Cij(i,j=1,2,…,n)。step2(求N(f)中从顶点s到顶点t的最大容量路Pst)令Uij:=Wij,Sij:=j,(i,j=1,2,…,n),k:=1。step3对1≤i,j≤n。如果Uij<min{Uik,Ukj},则令Uij:=min{Uik,Ukj},Sij:=Sik;否则Uij、Sij保持不变。step4如果k=n,转step5;否则,令k:=k+1,转step3。step5如果Ust=0,则N(f)中不存在从s到t的最大容量路,转step9;否则令θ:=Ust,转step6。step6(沿Pst调整流f和修正N(f)的容量)令1:=s,r:=Sst。step7如果Fr1=0,令W1r:=W1r-θ,Wr1:=Wr1+θ,F1r:=F1r+θ;否则,令W1r:=W1r-θ+min{θ,Fr1},Wr1:=Wr1+min{θ,Fr1},F1r:=F1r+θ-min{θ,Fr1},Fr1:=Fr1-min{θ,Fr1}。step8如果r=t,转step2;否则令1:=r,r:=Srt,转step7。step9(输出N的最大流在所有弧的对应流量)令i:=1。step10令j:=1。step11如果i≠j且Cij>0,则N中弧(i,j)存在,输出弧(i,j)和它的流量Fij。step12如果j<n,令j:=j+1,转step11;否则转step13。step13如果i<n,令i:=i+1,转step10;否则转step14。step14(利用引理2求N的最小截)令sign(i):=0(1≤i≤n),rotation:=1,(sign(i)=1表示顶点i∈V*1,sign(i)=0表示顶点i∈¯V*1,其中V*1和¯V*1如引理2定义)。step15(确定引理2中的V*1和¯V*1)令sign(s):=1。step16令i:=1。step17令j:=1。step18如果i≠j,转step19;否则转step22。step19如果Cij>0或Cji>0,转step20;否则转step22。step20如果sign(i)=1且Fij<Cij且sign(j)=0,令sign(j):=1。step21如果sign(i)=1且Fji>0且sign(j)=0,令sign(j):=1。step22令j:=j+1。如果j≤n,转step18;否则令i:=i+1,转step23。step23如果i≤n,转step17。否则转step24。step24令rotation:=rotation+1。如果rotation≤n,转step16;否则转step25。step25(输出N的最小截(V*1‚¯V*1))令i:=1。step26令j:=1。step27如果i≠j,转step28;否则转step30。step28如果Cij>0,转step29;否则转step30。step29如果sign(i)=1且sign(j)=0,则(i,j)为N中最小截的一条弧,输出弧(i,j)。step30令j:=j+1。如果j≤n,转step27;否则令i:=i+1,转step31。step31如果i≤n,转step26;否则停止。3软件的基本思想某运输网络如图1所示,顶点1为发点,顶点10为收点,弧上的数字为该弧的容量,求该运输网络的最大流和最小截。解顶点数n=10,发点s=1,收点t=10,容量矩阵C如下:C=[∞4020100000000∞200150000000∞1010100000000∞02000000000∞105500000010∞020300000000∞00∞00000010∞0∞000000020∞∞000000000∞]利用本文作者根据算法X5用VisualBasic5.0设计的名为《规划系统》的应用软件的名叫《网络最大流问题》的功能模块,只要输入容量矩阵C及相关信息n、s和t,就能快捷地求出运输网络图1的最大流和最小截,运行结果如