最小費(fèi)用最大流問題

《最小費(fèi)用最大流問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、§6.5最小費(fèi)用最大流問題§6.5.1最小費(fèi)用最大流問題的數(shù)學(xué)模型設(shè)網(wǎng)絡(luò)D=(V,A,W),每條弧除了容量以外，還給出單位流量的費(fèi)用（簡記為）。這樣，D就成為一個(gè)帶費(fèi)用的網(wǎng)絡(luò)，記為D=(V,A,W,C),其中,C稱為費(fèi)用函數(shù)。設(shè)X為D上的一個(gè)可行流，稱（6.5.1）為可行流X的費(fèi)用。最小費(fèi)用最大流問題，即要求一個(gè)最大流X，使總運(yùn)輸費(fèi)用（6.5.2）達(dá)到最小值，則有最小費(fèi)用最大流問題的數(shù)學(xué)模型（6.5.3）§6.5.2最小費(fèi)用最大流問題的算法尋求最大流的方法最小費(fèi)用最小費(fèi)用最大流從某個(gè)可行流出發(fā)，找到關(guān)于這個(gè)可行流的一條增廣

2、鏈，沿著該增廣鏈調(diào)整X，對新的可行流試圖尋求關(guān)于它的增廣鏈，如此反復(fù)直至最大流設(shè)想：當(dāng)沿著一條關(guān)于可行流X的增廣鏈以調(diào)整X，得到新的可行流且有這里第三個(gè)等式只是因?yàn)閷χ獾膩碚f即費(fèi)用均一樣。記稱是沿增廣鏈當(dāng)可行流增加單位流值時(shí)費(fèi)用的增量，簡稱為增廣鏈的單位費(fèi)用增量?？梢宰C明，若X是流量為f(X)的所有可行流中費(fèi)用最小者，而是關(guān)于X的所有增廣鏈中費(fèi)用最小的增廣鏈，則沿去調(diào)整X，得到的可行流就是流量為的所有可行流中的最小費(fèi)用流，這樣，當(dāng)是最大流時(shí)，即為最小費(fèi)用最大流。注意到故X=0必是流量為0的最小費(fèi)用流。這樣，總可以從X=0

3、開始。一般地，若X是流量f(X)的最小費(fèi)用流，為了尋求關(guān)于X的最小費(fèi)用增廣鏈，構(gòu)造一個(gè)賦權(quán)有向圖D(X)，它的頂點(diǎn)是原網(wǎng)絡(luò)D的頂點(diǎn)，而把D中的每一條弧變成兩個(gè)相反方向的弧和定義D(X)中弧的權(quán)在D(X)中長度為的弧可以略去。故在網(wǎng)絡(luò)D中尋找關(guān)于X的最小費(fèi)用增廣鏈就等價(jià)于在賦權(quán)有向圖D(X)中，尋找從到的最短路。算法步驟：Step1:確定初始可行流令Step2:記為經(jīng)過k次調(diào)整得到的最小費(fèi)用流，構(gòu)造Step3:求中到的最短路若不存在，則是最小費(fèi)用最大流，算法終止；否則，轉(zhuǎn)Step4；Step4:在D中找對應(yīng)的增廣鏈按式（6.

4、4.4）調(diào)整流量，得可行流令轉(zhuǎn)Step2。例6.5.1求圖6.5.1的最小費(fèi)用最大流，弧旁的數(shù)字為圖6.5.1解:取見圖6.4.7（a），圖6.5.1（a）構(gòu)造因沒有負(fù)權(quán)弧，故可用Dijkstra算法求得最短路為見圖6.5.1（b）。圖6.5.1（b）增廣鏈調(diào)整后如圖6.5.1（c）。圖6.5.1（c）構(gòu)造得到如圖6.5.1（d）。圖6.5.1（d）調(diào)整得如圖6.5.1（e）。圖6.5.1（e）構(gòu)造如圖6.5.1（f）。圖6.5.1（f）顯然，與關(guān)聯(lián)的弧指向不存在到的最短路。故圖6.5.1（e）所示的為最小費(fèi)用最大流。費(fèi)用

5、流值三、最小費(fèi)用最大流例6.8.3用LINGO軟件求解例6.5.1。解：程序如下：model:sets:nodes/1,2,3,4,5/:d;arcs(nodes,nodes)/1,21,32,32,43,43,54,5/:c,u,f;endsetsmin=@sum(arcs:c*f);@for(nodes(i)

6、i#ne#1#and#i#ne#@size(nodes):@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=d(i));@sum(arcs(i,j)

7、i#eq#1:f(i

8、,j))=d(1);@for(arcs:@Bnd(0,f,u));data:u=2136234;c=1325113;d=3000-3;enddataend運(yùn)行結(jié)果：Globaloptimalsolutionfoundatiteration:0Objectivevalue:12.00000VariableValueReducedCostD(1)3.0000000.000000D(2)0.0000000.000000D(3)0.0000000.000000D(4)0.0000000.000000D(5)-3.0000000.0

9、00000C(1,2)1.0000000.000000C(1,3)3.0000000.000000C(2,3)2.0000000.000000C(2,4)5.0000000.000000C(3,4)1.0000000.000000C(3,5)1.0000000.000000C(4,5)3.0000000.000000U(1,2)2.0000000.000000U(1,3)1.0000000.000000U(2,3)3.0000000.000000U(2,4)6.0000000.000000U(3,4)2.0000000.0

10、00000U(3,5)3.0000000.000000U(4,5)4.0000000.000000F(1,2)2.0000000.000000F(1,3)1.0000000.000000F(2,3)2.0000000.000000F(2,4)0.0000005.000000F(3,4)0.0000003