运筹学最大流.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,Page,*,网络的最大流,如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。,网络的最大流,基本概念：,1.容量网络：,队网络上的每条弧(v,i,v,j,)都给出一个最大的通过能力，称为该弧的,容量,，简记为c,ij,。容量网络中通常规定一个,发点,(也称源点，记为s)和一个,收点,(也称汇点，记为t)，网络中其他点称为,中间点,。,s,t,4,8,4,4,1,2,2,6,7,9,网络的最大流,2.,网络的最大流,是指网络中从发点到收点之间允许通过的最大流量。,3.,流与可行流,流,是指加在网络各条弧上的实际流量，对加在弧(v,i,v,j,)上的负载量记为f,ij,。若f,ij,=0，称为零流。,满足以下条件的一组流称为,可行流,。,容量限制条件。容量网络上所有的弧满足：,0f,ij,c,ij,中间点平衡条件。,若以,v(f,),表示网络中从,s,t,的流量，则有：,网络的最大流,结论：任何网络上一定存在可行流。（零流即是可行流）,网络最大流问题：,指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。,网络的最大流,割与割集,割是指容量网络中的发点和收点分割开，并使st的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用 表示。,如下图中，AA将网络上的点分割成 两个集合。并有 ，称弧的集合(v,1,v,3,),(v,2,v,4,)是一个割，且,的流量为18。,网络的最大流,s,t,v,1,v,3,v,2,v,4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(3),7(6),A,A,B,B,网络的最大流,定理1,设网络N中一个从,s,到,t,的流,f,的流量为,v,(,f,)，(,V,V,)为任意一个割集，则,v,(,f,),=,f,(,V,V,),f,(,V,V,),推论1,对网络 N中任意流量,v,(,f,),和割集,(V,V)，有,v,(,f,),c,(,V,V,),证明 w=,f,(,V,V,),f,(,V,V,),f,(,V,V,),c,(,V,V,),推论2,最大流量,v,(,f,),不大于最小割集的容量，即：,v,(,f,),min,c,(,V,V,),定理2,在网络中st的最大流量等于它的最小割集的容量，,即：,v,(,f,),=,c,(,V,V,),网络的最大流,增广链,在网络的发点和收点之间能找到一条链，在该链上所有指向为st的弧，称为前向弧，记作,+,存在,f0,，则称这样的链为增广链。例如下图中，sv,2,v,1,v,3,v,4,t。,定理3,网络N中的流,f,是最大流当且仅当N中不包含任何增广链,网络的最大流,s,t,v,1,v,3,v,2,v,4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(4),7(5),网络的最大流,求网络最大流的标号算法：,基本思想,由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。,基本方法,找出第一个可行流，（例如所有弧的流量,f,ij,=0,。）,用标号的方法找一条增广链,首先给发点,s,标号,(),标号中的数字表示允许的最大调整量。,选择一个点,v,i,已标号并且另一端未标号的弧沿着某条链向收点检查：,网络的最大流,如果弧的起点为,v,i,，并且有,f,ij,0,，则,v,j,标号,(,f,ji,),(3)重复第(2)步，可能出现两种结局：,标号过程中断，,t,无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，,记已标号的点集为,V,未标号的点集合为,V,(V,V,),为网络的最小割。,t,得到标号，反向追踪在网络中找到一条从,s,到,t,得由标号点及相应的弧连接而成的增广链。继续第,(4),步,网络的最大流,(4)修改流量。设原图可行流为f，令,得到网络上一个新的可行流f。,(5)擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何增广链，计算结束。,网络的最大流,例6.10 用标号算法求下图中st的最大流量，并找出最小割。,s,t,v,1,v,3,v,2,v,4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),网络的最大流,解：(1)先给s标号(),s,t,v,1,v,3,v,2,v,4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),网络的最大流,s,t,v,1,v,3,v,2,v,4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),(2)检查与s点相邻的未标号的点，因f,s1,c,s1,，故对v,1,标号=min,c,s1,-f,s1,=1,(1),网络的最大流,s,t,v,1,v,3,v,2,v,4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(6),(),(1),(2)检查与v,1,点相邻的未标号的点，因f,13,c,13,，故对v,3,标号=min1,c,13,-f,13,=min1,6=1,(1),网络的最大流,s,t,v,1,v,3,v,2,v,4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),(1),(1),(3)检查与v,3,点相邻的未标号的点，因f,3t,c,3t,，故对v,t,标号=min1,c,3t,-f,3t,=min1,1=1,(1),找到一条增广链sv,1,v,3,t,网络的最大流,(4)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,s,t,v,1,v,3,v,2,v,4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(3),7(5),(),(1),(1),(1),网络的最大流,(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。,s,t,v,1,v,3,v,2,v,4,8(8),9(4),5(5),10(8),6(0),2(0),9(9),5(3),7(5),(),(1),(1),(1),网络的最大流,(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。,s,t,v,1,v,3,v,2,v,4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(3),7(5),(),(2),(2)=min,2=2,(2),(1)=min2,3=2,(3)=min2,5=2,(2),(1),(4)=min2,1=1,(1),(t)=min1,2=1,网络的最大流,(6)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,s,t,v,1,v,3,v,2,v,4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(3),7(5),(),(2),(2),(2),(1),(1),网络的最大流,s,t,v,1,v,3,v,2,v,4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(2),7(6),(),(2),(2),(2),(1),(1),(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。,网络的最大流,s,t,v,1,v,3,v,2,v,4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(2),7(6),(),(1),(1),(1),(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。,(2)=min,1=1,(1)=min1,2=1,(3)=min1,4=1,网络的最大流,例6.9 求下图,s,t,的最大流，并找出最小割,s,t,v,1,v,2,v,3,v,4,v,5,4(3),3(2),10(4),3(2),1(1),4(3),3(2),5(3),4(2),2(2),7(6),8(3),网络的最大流,s,t,v,1,v,2,v,3,v,4,v,5,4(3),3(2),10(4),3(2),1(1),4(3),3(2),5(3),4(2),2(2),7(6),8(3),解:(1)在已知可行流的基础上，通过标号寻找增广链。,(),(2)=min,6=6,(6),(3)=min6,2=2,(2),(t)=min2,5=2,(2),存在增广链sv,2,v,3,t,网络的最大流,(2)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,s,t,v,1,v,2,v,3,v,4,v,5,4(3),3(2),10(4),3(2),1(1),4(3),3(2),5(3),4(2),2(2),7(6),8(3),(),(6),(2),(2),网络的最大流,(3)擦除原标号，重新搜寻增广链。,s,t,v,1,v,2,v,3,v,4,v,5,4(3),3(2),10(6),3(2),1(1),4(3),3(2),5(3),4(4),2(2),7(6),8(5),(),(6),(2),(2),网络的最大流,(4)重新搜寻增广链。,s,t,v,1,v,2,v,3,v,4,v,5,4(3),3(2),10(6),3(2),1(1),4(3),3(2),5(3),4(4),2(2),7(6),8(5),(),(2)=min,4=4,(4),(1),(5)=min4,1=1,(3)=min1,2=1,(1),(1),(t)=min1,3=1,存在增广链：sv,2,v,5,v,3,t,网络的最大流,(5)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,s,t,v,1,v,2,v,3,v,4,v,5,4(3),3(2),10(6),3(2),1(1),4(3),3(2),5(3),4(4),2(2),7(6),8(5),(),(4),(1),(1),(1),网络的最大流,(6)擦除原标号,s,t,v,1,v,2,v,3,v,4,v,5,4(3),3(2),10(7),3(2),1(1),4(3),3(3),5(4),4(4),2(2),7(6),8(6),(),(4),(1),(1),(1),网络的最大流,s,t,v,1,v,2,v,3,v,4,v,5,4(3),3(2),10(7),3(2),1(1),4(3),3(3),5(4),4(4),2(2),7(6),8(6),(),(1),(1),(1),(5)=min,1=1,(5)=min1,1=1,(5)=min1,2=1,(7)重新搜寻增广链。,存在增广链：sv,5,v,3,t,网络的最大流,(8)调整增广链上的流量，非增广链流量不变，得到新的可行流,s,t,v,1,v,2,v,3,v,4,v,5,4(3),3(2),10(7),3(2),1(1),4(3),3(3),5(4),4(4),2(2),7(6),8(6),(),(1),(1),(1),网络的最大流,s,t,v,1,v,2,v,3,v,4,v,5,4(3),3(3),10(7),3(2),1(1),4(3),3(3),5(5),4(4),2(2),7(6),8(7),(),(1),(1),(1),(9)擦除原标号,网络的最大流,s,t,v,1,v,2,v,3,v,4,v,5,4(3),3(3),10(7),3(2),1(1),4(3),3(3),5(5),4(4),2(2),7(6),8(7),(10)重新标号，搜索增广链,(),(1)=min,1=1,(1),(5)=min1,1=1,(1),(4)=min1,1=1,(1),(t)=min1,1=1,(1),存在增广链：sv,1,v,5,v,4,t,网络的最大流,s,t,v,1,v,2,v,3,v,4,v,5,4(3),3(3),10(7),3(2),1(1),4(3),3(3),5(5),4(4),2(2),7(6),8(7),(),(1),(1),(1),(1),(11)调整增广链上的流量，非增广链流量不变，得到新的可行流,网络的最大流,s,t,v,1,v,2,v,3,v,4,v,5,4(4),3(3),10(7),3(3),1(1),4(4),3(3),5(5),4(4),2(2),7(7),8(7),(),(1),(1),(1),(1),(11)擦除标号，在新的可行流上重新标号。,网络的最大流,s,t,v,1,v,2,v,3,v,4,v,5,4(4),3(3),10(7),3(3),1(1),4(4),3(3),5(5),4(4),2(2),7(7),8(7),(),(11)擦除标号，在新的可行流上重新标号。,(3),(1)=min,3=1,无法标号，不存在增广链，此可行流已为最大流。最大流量为14。,