最小费用最大流求解方法-20131212

1、 对每一条弧都给出的容量网络D=(V, A, C) (称为费用容量网络)中，求取最大流f，使输送流量的总费用 b(f) =bijfij 为最小的一类优化问题。 其中，cij表示弧(vi, vj)上的容量，bij表示弧(vi, vj)上通过单位流量所花费的费用，fij表示弧(vi, vj)上的流量。vivj(cij,bij,fij)2、最小费用流 对于一个费用容量网络，具有相同流量 v(f) 的可行流中，总费用b(f)最小的可行流称为该费用容量网络关于流量 v(f) 的最小费用流，简称流量为 v(f) 的最小费用流 当沿着一条关于可行流 f 的增广链（流量修正路线），以修正量=1进行调整，得到新

2、的可行流 ，则称 为)()(fbfbf增广链的费用定义为：以单位调整量调整可行流时所付出的费用；当修正量=1时，此时， 的流量v( ) = v(f)+1；ffijijijijijijijijbbffbffbfbfb)()()()(主要学习按思路主要学习按思路(1)(1)的求解方法的求解方法v(f)b(f)(1)(2)若f 是流量为v(f)的最小费用流，是关于 f 的所有增广链中费用最小的增广链，那么沿着去调整 f 得到的新的可行流 就是流量为 的最小费用流。f( )V f 基于第一种求解途径，根据上述定理，从流量为v(f) 的最小费用流f 开始，只要找到其上的最小费用增广链，在该链上调整流量，

3、就得到增加流量后的最小费用流。循环往复就可以求出最小费用最大流。：构造增广费用网络图，借助最短路算法寻找最小费用增广链。的 将流量网络中的每一条弧（vi,vj）用一对方向相反的弧替代，并定义弧的权数如下： vivj (cij,fij)bij 若0fijfij0+ 若fij=0bij 若0fij fij0+ 若fij=0 ，保持原弧不变，将单位费用作为权数，即wij= bij: Vi Vjbij Vi Vj-bij去掉原有弧，添加以单位费用的负数作为权数后向弧（虚线弧）： ，原有弧以单位费用作权数，并添加以单位费用的负数作为权数后向弧（虚线弧）：ViVj bij-bij- vsvtv2v3v1(

4、10,4)(7,1)(8,1)(10,3)(4,2)(5,2)(2,6)解：（1）以零流弧为初始可行流f(0)，则初始可行流的流量v(f(0)=0。vsvtv2v3v14113226 (5, 5)(7, 5)vsvtv2v3v1(10,0)(8, 5)(10, 0)(4, 0)(2, 0)第 1 次 迭 代 f(0)中全部是零流弧,则保持原边不变,单位费用为权；所有的权均大于零，可用D氏标号法求出最短路：即是f(0)的。 tsvvvv12流量调整量1=min8-0,5-0,7-0=5 总流量v(f(1)=5最小费用增广链的费用bij=1+2+1=4新的可行流为f(1),总费用b1=45=20

5、第 2 次 迭 代1v1vt-2 6v2v34-1 32 1vs-1(7, 7)vsvtv2v3v1(10, 2)(8, 5)(10, 0)(4, 0)(2, 0) (5, 5)零流弧保持原边,非饱和非零流弧(vs,v2)和(v1,vt)增添后向弧,饱和弧(v2,v1)去掉原弧增添后向弧；用列表法求出最短路: 即是f(1)的最小费用增广链。 流量调整量2=min10-0,7-5=2，总流量v(f(2)=原流量+新增 流量=5+2=7；最小费用增广链的费用 bij=4+1=5新的可行流为f(2),总费用b2=原费用+新增费用=20+52=30 tsvvv1vsvtv2v3v14-4-1-13 2

6、 6 -21零流弧保持原边，非饱和非零流弧增添后向弧，饱和弧去掉原边增添后向弧用列表法求得最短路 即是f(2)的最小费用增广链。流量调整量3=min8-5,10-0,4-0=3，总流量v(f(3) =原流量+新 增流量=7+3=10；最小费用增广链的费用 bij=1+3+2=6新的可行流为f(3),总费用b3=原费用+新增费用=30+63=48 tsvvvv32第 3 次 迭 代(7, 7)vsvtv2v3v1(10, 2)(8, 8)(10, 3)(4, 3)(2, 0)(5, 5) 6 34vsvtv2v3v1 -3-1-1-2 2-4 -2添加弧；用列表法求得最短路 对应最小费用增广链t

7、svvvvv321tsvvvvv 321调整流量 4=min10-2,5,10-3,4-3=1，总流量v(f(4) =10+1=11；最小费用增广链的费用 bij=4-2+3+2=7新的可行流为f(4),总费用b4=原费用+新增费用 =48+71=55。第 4 次 迭 代(7, 7)vsvtv2v3v1 (10, 3)(8, 8)(10, 4)(4, 4)(2, 0)(5, 4) 6 34vsvtv2v3v1 -3-1 -1-2-4 -2添加弧；用列表法计算发现Vs和Vt之间不存在一条最短路，计算结束。当前的可行流f(4)即为所求的最小费用最大流。第 5次 迭 代 2vsv1v2v3vtd(1)d(2)d(3)d(4)vs04 0000v1-40-2 64444v2-1 203 222v3-3 0 1055vt -1 -2 0 6 34vsvtv2v3v1 -3-1 -1-2-4 -2 2总