最小費用最大流問題

最小費用最大流問題網(wǎng)絡D=（V，A，C）,每一?。╲i，vj）∈A，給出（vi，vj）上單位流的費用b(vi，vj)≥0，（簡記bij）。最小費用最大流問題：求一個最大流f，使流的總費用取最小值。一、求解原理設對可行流f存在增廣鏈μ，當沿μ以=1調(diào)整f，得新的可行流f

'時，(顯然V(f')=V(f)+1)，兩流的費用之差b(f)-b(f′)稱為增廣鏈μ的費用。最小費用最大流的原理的主要依據(jù)：若f是流值為V（f）的所有可行流中費用最小者,而μ是關于f的所有增廣鏈中費用最小的增廣鏈,則沿μ以去調(diào)整f,得可行流f，f就是流量為V(f)+的所有可行流中費用最小的可行流。這樣，當f是最大流時，f就是所求的最小費用最大流。b(f′)-b(f)+1-1構(gòu)造賦權(quán)有向圖W(f),它的頂點是D的頂點,W(f)中弧及其權(quán)wij

按?。╲i，vj）在D中的情形分為：則（vi，vj）∈W（f）,且wij=bij則（vj

，vi

）∈W（f

）,且wji=-bijvjvi4vj4vi3.0vjvi5.53vivj-3如果已知f是流量為V（f

）的最小費用流，求出關于f

的最小費用增廣鏈。若（vi，vj）∈A，且fij=0(零?。?，若(vi，vj

)∈A，且fij=cij(飽和弧),費用若（vi，vj）∈A，且0＜fij<cij

vj4vi3.2則（vi，vj）∈W（f），且wij=bij

及（vj

，vi

）∈W（f），且wji=-bijvjvi4vivj-4新網(wǎng)絡W（f）成為流f的(費用)增量網(wǎng)絡。由增廣鏈費用的概念及網(wǎng)絡W（f）的定義，知在網(wǎng)絡D中尋求關于可行流f的最小費用增廣鏈，等價于在網(wǎng)絡W（f）中尋求從vs到vt的最短路。二、最小費用最大流算法算法步驟：第一步：確定初始可行流f

0=0，令k=0；第二步：記經(jīng)k

次調(diào)整得到的最小費用流為fk，構(gòu)造增量網(wǎng)絡W（fk）；在W（fk）中，尋找vs到vt的最短路。若不存在最短路（即最短路路長是∞），則fk

就是最小費用最大流，若存在最短路，則此最短路即為原網(wǎng)絡D中相應的可增廣鏈μ，轉(zhuǎn)入第

3步。

第三步：在增廣鏈μ上對f

k

按下式進行調(diào)整，調(diào)整量為k=min令得新的可行流fk+1,返回第2步。第四步：停止運算，并輸出當前最小費用可行流fk+1

，作為G的最小費用最大流。vsv2v34v1vt621132(a)w(f0)例1求下圖所示網(wǎng)絡的最小費用最大流。弧旁數(shù)字為

（bij，cij）。v2v3(4,10)v1vsvt（6，2）（2，5）(1，8)(1,7)（3,10）(2，4)解：（1）取初始可行流f

0=0；（2）按算法要求構(gòu)造長度網(wǎng)絡W（f

0

），求出從vs到vt的最短路。（3）在原網(wǎng)絡D中，與這條最短路對應的增廣鏈為

μ=（vs，v2，v1，vt）。（3）在原網(wǎng)絡D中，與這條最短路對應的增廣鏈為:（4）在μ上進行調(diào)整，=5，得f

1

，

如圖（b）所示。v2v3（10，0）v1vsvt（2，0）（5，0）(8，0)(7,0)(10,0)(4，0)μ=（vs，v2，v1，vt）v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)(7,5)(10,0)(4，0)(b)f1按照上述算法依次得f

1

，f

2

，f

3

，f

4

，流量依次為V(f

1)=5，V(f

2)=7，V(f

3)=10，V(f4)=11，構(gòu)造相應的增量網(wǎng)絡為W(f

1)，W(f

2)，W(f

3)，W(f4),如圖(a),(e),(g),(i)所示。vsv2v34v1vt621132(a)w(f0)v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)(7,5)(10,0)(4，0)(b)f1V(f1)=5v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)(7,5)(10,0)(4，0)(b)f1v2v3（10，2）v1vsvt(2,0)（5，5）(8，5)(7,7)(10,0)(4，0)(d)f2V(f2)=7vt2v2v3v1vs6-2-1-13(c)W(f

（1）)411v2v3（10，2）v1vsvt(2,0)（5，5）(8，5)(7,7)(10,0)(4，0)(d)f2V(f2)=7

(e)

w(f

2)v1vs-1v2v3-46-2-1341vt2v2v3（10，2）v1vsvt(2,0)（5，5）(8，8)(7,7)(10,3)(4，3)(f)f3V(f3)=10v2v3（10，2）v1vsvt(2,0)（5，5）(8，8)(7,7)(10,3)(4，3)(f)f3V(f3)=10vt2v2v3-4v1vs6-2-1-13(g)W(f

3)4-3-2v2v3（10，3）v1vsvt(2,0)（5，4）(8，8)(7,7)(10,4)(4，4)(h)f4V(f4)=11圖（i）中，不存在從vs到vt的最短路，所以f4為最小費用最大流。問題：（1）如何求網(wǎng)絡W（f

k）中的vs到vt最短路？（2）如何判斷無vs到vt的最短路？v2v3（10，3）v1vsvt(2,0)（5，4）(8，8)(7,7)(10,4)(4，4)(h)f4V(f4)=11vt-2v2v3-4v1vs6-2-1-13（i）W（f

4）4-32最小費用給定流xv1v2y3,0,45,2,24,4,23,2,44,2,2xv1v2y3,0,45,0,24,0,23,0,44,0,2xv1v2y3,1,45,1,24,3,23,2,44,2,2圖中數(shù)字含義:[c(e),f(e),b(e)](2,6)(4,2)(10,3)(8,1)V2(5,2)(10,4)vsV1(7,1)vtV3求下圖最小費用最大流第一輪：f0為初始可行流，作相應的費用有向圖網(wǎng)絡L(f

0)，如圖（a）。在L(f

0)上用DijksTra標號法求出由vs到vt的最短路（最小費用鏈）μ0=(vs,v2,v1,

vt)，并對μ0按進行流量的調(diào)整，由于，所以有，其余不變，得新的可行流f1的流量有向圖（b）。第二輪構(gòu)造L(f

1)，如圖（c）所示，在L(f

1)中用逐次逼近法求最短路，為(vs,v1,vt)，在G內(nèi)相應的增廣鏈上進行了流量的調(diào)整，調(diào)整量為2，得到流f2，如圖（d）所示。第三輪構(gòu)造L(f

2)，如圖（e）所示，在L(f

2)中用找到最短路（vs,v2,v3,vt），在G內(nèi)相應的增廣鏈上進行了流量的調(diào)整，調(diào)整量為3，得到，如圖（f3）所示。第四輪構(gòu)造L(f

3)，如圖（g）所示，在L(f

3)中用求的最短路(vs,v1,v2,v3,vt),在G內(nèi)相應的增廣鏈上進行了流量的調(diào)整，調(diào)整量為1，得到流（f4），如圖（h）所示。第五輪

構(gòu)造L(f

4)

，如圖（i）所示，在中不存在從vs到

vt的最短路，故算法結(jié)束。即f5為所求的最

小費用最大流。V16231V224vs1vtV3(a)L(f

0)

0005V250vs5vtV3(b)f1

V1vs6231V2541vtV3(c)L(f

1)

V10338V252vs7vtV3(f)f3V11-1vs6231V2-24-1vtV3(e)L(f

2)

V1-4-10005V252vs7vtV3(d)f2V12vt63-1V2-24-1V3(g)L(f

3)

V1-4-3-20448V243vs7vtV3(h)f4V1vs-463-1V2-24-1V3(i)L(f

4)

V1-3-2vtvs2最小費用最大流求解過程1.求下圖所示網(wǎng)絡的最小費用最大流,每弧旁的數(shù)字是(bij

.cij

)。(1,4)vsvt(3.5)(2.1)(4,2)(2.1)(3.3)(2.5)(1.3)(4.2)

2.下表給出某運輸問題的產(chǎn)銷平衡表與單位運價表。將此問題轉(zhuǎn)化為最小費用最大流問題，畫出網(wǎng)絡圖并求數(shù)值解。產(chǎn)地銷地123產(chǎn)量AB2030242252087銷量456最小總費用為240sBA321t(22,7)(24,8)(5,8)(30,7)(0,5)(0,6)(20,8)(0,7)(0,4)(20,8)(0,8)弧旁數(shù)字為(bij,cij

)3.現(xiàn)有兩個煤礦X1和X2,每月分別能生產(chǎn)煤13及15個單位,每單位煤的生產(chǎn)費用分別為5及3個單位;另有兩個電站Y1和Y2,每月需用煤分別為12及15個單位,從Xi至Yj的單位運費Wij如下表,問每個煤礦應生產(chǎn)多少煤并運往何處,才能滿足所有要求,同時使總的運費最低?

YjXiY1Y2X1X23567(13,5)X(15,3)(15,7)(15,5)(13,3)(12,0)(15,0)(13,6)YX2X1Y1Y2W(X,X1)=5W(X,X2)=3?生產(chǎn)費用最小費用流1.基本概念及定理（1）流的費用定義

對于一個可行流f=｛fij｝來說，如果網(wǎng)絡

G=(V,A,C,W)中，對于每條弧aij

∈A，都有一個單位流費用ωij，則流的費用定義為：（2）最小費用流定義

網(wǎng)絡G=(V,A,C,W)中，對于每一流值為V(f)

的可行流f來說，都存在一個流的費用

W(f)，使W(f)為最小的可行流，則稱為最小費用流。最小費用流的數(shù)學定義如下：目標函數(shù)：約束條件：（1）每一條??；（2）；

（3）；

（4）；其中：V(f)——目標流值；Cij

——能力；ωij——單位費用；Vs——發(fā)點；Vt——收點。（3）鏈的費用與最小費用增廣鏈定義已知網(wǎng)絡G=(V,A,C,W)

，f是G的可行流，μ為從

vs到vt的關于f的增廣鏈，稱為鏈的μ的費用。若μ*是vs三到vt所有增廣鏈中費用最小的鏈，則稱μ*為最小費用增廣鏈。（4）最小費用流的有關定理定理若f是流量為V（f）的最小費用流，μ是關于f的從vs到vt的一條最小費用增廣鏈，則f經(jīng)過μ調(diào)整流量得到新的可行流f`，f`一定是流量為V(f)+θ

的可行流中的最小費用流。最小費用流算法及算例基本思想：從某個初始的最小費用可行流f（0）（一般為零流）開始，尋找從源點vs到收點vt的關于f（0）的最小費用增廣鏈。在μ中按最大流的標號法的調(diào)整方法進行調(diào)整，只是在調(diào)整量上，要比較增廣鏈μ0上可調(diào)整的量與θ0與V目標-V(f（0）)的量值，若θ0

>V目標-V(f（0）),則μ0*上調(diào)整的量為V目標-V(f（0）)

，算法結(jié)束。若在鏈μ0上按θ0流量進行調(diào)整，得到流值為V(f（1）)

的最小費用可行流f（1）

，在f（1）上尋找從vs到vt的費用最小的增廣鏈μ1，再在μ1按上述方法進行流量調(diào)整，如此反復，直到最小費用可行流的流值達到V目標為止。例求下圖所示的網(wǎng)絡G中，求從vs到vt的目標流值為

25的最小費用流，弧上括號內(nèi)的數(shù)字第一個為容量，第二個為弧上單位流的費用。(17,3)(20,5)(15,4)V2(18,3)(14,5)V3V1(20,8)(12,8)vsvt解

:算法過程第一輪，k=0

取={0}開始，作如圖（a）所示，用DijksTra算法求的中vs到vt的最短路（vs,v1,v3,v4），在網(wǎng)絡G中相應的增廣鏈μ0=(vs,v2,v1,

vt

)上用最大流算法進行流的調(diào)整。

μ0+={（vs,v1）、（v1,v3），（v3,

vt）}μ0-=φ得到f(1)的如圖（b）所示。第二輪，k=1

作圖L(f(1))如圖（c）所示，由于弧上有負權(quán)，所以求最短路不能用DijksTra算法，可用逐次逼近法，最短路為(vs,v3,

vt)，在G