教案18_圖論最小費(fèi)用最大流

1、 第五節(jié) 最小費(fèi)用最大流問(wèn)題 網(wǎng)絡(luò)網(wǎng)絡(luò)D=（V，A，C）,每一?。恳换。╲i，vj）A，給，給出（出（vi，vj）上單位流的費(fèi)用）上單位流的費(fèi)用b(vi，vj)0，（簡(jiǎn)記，（簡(jiǎn)記bij）。）。 最小費(fèi)用最大流問(wèn)題：最小費(fèi)用最大流問(wèn)題： 求一個(gè)最大流求一個(gè)最大流 f，使流的總費(fèi)用，使流的總費(fèi)用 A),( )( jivvijijf bfb取最小值。取最小值。一、求解原理一、求解原理 設(shè)對(duì)可行流設(shè)對(duì)可行流 f 存在增廣鏈存在增廣鏈 ，當(dāng)沿，當(dāng)沿 以以 =1調(diào)整調(diào)整f，得新的可行流得新的可行流 f 時(shí)，時(shí)，(顯然顯然 V(f )=V(f )+1)，兩流的費(fèi)，兩流的費(fèi)用之差用之差 b( f )-b(

2、f) ) () ( ijijijijijijffbffb稱為增廣鏈稱為增廣鏈 的費(fèi)用。的費(fèi)用。最小費(fèi)用最大流的原理的主要依據(jù)：最小費(fèi)用最大流的原理的主要依據(jù)： 若若f 是流值為是流值為V（f ）的所有可行流中費(fèi)用最小者）的所有可行流中費(fèi)用最小者,而而 是關(guān)于是關(guān)于f 的所有增廣鏈中費(fèi)用最小的增廣鏈的所有增廣鏈中費(fèi)用最小的增廣鏈,則沿則沿 以以 去調(diào)整去調(diào)整 f ,得可行流得可行流 f ，f 就是流量為就是流量為V(f )+ 的所有可行流中費(fèi)用最小的可行流。這樣，當(dāng)?shù)乃锌尚辛髦匈M(fèi)用最小的可行流。這樣，當(dāng) f 是是最大流時(shí)，最大流時(shí)， f 就是所求的最小費(fèi)用最大流。就是所求的最小費(fèi)用最大流。b(

3、 f ) -b( f ) ijijbb+1-1 構(gòu)造賦權(quán)有向圖構(gòu)造賦權(quán)有向圖W( f ),它的頂點(diǎn)是它的頂點(diǎn)是D的頂點(diǎn)的頂點(diǎn),W(f )中中弧及其權(quán)弧及其權(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èi)用流，）的最小費(fèi)用流， 求求出關(guān)于出關(guān)于f 的最小費(fèi)用增廣鏈。的最小費(fèi)用增廣鏈。若（若（vi，vj）A，且，且fij=0(零?。┝慊。?，若若(vi，v

4、j )A，且，且fij=cij(飽和弧飽和弧),費(fèi)用費(fèi)用若（若（vi，vj）A，且，且0fijcij vj4vi3.2則（則（vi，vj）W（f ），且），且wij= bij 及及（ vj ， vi ）W（f ），且），且wji= - bijvjvi4vivj-4新網(wǎng)絡(luò)新網(wǎng)絡(luò)W（f ）成為流）成為流f 的的(費(fèi)用費(fèi)用)長(zhǎng)度網(wǎng)絡(luò)。長(zhǎng)度網(wǎng)絡(luò)。由增廣鏈費(fèi)用的概念及網(wǎng)絡(luò)由增廣鏈費(fèi)用的概念及網(wǎng)絡(luò)W（f ）的定義，知）的定義，知 在網(wǎng)絡(luò)在網(wǎng)絡(luò)D中尋求關(guān)于可行流中尋求關(guān)于可行流f 的最小費(fèi)用增廣鏈，的最小費(fèi)用增廣鏈，等價(jià)于在網(wǎng)絡(luò)等價(jià)于在網(wǎng)絡(luò)W（f ）中尋求從）中尋求從vs到到vt的最短路。的最短路。二、最小

5、費(fèi)用最大流算法二、最小費(fèi)用最大流算法算法步驟：算法步驟：第第1步：確定初始可行流步：確定初始可行流f 0 =0，令，令k=0；第第2步：記經(jīng)步：記經(jīng) k 次調(diào)整得到的最小費(fèi)用流為次調(diào)整得到的最小費(fèi)用流為f k，構(gòu)造，構(gòu)造 增量網(wǎng)絡(luò)增量網(wǎng)絡(luò)W（f k）；）；第第3步：在步：在W（f k）中，尋找）中，尋找vs到到vt的最短路。若不存的最短路。若不存 在最短路（即最短路路長(zhǎng)是在最短路（即最短路路長(zhǎng)是），則），則f k 就是就是 最小費(fèi)用最大流，若存在最短路，則此最短最小費(fèi)用最大流，若存在最短路，則此最短 路即為原網(wǎng)絡(luò)路即為原網(wǎng)絡(luò)D中相應(yīng)的可增廣鏈中相應(yīng)的可增廣鏈，轉(zhuǎn)入第，轉(zhuǎn)入第 4步。步。 第第4

6、步：在增廣鏈步：在增廣鏈上對(duì)上對(duì)f k 按下式進(jìn)行調(diào)整，調(diào)整量按下式進(jìn)行調(diào)整，調(diào)整量 為為 = min kijukijijuf)fc min , -(min -令令 uvv fuvvf u v,v ffjikijjikijjikijkij ),( ),( )( -1得新的可行流得新的可行流f k+1 , 返回第返回第2步。步。 vsv2v34v1vt621132(a) w(f0)例例 求下圖所示網(wǎng)絡(luò)的最小費(fèi)用最大流。弧旁數(shù)字為求下圖所示網(wǎng)絡(luò)的最小費(fèi)用最大流。弧旁數(shù)字為 （bij，cij）。）。v2v3（4，10）v1vsvt（6，2）（2，5）(1，8)（1，7）（3，10）(2，4)解：（解

7、：（1）取初始）取初始可行流可行流f 0 = 0； （2）按算法要求構(gòu)造）按算法要求構(gòu)造長(zhǎng)度網(wǎng)絡(luò)長(zhǎng)度網(wǎng)絡(luò)W（f 0 ），），求出從求出從vs到到vt的最短路。的最短路。（3）在原網(wǎng)絡(luò)）在原網(wǎng)絡(luò)D中，與中，與這條最短路對(duì)應(yīng)的增廣這條最短路對(duì)應(yīng)的增廣鏈為鏈為 =（vs，v2，v1，vt）。）。 （3）在原網(wǎng)絡(luò)）在原網(wǎng)絡(luò)D中，中， 與這條最短路對(duì)應(yīng)與這條最短路對(duì)應(yīng) 的增廣鏈為的增廣鏈為 : （4）在）在上進(jìn)行調(diào)整，上進(jìn)行調(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，

8、vt）v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)（7，5）（10，0）(4，0)(b) f 1 按照上述算法依次得按照上述算法依次得f 1 ，f 2 ，f 3 ，f 4 ，流量依次，流量依次為為V(f 1)=5，V(f 2)=7，V(f 3)=10，V( f 4)=11， 構(gòu)造相應(yīng)構(gòu)造相應(yīng)的增量網(wǎng)絡(luò)為的增量網(wǎng)絡(luò)為W(f 1)，W(f 2)，W(f 3)，W( f 4), 如圖如圖(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

9、) f 1V(f 1 ) = 5v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)（7，5）（10，0）(4，0)(b) f 1v2v3（10，2）v1vsvt（2，0）（5，5）(8，5)（7，7）（10，0）(4，0)(d) f 2 V( f 2)=7vt2v2v3v1vs6-2-1-13W（f （1） （c）411v2v3（10，2）v1vsvt（2，0）（5，5）(8，5)（7，7）（10，0）(4，0)(d) f 2 V( f 2)=7 w(f 2 ) (e)v1vs-1v2v3-46-2-1341vt2v2v3（10，2）v1vsvt（2，0）（5，5）(8，8)（7，

10、7）（10，3）(4，3)(f) f 3 V( f 3)=10v2v3（10，2）v1vsvt（2，0）（5，5）(8，8)（7，7）（10，3）(4，3)(f) f 3 V( f 3)=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) f 4 V( f 4)=11 圖（圖（i）中，不存在從）中，不存在從vs到到vt的最短路，所以的最短路，所以f 4為為最小費(fèi)用最大流。最小費(fèi)用最大流。問(wèn)題：（問(wèn)題：（1）如何求網(wǎng)絡(luò)）如何求網(wǎng)絡(luò)W（f k）中的）中的vs到到vt最短

11、路？最短路？ （2）如何判斷無(wú)）如何判斷無(wú)vs到到vt的最短路？的最短路？v2v3（10，3）v1vsvt（2，0）（5，4）(8，8)（7，7）（10，4）(4，4)(h) f 4 V( f 4)=11vt-2v2v3-4v1vs6-2-1-13（i） W（f 4） 4-32最小費(fèi)用給定流最小費(fèi)用給定流作業(yè)：作業(yè)：1. 用標(biāo)號(hào)法求下網(wǎng)絡(luò)中從點(diǎn)用標(biāo)號(hào)法求下網(wǎng)絡(luò)中從點(diǎn)v1到到v7的最大流。的最大流。v1 v2v3v4v5v6v7693742513476每條弧旁的數(shù)字為該段弧的容量。每條弧旁的數(shù)字為該段弧的容量。上面網(wǎng)絡(luò)中弧表示單行道，試確定上面網(wǎng)絡(luò)中弧表示單行道，試確定v2v3段道路的方向。段道

12、路的方向。2. 求下圖所示網(wǎng)絡(luò)的最小費(fèi)用最大流求下圖所示網(wǎng)絡(luò)的最小費(fèi)用最大流,每弧旁的數(shù)每弧旁的數(shù)字是字是( bij . cij ) 。(1,4)vsvt(3.5)(2.1)(4,2)(2.1)3.3)(2.5)(1.3)(4.2) 3.下表給出某運(yùn)輸問(wèn)題的產(chǎn)銷(xiāo)平衡表與單位運(yùn)價(jià)下表給出某運(yùn)輸問(wèn)題的產(chǎn)銷(xiāo)平衡表與單位運(yùn)價(jià)表。將此問(wèn)題轉(zhuǎn)化為最小費(fèi)用最大流問(wèn)題，畫(huà)出網(wǎng)表。將此問(wèn)題轉(zhuǎn)化為最小費(fèi)用最大流問(wèn)題，畫(huà)出網(wǎng)絡(luò)圖并求數(shù)值解。絡(luò)圖并求數(shù)值解。產(chǎn)地 銷(xiāo)地123產(chǎn)量AB2030242252087銷(xiāo)量456最小總費(fèi)用為最小總費(fèi)用為240 sBA321t(22,7)(24,8)(5,8)(30,7)(0,5)(0,6)(20,8)(0,7)(0,4)(20,8)(0,8)弧旁數(shù)字為弧