1.8最小费用最大流问题

1、 在实际生活中，涉及 “流”的问题时。人 们考虑的还不只是流量，而且还有“费 用”的因素。本节介绍的最小费用最大 流问题就是这类问题之一。 对每一条弧都给出对每一条弧都给出的的容量网络容量网络 D=(V, A, C) (称为费用容量网络称为费用容量网络)中，求取中，求取最最 大流大流f，使输送流量的，使输送流量的总费用总费用 b(f) =bijfij 为最为最 小小的一类优化问题。的一类优化问题。 其中，其中，cij表示弧表示弧(vi, vj)上的容量，上的容量，bij表示表示 弧弧(vi, vj)上通过单位流量所花费的费用，上通过单位流量所花费的费用，fij表表 示弧示弧(vi, vj)上的

2、流量。上的流量。 vivj (cij,bij,fij) 当沿着一条关于可行流当沿着一条关于可行流 f 的增广的增广 链（流量修正路线）链（流量修正路线），以修正量，以修正量=1 进行调整进行调整，得到新的可行流，得到新的可行流 ，则，则 称称 为为)()(fbfb f 增广链增广链的费用定义为：以的费用定义为：以单位调整量单位调整量 调整可行流时所付出的费用；调整可行流时所付出的费用； 当修正量当修正量=1时，时， 此时，此时， 的流量的流量v( ) = v(f)+1；f f ijijijijijijijij bbffbffbfbfb)()()()( 主要学习按思路主要学习按思路 (1)(1)

3、的求解方法的求解方法 v(f) b(f) (1) (2) 若若f 是流量为是流量为v(f)的最的最 小费用流，小费用流，是关于是关于 f 的所有增广的所有增广 链中链中费用最小的增广链费用最小的增广链，那么沿着，那么沿着 去去调整调整 f 得到的新的可行流得到的新的可行流 就是流量为就是流量为 的最小费用流。的最小费用流。 f )( fv 基于第一种求解途径，根据上述定理，基于第一种求解途径，根据上述定理， 从流量为从流量为v(f) 的最小费用流的最小费用流f 开始，只要找开始，只要找 到其上的到其上的最小费用增广链，在该链上调整流最小费用增广链，在该链上调整流 量，就得到量，就得到增加流量增

4、加流量后的最小费用流后的最小费用流。循环。循环 往复就可以求出最小费用最大流。往复就可以求出最小费用最大流。 ：构造增广费用网络图，借助最短路构造增广费用网络图，借助最短路 算法寻找最小费用增广链。算法寻找最小费用增广链。 的的 将流量网络中的每一条弧（将流量网络中的每一条弧（vi,vj）都看）都看 作一对方向相反的弧，并定义弧的权数如作一对方向相反的弧，并定义弧的权数如 下：下： vivj (cij,fij) bij 若若fij0 + 若若fij=0 bij 若若fij0 + 若若fij=0 ，保持原弧不变，将，保持原弧不变，将 单位费用作为权数，即单位费用作为权数，即wij= bij: V

5、i Vj bij Vi Vj -bij 去掉原有弧，添加去掉原有弧，添加 以单位费用的以单位费用的负数负数作为权数作为权数后向弧后向弧 （虚线弧）：（虚线弧）： ，原有，原有 弧以单位费用作权数，并添加以单位费弧以单位费用作权数，并添加以单位费 用的用的负数负数作为权数作为权数后向弧后向弧（虚线弧）：（虚线弧）： Vi Vj bij -bij - vs vt v2v3 v1 (10,4) (7,1) (8,1) (10,3) (4,2) (5,2)(2,6) 解：（解：（1）以零流弧为初始可行流）以零流弧为初始可行流f(0)，则初始可，则初始可 行流的流量行流的流量v(f(0)=0。 vs v

6、t v2v3 v1 4 1 1 3 2 26 (5, 5) (7, 5) vsvt v2v3 v1 (10,0) (8, 5) (10, 0) (4, 0) (2, 0) 第第 1 次次 迭迭 代代 f f(0) (0)中全部是零流弧 中全部是零流弧, ,则保则保 持原边不变持原边不变, ,单位费用为权；单位费用为权； 所有的权均大于零，可用所有的权均大于零，可用D D 氏标号法求出最短路：氏标号法求出最短路： 即是即是f f(0) (0)的 的。 ts vvvv 12 流量调整量流量调整量 1 1=min8-0,5-0,7-0=5=min8-0,5-0,7-0=5 总流量总流量v(fv(f(

7、1) (1)=5 )=5 最小费用增广链的费用最小费用增广链的费用 b bij ij=1+2+1=4 =1+2+1=4 新的可行流为新的可行流为f f(1) (1), ,总费 总费 用用b b1 1=4=45=205=20 第第 2 次次 迭迭 代代 1 v1 vt -2 6 v2 v3 4 -1 3 2 1 vs -1 (7, 7) vsvt v2 v3 v1 (10, 2) (8, 5) (10, 0) (4, 0) (2, 0) (5, 5) 零流弧保持原边零流弧保持原边, ,非饱和非非饱和非 零流弧零流弧(v(vs s,v,v2 2) )和和(v(v1 1,v,vt t) )增添后增添

8、后 向弧向弧, ,饱和弧饱和弧(v(v2 2,v,v1 1) )去掉原弧去掉原弧 增添后向弧；增添后向弧； 用列表法求出最短路用列表法求出最短路: : 即是即是f f(1) (1)的最小费用增广链 的最小费用增广链。 流量调整量流量调整量 2 2=min10-0,7-5=2=min10-0,7-5=2， 总流量总流量v(fv(f(2) (2)= )=原流量原流量+ +新增新增 流量流量=5+2=7=5+2=7； 最小费用增广链的费用最小费用增广链的费用 b bij ij=4+1=5 =4+1=5 新的可行流为新的可行流为f f(2) (2), ,总费用 总费用 b b2 2= =原费用原费用+

9、 +新增费用新增费用 =20+5=20+52=30 2=30 ts vvv 1 vs vt v2v3 v1 4 -4 -1 -1 3 2 6 -21 零流弧保持原边，非饱和非零流弧保持原边，非饱和非 零流弧增添后向弧，饱和弧去零流弧增添后向弧，饱和弧去 掉原边增添后向弧掉原边增添后向弧 用列表法求得最短路用列表法求得最短路 即是即是f(2)的最小费用增广链。的最小费用增广链。 流量调整量流量调整量3 3=min8-=min8- 5,10-0,4-0=35,10-0,4-0=3， 总流量总流量v(fv(f(3) (3) ) = =原流量 原流量+ +新新 增流量增流量=7+3=10=7+3=10

10、； 最小费用增广链的费用最小费用增广链的费用 b bij ij=1+3+2=6 =1+3+2=6 新的可行流为新的可行流为f f(3) (3), ,总费用 总费用 b b3 3= =原费用原费用+ +新增费用新增费用 =30+6=30+63=48 3=48 ts vvvv 32 第第 3 次次 迭迭 代代 (7, 7) vs vt v2v3 v1 (10, 2) (8, 8) (10, 3) (4, 3) (2, 0) (5, 5) 6 3 4 vsvt v2v3 v1 -3 -1 -1 -2 2 -4 -2 添加弧；添加弧； 用列表法求得最短路用列表法求得最短路 对应最小费用增广链对应最小费

11、用增广链 ts vvvvv 321 ts vvvvv 321 调整流量调整流量 4 4=min10-2,5,10-3,4-3=1=min10-2,5,10-3,4-3=1， 总流量总流量v(fv(f(4) (4) ) =10+1=11 =10+1=11； 最小费用增广链的费用最小费用增广链的费用 b bij ij=4-2+3+2=7 =4-2+3+2=7 新的可行流为新的可行流为f f(4) (4), ,总费用 总费用 b b4 4= =原费用原费用+ +新增费用新增费用 =48+7=48+71=551=55。 第第 4 次次 迭迭 代代 (7, 7) vsvt v2v3 v1 (10, 3)

12、 (8, 8) (10, 4) (4, 4) (2, 0) (5, 4) 6 3 4 vsvt v2v3 v1 -3 -1 -1 -2 -4 -2 添加弧；添加弧； 用列表法计算发现用列表法计算发现VsVs 和和VtVt之间不存在一条最之间不存在一条最 短路，计算结束。当前短路，计算结束。当前 的可行流的可行流f f(4) (4)即为所求的 即为所求的 最小费用最大流。最小费用最大流。 第第 5次次 迭迭 代代 2 vsv1v2v3vtd(1)d(2)d(3)d(4) vs04 0000 v1-40-2 64444 v2-1 203 222 v3-3 0 1055 vt -1 -2 0 6 3 4 vs vt v2v3 v1 -3 -1 -1 -2 -4 -2 2 总总 结结 最短路算法与最大流算法的结合运用最短路算法与最大流算法的结合运用 1 1）