运筹学最小费用最大流流问题.pptx

第五节第五节 最小费用最大流流问题最小费用最大流流问题 在在在在实实实实际际际际的的的的网网网网络络络络系系系系统统统统中中中中，当当当当涉涉涉涉及及及及到到到到有有有有关关关关流流流流的的的的问问问问题题题题的的的的时时时时候候候候，我我我我们们们们往往往往往往往往不不不不仅仅仅仅仅仅仅仅考考考考虑虑虑虑的的的的是是是是流流流流量量量量，还还还还经经经经常常常常要要要要考考考考虑虑虑虑费费费费用用用用的的的的问问问问题题题题。比比比比如如如如一一一一个个个个铁铁铁铁路路路路系系系系统统统统的的的的运运运运输输输输网网网网络络络络流流流流，即即即即要要要要考考考考虑虑虑虑网网网网络络络络流流流流的的的的货货货货运运运运量量量量最最最最大大大大，又又又又要要要要考考考考虑虑虑虑总总总总费费费费用用用用最最最最小小小小。最最最最小小小小费费费费用用用用最最最最大大大大流流流流问问问问题题题题就就就就是是是是要要要要解解解解决决决决这一类问题。这一类问题。这一类问题。这一类问题。最小费用最大流问题提法最小费用最大流问题提法最小费用最大流问题提法最小费用最大流问题提法:设设设设一一一一个个个个网网网网络络络络G G=（V V，E E，C C），对对对对于于于于每每每每一一一一个个个个弧弧弧弧(v vi i,v,vj j)E E E E,给给给给定定定定容容容容量量量量c c c cijijijij外外外外，还还还还给给给给出出出出单单单单位位位位流流流流量量量量的的的的费费费费用用用用d d d dijijijij 0 0 0 0，网网网网络络络络记记记记为为为为G G=（V V，E E，C C，d d）。网网网网络络络络系系系系统统统统的的的的最最最最小小小小费费费费用用用用最最最最大大大大流流流流问问问问题题题题，是是是是指指指指要寻求一个最大流要寻求一个最大流要寻求一个最大流要寻求一个最大流 f f，使流量，使流量，使流量，使流量w(f)=v,w(f)=v,w(f)=v,w(f)=v,且流的总费用且流的总费用且流的总费用且流的总费用达到最小。达到最小。达到最小。达到最小。如果要求如果要求如果要求如果要求f f为最大流，问题转化为最小费用最大流。为最大流，问题转化为最小费用最大流。为最大流，问题转化为最小费用最大流。为最大流，问题转化为最小费用最大流。其算法有：原始算法和其算法有：原始算法和其算法有：原始算法和其算法有：原始算法和对偶算法。对偶算法。对偶算法。对偶算法。定义24：已知网络已知网络已知网络已知网络G G=（V V，E E，C C，d d），），），），f f是是是是GG上的一上的一上的一上的一个可行流，个可行流，个可行流，个可行流，u u为从为从为从为从vs vs 到到到到vtvt的可增广链，的可增广链，的可增广链，的可增广链，d(u)d(u)为链为链为链为链u u的费的费的费的费用。用。用。用。vsv1v2vt3514d(u)=(3+1+4)-(5)=3我们将我们将 叫做这条增广链的费用叫做这条增广链的费用。实实实实际际际际上上上上在在在在一一一一个个个个网网网网络络络络G G中中中中，当当当当沿沿沿沿可可可可行行行行流流流流 f f 的的的的一一一一条条条条增广链增广链增广链增广链，以调整量，以调整量，以调整量，以调整量=1=1改进改进改进改进f f，得到的新可行流，得到的新可行流，得到的新可行流，得到的新可行流f f 的的的的流流流流量量量量，有有有有 w w(f f )=)=w w(f f )+1)+1，而而而而此此此此时时时时总总总总费费费费用用用用b b(f f )比比比比b b(f f)增加了增加了增加了增加了结论：结论：结论：结论：如果可行流如果可行流如果可行流如果可行流 f f 在流量为在流量为在流量为在流量为w w(f f )的所有可行流中的所有可行流中的所有可行流中的所有可行流中的的的的费用最小费用最小费用最小费用最小，并且，并且，并且，并且 是关于是关于是关于是关于f f 的所有的所有的所有的所有增广链中的增广链中的增广链中的增广链中的费费费费用最小的增广链用最小的增广链用最小的增广链用最小的增广链，那么沿增广链，那么沿增广链，那么沿增广链，那么沿增广链调整可行流调整可行流调整可行流调整可行流f f，得，得，得，得到的新可行流到的新可行流到的新可行流到的新可行流f f ，也是流量为，也是流量为，也是流量为，也是流量为w w(f f)的所有可行流中的所有可行流中的所有可行流中的所有可行流中的最小费用流。依次类推，当的最小费用流。依次类推，当的最小费用流。依次类推，当的最小费用流。依次类推，当 f f 是最大流时，就是是最大流时，就是是最大流时，就是是最大流时，就是所要求的最小费用最大流。所要求的最小费用最大流。所要求的最小费用最大流。所要求的最小费用最大流。对偶算法基本思路：对偶算法基本思路：零流零流f f=0=0是流量为是流量为0 0的最小费用流。的最小费用流。一般地，寻求最小费一般地，寻求最小费用流，总可以从零流用流，总可以从零流f f=0=0开始。下面的问题是：如果已开始。下面的问题是：如果已知知f f 是流量为是流量为w w(f f)的最小费用流，那么就要去的最小费用流，那么就要去寻找关于寻找关于f f 的最小费用增广链的最小费用增广链，用最大流的方法将，用最大流的方法将f f(0)(0)调整到调整到f f(1)(1)，使，使f f(1)(1)流量为流量为w(fw(f(0)(0)+)+，且保证且保证f f(1)(1)在在w(fw(f(0)(0)+)+流量下的最流量下的最小费用流，小费用流，不断进行到不断进行到w(fw(f(k)(k)=v)=v为止。为止。定理定理1212：如果如果f f是流量为是流量为w(f)w(f)的最小费用流，的最小费用流，u u是关于是关于f f的从的从vsvs到到vtvt的一条最小费用可增广链，则的一条最小费用可增广链，则f f经过经过u u调整流量调整流量得得到新可行流到新可行流f(f=fu),f(f=fu),一定是流量为一定是流量为w(f)+w(f)+可行流中可行流中的最小费用流。的最小费用流。定义定义定义定义25252525：网络网络网络网络G G=（V V，E E，C C，d d），），），），f f是是是是GG上的一个上的一个上的一个上的一个可行流，保持原网络各点，可行流，保持原网络各点，可行流，保持原网络各点，可行流，保持原网络各点，每一条边每一条边每一条边每一条边 (v vi i,v,vj j)用两用两用两用两条方向相反的边条方向相反的边条方向相反的边条方向相反的边（v vi i ,v,vj j）和和和和(v vj j,v,vi i)代替代替代替代替，各边的权，各边的权，各边的权，各边的权L Lij ij为：为：为：为：并且将权为并且将权为+的边去掉的边去掉。1、边边边边（v vi i ,v,vj j）E E2、边边边边（v vj j ,v,vi i ）为原图）为原图）为原图）为原图GG中（中（中（中（v vi i,v,vj j）的反向边）的反向边）的反向边）的反向边 这这样样，在在网网络络G中中寻寻找找关关于于f 的的最最小小费费用用增增广广链链就就等等于于价于在长度网络价于在长度网络L(f)中寻求从中寻求从vs 到到vt 的最短路。的最短路。对偶算法基本步骤：对偶算法基本步骤：（1 1）、取零流）、取零流f(0)=0.（2 2）、如果在第）、如果在第K-1步得到最小费用流步得到最小费用流f (K-1),流量流量w(fw(f(k)(k)v,)v,则构造长度网络则构造长度网络L L(f(k-1)。（3）、）、在长度网络在长度网络L L(f(k-1)中，寻求从中，寻求从vs到到vt的最短路。如的最短路。如果不存在最短路，则果不存在最短路，则f(k-1)就是最小费用最大流。如果存在最就是最小费用最大流。如果存在最短路，则在短路，则在原网络原网络G中得到相对应的增广链中得到相对应的增广链。（4 4 4 4）、在）、在）、在）、在G G G G中与这条最短路相应的可增广链中与这条最短路相应的可增广链中与这条最短路相应的可增广链中与这条最短路相应的可增广链 上，对上，对上，对上，对f f(k(k 1 1)进行进行进行进行调整，调整，调整，调整，f f(k)(k)=f f(k)(k)u u,取调整量取调整量取调整量取调整量令：令：得到一个新的可行流得到一个新的可行流得到一个新的可行流得到一个新的可行流f f(k)(k)，其流量为，其流量为，其流量为，其流量为w(fw(fw(fw(f(k-1)(k-1)(k-1)(k-1)+)+)+)+;如果如果如果如果w(fw(fw(fw(f(k-1)(k-1)(k-1)(k-1)+)+)+)+=v=v，则停止；否则令，则停止；否则令，则停止；否则令，则停止；否则令f f(k)(k)代替代替代替代替f f f f(k-1)(k-1)(k-1)(k-1)返回返回返回返回2 2。例例 求求图图所所示示网网络络中中的的流流量量为为1010的的最最小小费费用用流流，弧旁的权是弧旁的权是（cij,dij）.(cij,dij)(8,1)(10,3)(4,2)(2,6)(7,1)(10,4)(5,2)v1v2vsv3vt 解解：（1 1）取取初初始始可可行行流流为为零零流流f(0)=0,构构造造赋赋权权有有向向图图L(f(0),用用Dijkstra求求出出从从vs到到vt的的最最短短路路(vs,v2,v1,vt),如图如图 b 中虚线所示。中虚线所示。(1)(3)(2)(6)(1)(4)(2)L(f(0)v1vsv2v3vt图图 bv1vsv2v3vtf(0)=0(cij,dij)(8,1)(10,3)(4,2)(2,6)(7,1)(10,4)(5,2)v1v2vsv3vt （2 2 2 2）在在在在原原原原网网网网络络络络G G中中中中，与与与与这这这这条条条条最最最最短短短短路路路路相相相相对对对对应应应应的的的的增增增增广广广广链链链链为为为为=（v vs s ,v,v2 2 ,v,v1 1 ,v,vt t）。（3 3 3 3）在）在）在）在上对上对上对上对f f(0)(0)=0=0进行调整，进行调整，进行调整，进行调整，=min8,5,7=5=min8,5,7=5，得到新可行流，得到新可行流，得到新可行流，得到新可行流f f(1)(1)，如图，如图，如图，如图b b所示。所示。所示。所示。按照以上的算法，依次类推，可以得到按照以上的算法，依次类推，可以得到按照以上的算法，依次类推，可以得到按照以上的算法，依次类推，可以得到f f(1)(1)，f f(2)(2)，f f(3)(3)，f f(4)(4)，流量分别为流量分别为流量分别为流量分别为5 5 5 5，7 7 7 7，10101010，11111111，并且分别构造相对应的赋权有向图并且分别构造相对应的赋权有向图并且分别构造相对应的赋权有向图并且分别构造相对应的赋权有向图L L(f f(1)1),L(f L(f(2)(2),L,L(f f(3)(3),L,L(f f(4)(4)。由于在由于在由于在由于在L L(f f(4)(4)中已经不存在从中已经不存在从中已经不存在从中已经不存在从v v v vs s到到到到v vt t的最短路，的最短路，的最短路，的最短路，因此，可行流因此，可行流因此，可行流因此，可行流f f(4)(4)，v(fv(f(1)(1)=11=11是最小费用最大是最小费用最大是最小费用最大是最小费用最大流。流。流。流。(5)(0)(0)(0)(5)(0)(5)图图 cf(1),w(f(1)=5d(f(1)=5*1+5*2+5*3v1vsv2v2vtvsv2v3vtf(1)=5L(f(1)图图 dv1(2)(-1)v3(1)(3)(6)(1)(4)(-2)(-1)vsv2vt最短路：最短路：最短路：最短路：v vs s-v-v1 1-v-vt t(2,0)(5,5)(8,5)(4,0)(7,7)(10,2)(10,0)图图 ef(2),w(f(2)=7v1vsv2v3vtL(f(2)图图 f(1)(3)(2)(6)(-1)(4)(-2)(-1)(-4)v1vsv3vtv2最短路：最短路：最短路：最短路：vs-v2-v3-vtvs-v2-v3-vt(8,8)(10,3)(4,3)(2,0)(7,7)(10,2)(5,5)图图 gf(3),w(f(3)=10v1vsv2v3vtd(f(3)=2*4+8*1+5*2+3*3+3*2+7*1=48(-1)(3)(2)(6)(-1)(4)(-2)(-4)L(f(3)图图 h(-2)(-3)v1vsv2v3vt(8,8)(10,4)(4,4)(2,0)(7,7)(10,3)(5,4)图图 if(4),w(f(4)=11v1vsv2v3vt(-1)(3)(-2)(6)(-1)(4)(2)(-4)L(f(4)图图 j(-2)(-3)v1vsv2v3vt小结:1、理解最小费用流问题的概念。2、掌握求最小费用流问题的算法。