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

1、 對每一條弧都給出的容量網(wǎng)絡(luò)D=(V, A, C) (稱為費用容量網(wǎng)絡(luò))中，求取最大流f，使輸送流量的總費用 b(f) =bijfij 為最小的一類優(yōu)化問題。 其中，cij表示弧(vi, vj)上的容量，bij表示弧(vi, vj)上通過單位流量所花費的費用，fij表示弧(vi, vj)上的流量。vivj(cij,bij,fij)2、最小費用流 對于一個費用容量網(wǎng)絡(luò)，具有相同流量 v(f) 的可行流中，總費用b(f)最小的可行流稱為該費用容量網(wǎng)絡(luò)關(guān)于流量 v(f) 的最小費用流，簡稱流量為 v(f) 的最小費用流 當(dāng)沿著一條關(guān)于可行流 f 的增廣鏈（流量修正路線），以修正量=1進行調(diào)整，得到新

2、的可行流 ，則稱 為)()(fbfbf增廣鏈的費用定義為：以單位調(diào)整量調(diào)整可行流時所付出的費用；當(dāng)修正量=1時，此時， 的流量v( ) = v(f)+1；ffijijijijijijijijbbffbffbfbfb)()()()(主要學(xué)習(xí)按思路主要學(xué)習(xí)按思路(1)(1)的求解方法的求解方法v(f)b(f)(1)(2)若f 是流量為v(f)的最小費用流，是關(guān)于 f 的所有增廣鏈中費用最小的增廣鏈，那么沿著去調(diào)整 f 得到的新的可行流 就是流量為 的最小費用流。f( )V f 基于第一種求解途徑，根據(jù)上述定理，從流量為v(f) 的最小費用流f 開始，只要找到其上的最小費用增廣鏈，在該鏈上調(diào)整流量，

3、就得到增加流量后的最小費用流。循環(huán)往復(fù)就可以求出最小費用最大流。：構(gòu)造增廣費用網(wǎng)絡(luò)圖，借助最短路算法尋找最小費用增廣鏈。的 將流量網(wǎng)絡(luò)中的每一條弧（vi,vj）用一對方向相反的弧替代，并定義弧的權(quán)數(shù)如下： vivj (cij,fij)bij 若0fijfij0+ 若fij=0bij 若0fij fij0+ 若fij=0 ，保持原弧不變，將單位費用作為權(quán)數(shù)，即wij= bij: Vi Vjbij Vi Vj-bij去掉原有弧，添加以單位費用的負數(shù)作為權(quán)數(shù)后向弧（虛線?。?，原有弧以單位費用作權(quán)數(shù)，并添加以單位費用的負數(shù)作為權(quán)數(shù)后向?。ㄌ摼€弧）：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)中全部是零流弧,則保持原邊不變,單位費用為權(quán)；所有的權(quán)均大于零，可用D氏標號法求出最短路：即是f(0)的。 tsvvvv12流量調(diào)整量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)的最小費用增廣鏈。 流量調(diào)整量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)的最小費用增廣鏈。流量調(diào)整量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添加??；用列表法求得最短路 對應(yīng)最小費用增廣鏈t

7、svvvvv321tsvvvvv 321調(diào)整流量 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添加?。挥昧斜矸ㄓ嬎惆l(fā)現(xiàn)Vs和Vt之間不存在一條最短路，計算結(jié)束。當(dāng)前的可行流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總