《运筹学》课程授课教案（讲稿）第19讲 最小费用最大流

课程名称：《运筹学》第_19_讲次授课题目最小费用最大流本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，学会最小费用最大流求解方法。[重点及难点]最小费用最大流求解。内容[本讲课程的引入]前面讨论了网络上的最大流问题。在实际的网络系统中，凡是涉及“流”的问题，我们往往不只考虑流量，还要考虑“费用”的问题，比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。本节介绍的最小费用流的问题就属于这类问题之一。[本讲课程的内容]最小费用流问题是在一个连通网络G=（V，E，C）中，每条边(Vi，V,）除了已给出容量C,外，还给出了单位流量的费用d,(≥O)，记作G=（V，E，C，d)。求G的一个可行流f=f,)，使得流量W(f)=v，且总费用d(f)=Z di,·f,最小。(V,)EE当F=f）为最大流时，此问题就是最小费用最大流问题（简称最小费用流问题）。和最短路问题、最大流问题相似，最小费用流问题也是线性规划问题，而且用网络图论的方法求解比直接用线性规划方法求解要简便。最小费用流问题的求解方法有多种。都是在求最大流的算法上，作一些改变，使得到的解是网络上的最大流（或预定值），且费用最小。下面我们介绍一种应用较为广泛的“最短路法

课程名称：《运筹学》 第 19 讲次 授课题目 最小费用最大流 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，学会最小费用最大流求解方法。 [重点及难点] 最小费用最大流求解。 内 容 [本讲课程的引入] 前面讨论了网络上的最大流问题。在实际的网络系统中，凡是涉及“流”的问题， 我们往往不只考虑流量，还要考虑“费用” 的问题，比如一个铁路系统的运输网络流， 即要考虑网络流的货运量最大，又要考虑总费用最小。本节介绍的最小费用流的问题就 属于这类问题之一。 [本讲课程的内容] 最小费用流问题是在一个连通网络 G =（V，E，C）中，每条边 ( , ) i j v v 除了已给出容量 i j c 外， 还给出了单位流量的费用 ( 0) di j ，记作 G =（V，E，C，d）。求 G 的一个可行流 { }i j f  f ，使得 流量 W( f )  v ，且总费用     v v E i j i j i j d f d f ( , ) ( ) 最小。 当 { }i j f  f 为最大流时，此问题就是最小费用最大流问题（简称最小费用流问题）。 和最短路问题、最大流问题相似，最小费用流问题也是线性规划问题，而且用网络图论的方法 求解比直接用线性规划方法求解要简便。 最小费用流问题的求解方法有多种。都是在求最大流的算法上，作一些改变，使得到的解是网 络上的最大流（或预定值），且费用最小。 下面我们介绍一种应用较为广泛的“最短路法

内容定义23已知网络G=（V，E，C，d)，f是G上的一个可行流，u为一条（关于f的）从vs到vt的可增广链，d(f)=d,-d,称为链μ的费用。u若μ是从's到vt的可增广链中费用最小的链，则称μ是最小费用可增广链。结论：如果可行流f在流量为W()的所有可行流中的费用最小，并且μ是关于f的所有增广链中的费用最小的增广链，那么沿增广链μ调整可行流f，得到的新可行流于*也是流量为W()的所有可行流中的最小费用流。依次类推，当是最大流时，就是所要求的最小费用流。所以，此算法的基本思路为：先找一个流量为W(f()）的最小费用流f()，然后寻找从vs到yt的可增广链μ，用最大流的方法将f(0)调整到()，使于()的流量为W(f()+，且保证()是在W(f()）+の下最小的费用流，再对f()重复上述步骤。因为dij≥0，显然，零流f=(0)是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流(0)=(0)开始。下面的问题是：如果已知f是流量为W()的最小费用流，如何寻找关于的最小费用增广链？对此，重新构造一个赋权有向图L(J)，其项点是原网络G的项点，而将G中的每一条边（v，)变成两个相反方向的边（vi，）和(y，)，并且定义图中边的权l,为：1.当边(V,V)eE，令[d当fi0l={+0当f,=0（其中+8的含义为：此边流量已经减少到0，不能再减少，权为+的边可从网络中去掉。）这样，在网络G中寻找关于的最小费用可增广链就等于价于在L(f)中寻求从Vs到

内 容 定义 23 已知网络 G =（V，E，C，d）， f 是 G 上的一个可行流，  为一条（关于 f 的）从 vs 到 vt 的可增广链，        di j di j d( f ) 称为链  的费用。 若  * 是从 vs 到 vt 的可增广链中费用最小的链，则称  * 是最小费用可增广链。 结论：如果可行流 f 在流量为 W(f )的所有可行流中的费用最小，并且  *是关于 f 的 所有增广链中的费用最小的增广链，那么沿增广链  *调整可行流 f，得到的新可行流 f * 也是流量为 W(f * )的所有可行流中的最小费用流。依次类推，当 f * 是最大流时，就是所要 求的最小费用流。 所以，此算法的基本思路为： 先找一个流量为 ( ) (0) W f 的最小费用流 (0) f ，然后寻找从 vs 到 vt 的可增广链  ，用 最大流的方法将 (0) f 调整到 (1) f ，使 (1) f 的流量为 ( )  (0) W f ，且保证 (1) f 是在 ( )  (0) W f 下最小的费用流，再对 (1) f 重复上述步骤。 因为 di j  0 ，显然，零流 f ={0}是流量为 0 的最小费用流。一般地，寻求最小费用流，总 可以从零流 (0) f ={0}开始。下面的问题是：如果已知 f 是流量为 W(f)的最小费用流，如何 寻找关于 f 的最小费用增广链？ 对此，重新构造一个赋权有向图 L( f ) ，其顶点是原网络 G 的顶点，而将 G 中的每一 条边 ( vi , vj )变成两个相反方向的边（vi， vj）和(vj , vi)，并且定义图中边的权 i j l 为： 1.当边 (vi , v j ) E ，令          i j i j i j i j i j i j f c d f c l 当 当 （其中   的含义为：这条边已经饱和，不管付出多大代价，也不能再增大流量，权为   的边可从网络中去掉。） 2.当边 ( , ) j i v v 为原来网络 G 中边（vi， vj）的反向边，令           0 0 i j i j i j ji f d f l 当 当 （其中   的含义为：此边流量已经减少到 0，不能再减少，权为   的边可从网络中去 掉。） 这样，在网络 G 中寻找关于 f 的最小费用可增广链就等于价于在 L(f )中寻求从 vs 到

内容vt的最短路。其算法步骤为：（1）取零流为初始可行流，(0)=(0)。(2）一般地，如果在第K-1步得到最小费用流F(K-I)，则构造图L(f(k-1))(3）在图L(r(k-1)中，寻求从vs到vr的最短路。若不存在最短路，则(K-1)就是最小费用最大流，停止计算；否则转（4）。（4）如果存在最短路，则在可行流k-1)的图中得到与此最短路相对应的可增广链μ，在可增广链μ上，对f(K-I)进行调整，调整量为：min(c, -fi-), min(F-1)0=minH令[r-+0(vi,y,)eμ*Sr(t-1) -0(v,V,)Eμ则得到新的可行流f()。对f()重复f(k)[uru-)(v,,v,)tμ上面的步骤，返回步骤（2)。例8.11求图8—21所示网络中的最小费用最大流，弧旁的权是（bij·cji）(1）取初始可行流为零流(0)=[0)(1,6)1（2）构造赋权有向图(4 ,8)W(r(0))，求出从vs到vt的(2 ,5)[(3 ,2)最短路Vs(2 ,3)如图8—22（1）中双箭线所示。Vs4在网络G中相应的可增广链(1,4)V2(6,7) =(Vs,V2,V1, V3,V)图8—21上用最大流算法进行流量调整，得：=(s,2),(V2,),(,V),(V,),=所以，调整量0, =min(4,3, 6, 5)=3。[r0 +3 (v,v)ept*f(1)[(s0)(vi,y,)Eμ*结果见图8—22（2)

内 容 vt 的最短路。 其算法步骤为： （1）取零流为初始可行流 ，f (0) ={0}。 （2）一般地，如果在第 K 1 步得到最小费用流 (K1) f ，则构造图 L( f (k-1) )。 （3）在图 L(f (k-1))中，寻求从 vs 到 vt 的最短路。若不存在最短路，则 (K1) f 就是最 小费用最大流，停止计算；否则转（4）。 （4）如果存在最短路，则在可行流 f (k－1)的图中得到与此最短路相对应的可增广链  ， 在可增广链  上，对 (K1) f 进行调整，调整量为：             min min( ) , min( ) ( 1) (k 1) i j k i j i j c f f    令                        ( , ) ( , ) ( , ) ( 1) ( 1) ( 1) ( ) i j k i j i j k i j i j k i j k i j f v v f v v f v v f 则得到新的可行流 (k ) f 。对 (k ) f 重复 上面的步骤，返回步骤（2）。 例 8.11 求图 8—21 所示网络中的最小费用最大流，弧旁的权是（bij , cij） （1）取初始可行流为零流 f (0)={0} （2）构造赋权有向图 W(f (0))，求出从 vs 到 vt 的 最短路 vs→v 2→v 1→v 3→vt ， 如图 8—22（1）中双箭线所示。 在网络 G 中相应的可增广链 ( , , , , ) 1 s 2 1 3 t   v v v v v 上用最大流算法进行流量调整，得：          ( , ),( , ),( , ),( , ) , s 2 2 1 1 3 3 t v v v v v v v v 所以，调整量 1  min(4, 3 , 6 , 5)  3。             ( , ) 3 ( , ) (0) (0) (1) i j i j i j i j f v v f v v f 结果见图 8—22（2）。 (3 ,2) vs v 2 v 1 vt v 3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) 图 8—21

内容（3）构造赋权有向图W(f(1)），如图8一22（3），由于边上有负权，用逐次逼近法，求得最短路为Vs-V-3-1，在网络G内相应的可增广链上进行调整，得(2)，见图一22（3)，，图8一22中，双线所示路径为最小费用最大流。从赋权有向图W(f(5))可以看出，不存在从vs到v的最短路，故已得到最小费用流，最大流为9，最小费用为：4×+5×4+5×1+4×6+5×2=6330,=3W(f)=3S6V2302图8——22 (1)L(r()图8—22(2)f@2=13W(f2)=42162402图8——22 (3) L(f(1)图8—22 (4)(2)

内 容 （3）构造赋权有向图 W(f (1) )，如图 8—22（3）， 由于边上有负权，用逐次逼近法，求得最短路为 vs→v 2→v 3→vt ，在网络 G 内相应的可增 广链上进行调整，得 (2) f ，见图—22（3），.， 图 8—22 中，双线所示路径为最小费用最大流。从赋权有向图 W(f (5) )可以看出，不 存在从 vs 到 vt 的最短路，故已得到最小费用流，最大流为 9，最小费用为： 4 `54  51 46  52  63 。 0 vs v 2 v 1 vt v 3 3 0 0 3 3 3 图 8—22 (2) f ( 1) 1=3 W(f (1))=3 3 vs v 2 v 1 vt v 3 1 6 4 1 2 2 图 8——22 (1) L(f (0)) 1 vs v 2 v 1 vt v 3 4 0 0 3 4 3 图 8—22 (4 ) f ( 2) 2=1 W(f (2))=4 －1 图 8——22 (3) L(f (1) ) －2 3 vs v 2 v 1 vt v 3 1 6 4 1 2 －1 －2

内容0;=1W(f3)=5VVSVt-1126's图8——22 (5) L(r(2)412图8—22(6)(3)e,=3VSW(f)-86V2图8——22 (7)L(r(3)43V2图8—22(8）(4)

内 容 L(f (2)) －3 vs v 2 v 1 vt v 3 －1 4 1 2 －2 图 8——22 (5) －2 3 －1 6 6 L(f (3)) vs v 2 v 1 vt v 3 －3 －1 4 1 2 －2 图 8——22 (7) 3 －1 6 1 vs v 2 v 1 vt v 3 4 3 4 4 5 0 图 8—22 (8 ) f ( 4) 4=3 W(f (4))=8 1 vs v 2 v 1 vt v 3 4 0 1 4 5 3 图 8—22 (6 ) f ( 3) 3=1 W(f (3))=5

内容0s=1W(f5)=9VSV6-1V2图 8——22 (9) L(F(4)Vt4XV2图8—22 (10)(5)P-16"2图 8———22 (11) L(f(5)

内 容 －1 2 3 －1 vs v 2 v 1 vt v 3 －3 4 图 8——22 (9) 1 2 6 L( f ( 4)) 0 vs v 2 v 1 vt v 3 4 4 5 5 5 0 图 8—22 (10 ) 5=1 W(f (5))=9 f ( 5) 3 －1 2 －1 4 图 8——22 (11) L( f ( 5)) 1 2 6 －4 －3 vs v 2 v 1 vt v 3 －6

内容【本讲小结】今天我们给大家重点介绍最小费用最大流问题，希望大家课下要很好的复习。【本讲课程的作业】复习本节学习的内容

内 容 [本讲小结] 今天我们给大家重点介绍最小费用最大流问题，希望大家课下要很好的复 习。 [本讲课程的作业] 复习本节学习的内容