运筹学最小费用最大流流问题课件.pptx
第五节 最小费用最大流流问题,在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。,最小费用最大流问题提法:设一个网络G=（V，E，C），对于每一个弧(vi ,vj )E ,给定容量cij外，还给出单位流量的费用dij 0 ，网络记为G=（V，E，C，d）。网络系统的最小费用最大流问题，是指要寻求一个最大流 f ，使流量w(f)=v,且流的总费用达到最小。,如果要求f为最大流，问题转化为最小费用最大流。其算法有：原始算法和对偶算法。,定义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,我们将 叫做这条增广链的费用。,实际上在一个网络G中，当沿可行流 f 的一条增广链，以调整量=1改进f ，得到的新可行流f 的流量，有 w(f )=w(f )+1，而此时总费用b(f )比b(f)增加了,结论：如果可行流 f 在流量为w(f )的所有可行流中的费用最小，并且 是关于f 的所有增广链中的费用最小的增广链，那么沿增广链调整可行流f，得到的新可行流f ，也是流量为w(f )的所有可行流中的最小费用流。依次类推，当 f 是最大流时，就是所要求的最小费用最大流。,对偶算法基本思路：零流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)+可行流中的最小费用流。,定义25：网络G=（V，E，C，d），f是G上的一个可行流，保持原网络各点，每一条边 ( vi , vj )用两条方向相反的边（vi , vj）和(vj , vi)代替，各边的权Lij为：,并且将权为+的边去掉。,1、边（vi , vj） E,2、边（ vj , vi ）为原图G中（vi,vj）的反向边,这样，在网络G中寻找关于f 的最小费用增广链就等于价于在长度网络L(f )中寻求从vs 到vt 的最短路。对偶算法基本步骤：（1）、取零流f (0) =0.（2）、如果在第K-1步得到最小费用流f (K-1),流量w(f(k)v,则构造长度网络L(f (k-1)。（3）、 在长度网络L(f (k-1)中，寻求从vs到vt的最短路。如果不存在最短路，则f (k-1)就是最小费用最大流。如果存在最短路，则在原网络G中得到相对应的增广链。,（4）、在G中与这条最短路相应的可增广链上，对f (k1)进行调整， f(k) = f(k)u,取调整量,令：,得到一个新的可行流f(k)，其流量为w(f(k-1)+; 如果w(f(k-1)+=v，则停止；否则令f(k)代替f(k-1)返回2 。,例 求图所示网络中的流量为10的最小费用流，弧旁的权是（ cij , dij ）.,解：（1）取初始可行流为零流f (0)=0,构造赋权有向图L(f(0),用Dijkstra求出从vs到vt的最短路(vs ,v2 ,v1 ,vt),如图b 中虚线所示。,图 b,v1,vs,v2,v3,vt,f (0) =0,（2）在原网络G中，与这条最短路相对应的增广链为=（vs ,v2 ,v1 ,vt ）。 （3）在上对f (0)=0进行调整，=min8,5,7=5，得到新可行流f (1)，如图b所示。,按照以上的算法，依次类推，可以得到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)中已经不存在从vs到vt的最短路，因此，可行流f (4)，v(f(1)=11是最小费用最大流。,(5),(0),(0),(0),(5),(0),(5),图 c,f(1),w( f (1)=5d( f (1)=5*1+5*2+5*3,v1,vs,v2,v2,vt,L(f (1),图 d,最短路：vs-v1-vt,L( f (2) ),图 f,最短路：vs-v2-v3-vt,d( f (3)=2*4+8*1+5*2+ 3*3+ 3*2+ 7*1=48,小结:1、理解最小费用流问题的概念。2、掌握求最小费用流问题的算法。,
