最小費(fèi)用最大流ppt課件

1、( ,)ijv vijw( ,)0ijc v vijc(,)()ijijijv vAC Xc x6.5 最小費(fèi)用最大流問題最小費(fèi)用最大流問題6.5.1 最小費(fèi)用最大流問題的數(shù)學(xué)模型最小費(fèi)用最大流問題的數(shù)學(xué)模型設(shè)網(wǎng)絡(luò)D=(V,A,W), 每條弧 除了容量 以 外， 還給出單位流量的費(fèi)用 （簡(jiǎn)記為 ）。 這樣，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)用。 (,)min()ijijijv vAC Xc x(,)11min()0. .0,( ,)ijijijv vAnnijjijjijijijC Xc x

2、XXstxwv vA最小費(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)用費(fèi)用 最小費(fèi)用最大流最小費(fèi)用最大流 從某個(gè)可行流出發(fā)，從某個(gè)可行流出發(fā)，找到關(guān)于這個(gè)可行流找到關(guān)于這個(gè)可行流的一條增廣鏈，沿著的一條增廣鏈，沿著 該增廣鏈調(diào)整該增廣鏈調(diào)整X，對(duì)，對(duì)新的可行流試圖尋求新的可行流試圖尋求關(guān)于它的增廣鏈，如關(guān)于它的增廣鏈，如此反復(fù)直至最大流此反復(fù)直至最大流 ()()ijijijijijijuuucxcxc x(

3、)ijijuucc,X( ,)ijv v(,)(,)()()ijijijijijijv vAv vAC XC Xc xc x ijijijijuuc xc x想象： 當(dāng)沿著一條關(guān)于可行流X的增廣鏈 以 調(diào)整X， 得到新的可行流 且有 這里第三個(gè)等式只是因?yàn)閷?duì) 之外的 來說 ()f XX,ijijxx( ),ijijuuccc( )c,X即費(fèi)用均一樣。 記 稱 是沿增廣鏈 當(dāng)可行流增加單位流值時(shí)費(fèi)用的增量， 簡(jiǎn)稱為增廣鏈 的單位費(fèi)用增量。可以證明， 若X是流量為f(X)的所有可行流中費(fèi)用最小者， 而 是關(guān)于X的所有增廣鏈中費(fèi)用最小的增廣鏈，則沿 去調(diào)整X， 得到的可行流 就是流量為的所有可行流中

4、的最小費(fèi)用流， 這樣， 當(dāng),( ,),ijijijijijijijcxwww v vxw若若( ,)ijv v( ,)ijv v0,ijc (,),jiv v:ijw是最大流時(shí)， 即為最小費(fèi)用最大流。注意到 故X=0必是流量為 0的最小費(fèi)用流。這樣， 總可以從X=0開始。 一般地， 若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) ,0(,),0ijijjijiijcxww v vx若若1vnv在D(X)中長(zhǎng)度為 的弧可以略去。 故在網(wǎng)絡(luò)D中

5、尋找關(guān)于 X的最小費(fèi)用增廣鏈就等價(jià)于在賦權(quán)有向圖D(X)中， 尋找從 到 的最短 路。 :1,kk(1),kX,( )kP( ),kP1v(0)0,X: 0;k ( )kXnv( )kX( )();kD X( )()kD X算法步驟：算法步驟： Step1: 確定初始可行流 令 Step2: 記 為經(jīng)過k次調(diào)整得到的最小費(fèi)用流， 構(gòu)造 Step3: 求 中 到 的最短路 假設(shè) 不存在，那么 是最小費(fèi)用最大流，算法終止；否則，轉(zhuǎn)Step4； Step4: 在D中找對(duì)應(yīng)的增廣鏈 按式6.4.4調(diào)整流量，得可行流 令 轉(zhuǎn)Step2。(,).ijijcw1v例例6.5.1 求圖6.5.1的最小費(fèi)用最大

6、流，弧旁的數(shù)字為2v3v4v5v(1,2)(3,1)(2,3)(5,6)(1,2)(1,3)(3,4)圖圖6.5.1(0)0,X(0)().D X解解: 取 見圖6.4.7a）， 1v2v3v4v5v(1,2,0)(3,1,0)(2,3,0)(5,6,0)(1,2,0)(1,3,0)(3,4,0)圖圖6.5.1a）構(gòu)造 (0)1 3 5,Pv v v因沒有負(fù)權(quán)弧， 故可用Dijkstra算法求得最短路為 見圖6.5.1b）。 1v2v3v4v5v1325113圖圖6.5.1b）(0)1 3 5v v vmin 1 0,301(1)X增廣鏈 調(diào)整后 如圖6.5.1c）。 1v2v3v4v5v(1

7、,2,0)(3,1,1)(2,3,0)(5,6,0)(1,2,0)(1,3,1)(3,4,0)圖圖6.5.1c）(1)()D X(1)1 2 3 5Pv v v v構(gòu)造 得到 如圖6.5.1d）。 1v2v3v4v5v1325113圖圖6.5.1d）1(1)1 2 3 5v v v vmin 20,30,3 12(2),X調(diào)整得 如圖6.5.1e）。 1v2v3v4v5v(1,2,2)(3,1,1)(2,3,2)(5,6,0)(1,2,0)(1,3,3)(3,4,0)圖圖6.5.1e）(2)(),D X構(gòu)造 如圖6.5.1f）。 1v2v3v4v5v1325113圖圖6.5.1f）11v(2)

8、X(2)()1 2+3 1+5 0+2 2+1 0+3 0+1 3c X =12(2)()3.f X顯然， 與 關(guān)聯(lián)的弧指向 1,v不存在 1vnv到 的最短路。 故圖6.5.1e所示的 為最小費(fèi)用 最大流。 費(fèi)用 流值 三、最小費(fèi)用最大流例例6.8.3 用LINGO軟件求解例6.5.1。解：解：程序如下：model:sets:nodes/1,2,3,4,5/:d;arcs(nodes,nodes)/1,2 1,3 2,3 2,4 3,4 3,5 4,5/:c,u,f;endsetsmin=sum(arcs:c*f);for(nodes(i)|i#ne#1#and#i#ne#size(node

9、s):sum(arcs(i,j):f(i,j)-sum(arcs(j,i):f(j,i)=d(i);sum(arcs(i,j)|i#eq#1:f(i,j)=d(1);for(arcs:Bnd(0,f,u);data:u=2 1 3 6 2 3 4;c=1 3 2 5 1 1 3;d=3 0 0 0 -3;enddataend運(yùn)行結(jié)果：Global optimal solution found at iteration: 0 Objective value: 12.00000Variable Value Reduced CostD( 1) 3.000000 0.000000D( 2) 0.000

10、000 0.000000D( 3) 0.000000 0.000000D( 4) 0.000000 0.000000D( 5) -3.000000 0.000000C( 1, 2) 1.000000 0.000000C( 1, 3) 3.000000 0.000000C( 2, 3) 2.000000 0.000000C( 2, 4) 5.000000 0.000000C( 3, 4) 1.000000 0.000000C( 3, 5) 1.000000 0.000000C( 4, 5) 3.000000 0.000000U( 1, 2) 2.000000 0.000000U( 1, 3) 1

11、.000000 0.000000U( 2, 3) 3.000000 0.000000U( 2, 4) 6.000000 0.000000U( 3, 4) 2.000000 0.000000U( 3, 5) 3.000000 0.000000U( 4, 5) 4.000000 0.000000F( 1, 2) 2.000000 0.000000F( 1, 3) 1.000000 0.000000F( 2, 3) 2.000000 0.000000F( 2, 4) 0.000000 5.000000F( 3, 4) 0.000000 3.000000F( 3, 5) 3.000000 0.0000

12、00F( 4, 5) 0.000000 0.000000結(jié)果說明，最小費(fèi)用為結(jié)果說明，最小費(fèi)用為12，此時(shí)，流值為，此時(shí)，流值為3。例例6.8.6 用MATLAB軟件求解例6.5.1。 MATLAB編程如下：解：解：f=zeros(7,1);f(1)=1;f(2)=1;g=-f;aeq=1,0,-1,-1,0,0,0 0,1,0,1,-1,0,-1 0,0,1,0,1,-1,0; beq=zeros(3,1);lb=zeros(7,1); ub=2 1 6 3 2 4 3;x,fval,exitflag,output,lambda=linprog(g,aeq,beq,lb,ub);f1=1,3

13、,5,2,1,3,1;aq=1 1 zeros(1,5);aeq1=aq;aeq;beq1=-fval;beq;z,favl1,exitflag,output,lambda=linprog(f1,aeq1,beq1,lb,ub);zfavl1運(yùn)行結(jié)果如下：z = 2.0000 1.0000 0.0000 2.0000 0.0000 0.0000 3.0000favl1 = 12.0000結(jié)果說明最大流值為3，最小費(fèi)用為12。 可以看出，最小費(fèi)用最大流問題其實(shí)就是在最大流問題基礎(chǔ)上，再進(jìn)行一次線性規(guī)劃問題的計(jì)算得出。18，410，17，2 5，310，6 2，2 4，svtv1v3v2vstvv

14、例：求圖中從的最小費(fèi)用最大流。000fWf解：從開始，構(gòu)造加權(quán)網(wǎng)絡(luò)圖：00f 1412362svtv1v3v2v 8 0 10 0 7 0 5 0 10 0 2 0 4 0svtv1v3v2v0Wf01344+5+5+51055ff1Wf0154 8 5 10 0 7 5 5 5 10 0 2 0 4 0svtv1v3v2v1412362svtv1v3v2v114+2+22127ff2Wf0164 8 5 10 2 7 7 5 5 10 0 2 0 4 0svtv1v3v2v41412362svtv1v3v2v41+3+3+332310ff3Wf04725 8 8 10 2 7 7 5 5 1

15、0 3 2 0 4 3svtv1v3v2v321412362svtv1v3v2v4+1+1-1+143111ff 4Wfstvv 的最短路不存在，已經(jīng)求得最小費(fèi)用的最大流。最大流為：最大流為：3+8=7+4=11最小費(fèi)用為：最小費(fèi)用為：34+81+42+71+43+42=55 8 8 10 3 7 7 5 4 10 4 2 0 4 4svtv1v3v2v04253sv1v32141262tv3v2v4sets: nodes/s,1,2,3,t/:d; arcs(nodes, nodes)/ s,1 s,2 2,1 2,3 1,t 1,3 3,t/: c, u, f;endsetsdata: d

16、 = 11 0 0 0 -11; c = 4 1 2 3 1 6 2; u = 10 8 5 10 7 2 4;enddatamin=sum(arcs:c*f);for(nodes(i) | 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)|i #eq# 1 : f(i,j)=d(1);for(arcs:bnd(0,f,u); Global optimal solution found at iteration: 2 Objective value:

17、 55.00000 Variable Value Reduced Cost D( S) 11.00000 0.000000 D( 1) 0.000000 0.000000 D( 2) 0.000000 0.000000 D( 3) 0.000000 0.000000 D( T) -11.00000 0.000000 C( S, 1) 4.000000 0.000000 C( S, 2) 1.000000 0.000000 C( 2, 1) 2.000000 0.000000 C( 2, 3) 3.000000 0.000000 C( 1, T) 1.000000 0.000000 C( 1,

18、3) 6.000000 0.000000 C( 3, T) 2.000000 0.000000 U( S, 1) 10.00000 0.000000 U( S, 2) 8.000000 0.000000 U( 2, 1) 5.000000 0.000000 U( 2, 3) 10.00000 0.000000 U( 1, T) 7.000000 0.000000 U( 1, 3) 2.000000 0.000000 U( 3, T) 4.000000 0.000000 F( S, 1) 3.000000 0.000000 F( S, 2) 8.000000 -1.000000 F( 2, 1)

19、 4.000000 0.000000 F( 2, 3) 4.000000 0.000000 F( 1, T) 7.000000 -2.000000 F( 1, 3) 0.000000 5.000000 F( 3, T) 4.000000 0.000000 Row Slack or Surplus Dual Price 1 55.00000 -1.000000 2 0.000000 -3.000000 3 0.000000 -5.000000 4 0.000000 -2.000000 5 0.000000 -7.000000ie,ijw6.6 中國(guó)郵遞員問題中國(guó)郵遞員問題中國(guó)郵遞員問題：（中國(guó)郵

20、遞員問題：（1962年，管梅谷年，管梅谷 ，中國(guó)，中國(guó)) 某一郵遞員負(fù)責(zé)某街區(qū)的郵件投遞工作， 要從郵局出發(fā)走遍負(fù)責(zé)的所有街道， 每次都再回到郵局， 應(yīng)如何安排投遞路線， 他使所走的總路程最短。 圖論語言圖論語言 給定一個(gè)連通圖，在每個(gè)邊給定一個(gè)連通圖，在每個(gè)邊 上賦予非負(fù)權(quán)數(shù)上賦予非負(fù)權(quán)數(shù) 要求一個(gè)回路，過每邊至少一次，并使回路的要求一個(gè)回路，過每邊至少一次，并使回路的總權(quán)數(shù)最小。總權(quán)數(shù)最小。iv ,Giv定義定義6.6.1 設(shè) G為連通圖，若存在一條回路，經(jīng)過每條邊一次且僅一次，稱這條回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖。定理定理6.6.1 連通圖G是歐拉圖當(dāng)且僅當(dāng) G中的點(diǎn)全為偶點(diǎn)

21、。證明：證明： 必要性。 設(shè)G為歐拉圖， 故存在一條回路經(jīng)過G中所有的邊， 這條回路上， 邊不重復(fù)但頂點(diǎn)可能重復(fù)。 對(duì)任一點(diǎn) 只要它在回路中出現(xiàn)一次， 必關(guān)聯(lián)兩條邊。 故 可以在回路中重復(fù)出現(xiàn)， 但點(diǎn)的次必為偶數(shù)。ivGG，1v2,v3,vCC，1vC。 充分性。 設(shè)G中的點(diǎn)全為偶點(diǎn)， 如從 出發(fā)， 經(jīng)關(guān)聯(lián)邊到 而 2v為偶點(diǎn)， 故必經(jīng)關(guān)聯(lián)邊到另一點(diǎn) 如此下去， 每條邊僅取一次。 由于G的點(diǎn)數(shù)有限， 所以沿這條路 必可走回 得到一條回路 假設(shè) 經(jīng)過G中所有邊， 那么 C即為歐拉回路。 否 則從G中去掉 C后得到子圖 那么 中每個(gè)頂點(diǎn) 的次數(shù)仍為偶數(shù)， 因G為連通圖， 故 C與 G至少有 一個(gè)頂點(diǎn)與 重合， 在 G中從 iv出發(fā)， 反復(fù) C的 方法， 得到回路 C把 C和 組合在一起， 如果