运筹学最小费用最大流流问题课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,运筹学教程,第五节 最小费用最大流流问题,在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。,第五节 最小费用最大流流问题 在实际的网络系统,1,最小费用最大流问题提法,:,设一个网络,G,=,（,V,，,E,，,C,），,对于每一个弧,(,v,i,v,j,),E,给定容量,c,ij,外，还给出单位流量的费用,d,ij,0,，网络记为,G,=,（,V,，,E,，,C,，,d,）。,网络系统的最小费用最大流问题，是指要寻求一个最大流,f,，使流量,w(f)=v,且流的总费用,达到最小。,如果要求,f,为最大流，问题转化为最小费用最大流。,其算法有：原始算法和,对偶算法。,最小费用最大流问题提法:如果要求f为最大流，问题转化为最小费,2,定义,24,：,已知网络,G,=,（,V,，,E,，,C,，,d,），,f,是,G,上的一个可行流，,u,为从,vs,到,vt,的可增广链，,d(u),为链,u,的费用。,vs,v1,v2,vt,3,5,1,4,d(u)=(3+1+4)-(5)=3,定义24：已知网络G=（V，E，C，d），f是G上的一个可行,3,我们将 叫做这条增广链的费用,。,实际上在一个网络,G,中，当沿可行流,f,的一条增广链,，以调整量,=1,改进,f,，得到的新可行流,f ,的流量，有,w,(,f,)=,w,(,f,)+1,，而此时总费用,b,(,f,),比,b,(,f,),增加了,我们将 叫做这条增广链的费用。 实际,4,结论：,如果可行流,f,在流量为,w,(,f,),的所有可行流中的,费用最小,，并且, 是关于,f,的所有,增广链中的,费用最小的增广链,，那么沿增广链,调整可行流,f,，得到的新可行流,f ,，也是流量为,w,(,f ,),的所有可行流中的最小费用流。依次类推，当,f ,是最大流时，就是所要求的最小费用最大流。,结论：如果可行流 f 在流量为w(f )的所有可行流中的费,5,对偶算法基本思路：,零流,f,=0,是流量为,0,的最小费用流。,一般地，寻求最小费用流，总可以从零流,f,=0,开始。下面的问题是：如果已知,f,是流量为,w,(,f,),的最小费用流，那么就要去,寻找关于,f,的最小费用增广链,，用最大流的方法将,f,(0),调整到,f,(1),，使,f,(1),流量为,w(f,(0),)+,，,且保证,f,(1),在,w(f,(0),)+,流量下的最小费用流，,不断进行到,w(f,(k),)=v,为止。,定理,12,：,如果,f,是流量为,w(f),的最小费用流，,u,是关于,f,的从,vs,到,vt,的一条最小费用可增广链，则,f,经过,u,调整流量,得到新可行流,f(f=fu),一定是流量为,w(f)+,可行流中的最小费用流。,对偶算法基本思路：定理12：如果f是流量为w(f)的最小费用,6,定义,25,：,网络,G,=,（,V,，,E,，,C,，,d,），,f,是,G,上的一个可行流，保持原网络各点，,每一条边,(,v,i, v,j,),用两条方向相反的边,（,v,i, v,j,）,和,(,v,j, v,i,),代替,，各边的权,L,ij,为：,并且将权为,+,的边去掉,。,1,、,边,（,v,i, v,j,） ,E,2,、,边,（,v,j, v,i,）为原图,G,中（,v,i,v,j,）的反向边,定义25：网络G=（V，E，C，d），f是G上的一个可行流，,7,这样，在网络,G,中寻找关于,f,的最小费用增广链就等于价于在长度网络,L,(,f,),中寻求从,v,s,到,v,t,的最短路。,对偶算法基本步骤：,（,1,）、取零流,f,(0),=0,.,（,2,）、如果在第,K,-1,步得到最小费用流,f,(K-1),流量,w(f,(k),)v,则构造长度网络,L,(,f,(k-,1,),),。,（,3,）、,在长度网络,L,(,f,(k-,1,),),中，寻求从,v,s,到,v,t,的最短路。如果不存在最短路，则,f,(k-,1,),就是最小费用最大流。如果存在最短路，则在,原网络,G,中得到相对应的增广链,。,这样，在网络G中寻找关于f 的最小费用增广链就等于价,8,（,4,）、在,G,中与这条最短路相应的可增广链,上，对,f,(k,1,),进行调整，,f,(k),=,f,(k),u,取调整量,令：,得到一个新的可行流,f,(k),，其流量为,w(f,(k-1),)+,;,如果,w(f,(k-1),)+,=v,，则停止；否则令,f,(k),代替,f,(k-1),返回,2,。,（4）、在G中与这条最短路相应的可增广链上，对f (k1,9,例,求图所示网络中的流量为,10,的最小费用流，弧旁的权是,（,c,ij, d,ij,）,.,(,c,ij, d,ij,),(8, 1),(10, 3),(4, 2),(2, 6),(7, 1),(10, 4),(5, 2),v,1,v,2,v,s,v,3,v,t,例 求图所示网络中的流量为10的最小费用流，弧旁的权是（,10,解：（,1,）取初始可行流为零流,f,(0),=0,构造赋权有向图,L(f,(0),),用,Dijkstra,求出从,v,s,到,v,t,的最短路,(,v,s,v,2,v,1,v,t,),如图,b,中虚线所示。,(1),(3),(2),(6),(1),(4),(2),L(f,(,0),),v,1,v,s,v,2,v,3,v,t,图,b,v,1,v,s,v,2,v,3,v,t,f,(0),=0,(,c,ij, d,ij,),(8, 1),(10, 3),(4, 2),(2, 6),(7, 1),(10, 4),(5, 2),v,1,v,2,v,s,v,3,v,t,解：（1）取初始可行流为零流f (0)=0,构造赋权有,11,（,2,）在原网络,G,中，与这条最短路相对应的增广链为,=,（,v,s,v,2,v,1,v,t,）,。,（,3,）在,上对,f,(0),=0,进行调整，,=min8,5,7=5,，得到新可行流,f,(1),，如图,b,所示。,（2）在原网络G中，与这条最短路相对应的增广链为=（v,12,按照以上的算法，依次类推，可以得到,f,(1),，,f,(2),，,f,( 3),，,f,(4),，,流量分别为,5,，,7,，,10,，,11,，并且分别构造相对应的赋权有向图,L,(,f,(,1 ),), L(f,(2),), L,(,f,(3),),L,(,f,(4),),。,由于在,L,(,f,(4),),中已经不存在从,v,s,到,v,t,的最短路，因此，可行流,f,(4),，,v(f,(1),),=11,是最小费用最大流。,按照以上的算法，依次类推，可以得到f (1)，f (2)，f,13,(5),(0),(0),(0),(5),(0),(5),图,c,f,(,1),w,(,f,(,1),)=5,d,(,f,(,1),)=5*1+5*2+5*3,v,1,v,s,v,2,v,2,v,t,v,s,v,2,v,3,v,t,f,(1),=5,(5)(0)(0)(0)(5)(0)(5)图 cf(1),w,14,L,(,f,(,1),),图,d,v,1,(2),( -1),v,3,(1),(3),(6),(1),(4),(-2),(-1),v,s,v,2,v,t,最短路：,v,s,-v,1,-v,t,L(f (1)图 dv1(2)( -1)v3(1)(3),15,运筹学最小费用最大流流问题课件,16,运筹学最小费用最大流流问题课件,17,运筹学最小费用最大流流问题课件,18,运筹学最小费用最大流流问题课件,19,(2,0),(5,5),(8,5),(4,0),(7,7),(10,2),(10,0),图,e,f,(2),w,(,f,(2),)=7,v,1,v,s,v,2,v,3,v,t,(2,0)(5,5)(8,5)(4,0)(7,7)(10,2,20,L,(,f,(2),),图,f,(1),(3),(2),(6),(-1),(4),(-2),(-1),(-4),v,1,v,s,v,3,v,t,v,2,最短路：,vs-v2-v3-vt,L( f (2) )图 f(1)(3)(2)(6)(-1),21,(8,8),(10,3),(4,3),(2,0),(7,7),(10,2),(5,5),图,g,f,(3,),w,(,f,(3),)=10,v,1,v,s,v,2,v,3,v,t,d,(,f,(,3),)=2*4+8*1+5*2+ 3*3+ 3*2+ 7*1=48,(8,8)(10,3)(4,3)(2,0)(7,7)(10,22,(-1),(3),(2),(6),(-1),(4),(-2),(-4),L(,f,(3),),图,h,(-2),(-3),v,1,v,s,v,2,v,3,v,t,(-1)(3)(2) (6)(-1)(4) (-2) (,23,(8,8),(10,4),(4,4),(2,0),(7,7),(10,3),(5,4),图,i,f,(4,),w,(,f,(,4),) =11,v,1,v,s,v,2,v,3,v,t,(8,8)(10,4)(4,4)(2,0)(7,7)(10,24,(-1),(3),(-2),(6),(-1),(4),(2),(-4),L,(,f,(4),),图,j,(-2),(-3),v,1,v,s,v,2,v,3,v,t,(-1)(3)(-2)(6)(-1)(4) (2) (-4),25,小结,:,1,、理解最小费用流问题的概念。,2,、掌握求最小费用流问题的算法。,小结:,26,