《圖與網(wǎng)絡分析》PPT課件

《《圖與網(wǎng)絡分析》PPT課件》由會員分享，可在線閱讀，更多相關《《圖與網(wǎng)絡分析》PPT課件（80頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、運籌學第六章 圖與網(wǎng)絡分析,機電工程學院 工業(yè)工程系 周宇鵬 辦公電話：86417778-604 手機：13936135705 Email：,哥尼斯堡七橋問題,第六章 圖與網(wǎng)絡分析,2,表示過橋的費用,表示橋單位時間最多通過的車輛數(shù),圖的基本概念 樹圖 最短路徑問題 網(wǎng)絡最大流問題 網(wǎng)絡最小費用流問題,第六章 圖與網(wǎng)絡分析,3,圖與網(wǎng)絡分析的主要內(nèi)容,圖在生產(chǎn)、生活中的應用十分廣泛 物流、交通領域 交通圖 供水、電等 管網(wǎng)圖 通訊 網(wǎng)絡拓撲圖 設施規(guī)劃 組織比賽 表示企業(yè)組織架構(gòu),圖的主要應用領域,第六章 圖與網(wǎng)絡分析,4,樹,第六章 圖與網(wǎng)絡分析,5,第一節(jié) 圖的基本概念（1）,圖: 由點和

2、點與點之間的連線組成，是點和線的集合。 若點與點之間的連線沒有方向，稱為邊，由此構(gòu)成的圖為無向圖。表示為：G =（V，E）。 若點與點之間的連線有方向，稱為弧，這樣的圖稱為有向圖。表示為：G =（V，A）。,v1,v2,v3,v4,v5,v6,e2,e4,e5,e6,e7,e8,e1,e3,e9,頂點 節(jié)點,邊,弧,第一節(jié) 圖的基本概念（4）,完全圖：任意兩點均有邊相連的簡單圖。 環(huán)：端點相重的邊或弧。 多重邊：兩點間有多條邊。 簡單圖：無環(huán)和多重邊的圖。 完全圖的特性 含有n個頂點的完全圖，其邊數(shù)有 條。,第六章 圖與網(wǎng)絡分析,8,第一節(jié) 圖的基本概念（5）,偶圖（二分圖） 圖的頂點能分為兩

3、個互不相交的非空集合V1和V2，使在同一集合中任意兩個頂點均不相鄰，這樣的圖我們稱為偶圖。 V1和V2間每一對不同的頂點都相鄰，這樣圖稱為完全偶圖。如V1中有m個頂點，V2中有n個頂點，其邊數(shù)共mn條。,第六章 圖與網(wǎng)絡分析,9,第二節(jié) 樹圖樹的定義和性質(zhì),樹：無圈的連通圖。 樹的性質(zhì)： 樹是簡單圖（無環(huán)和多重邊） 樹中必然存在次為1的點 n個頂點的樹，邊為n-1條 有n個頂點，n-1條邊的連通圖必然是樹。,第六章 圖與網(wǎng)絡分析,10,懸掛邊,懸掛點,樹枝,根,葉子,第二節(jié) 樹圖最小部分樹,子圖： 圖G1=（V1，E1）和G2=（V2，E2），如V2 V1且E2 E1，則稱G2為G1的子圖。

4、部分圖：如V2= V1且E2 E1，則稱G2為G1的部分圖。 部分樹： G2為G1的部分圖且G2是樹，則稱G2為G1的部分樹。 最小部分樹：樹枝總長最小的部分樹稱為最小部分樹（最小支撐樹）。,第六章 圖與網(wǎng)絡分析,11,v1,v2,v3,v4,e2,e4,e1,e3,e9,v1,v2,v3,v4,e2,e4,e1,圖1,圖2,第二節(jié) 樹圖最小部分樹定理,求圖最小部分樹方法： 避圈法 破圈法 定理：圖G任意點vi，若j是與i相鄰點中距離最近的，則邊i,j必包含于G的最小部分樹中。 推論：把圖G分為V和V兩個集合，兩集合間連線的最短邊必定包含于G的最小生成樹中。,第六章 圖與網(wǎng)絡分析,12,k,i

5、,j,第二節(jié) 樹圖避圈法（1）,第六章 圖與網(wǎng)絡分析,13,6,5,5,1,7,2,3,4,4,v1,v2,v3,v4,v5,v6,是否所有點V,任選一點vi V，其余點V,開始,結(jié)束,找出V和V之間的最短邊，vi，vj 最小部分樹,Vvj =V，V vj =V,是,否,算法流程圖：,已知：點A、B、C、D、E、S、T代表城市，線代表城市之間的道路，線上的數(shù)字代表道路的長度。 求：沿道路架設電線，使所有城市都能通上電，如何架設使總的線路長度最短。,第二節(jié) 樹圖避圈法（2）,第六章 圖與網(wǎng)絡分析,14,S,D,A,T,B,C,E,2,2,4,1,3,4,7,7,5,5,5,1,第二節(jié) 樹圖破圈法

6、,任選一個圈，從圈中去掉權(quán)最大的一條邊。在余下的圖中重復這個步驟，直到得到一不含圈的連通圖為止。,第六章 圖與網(wǎng)絡分析,15,S,D,A,T,B,C,E,2,2,1,3,5,1,第三節(jié) 最短路問題,賦權(quán)無向圖D中的兩個頂點vs和vt，設P是由vs到vt的一條路，把P中所有邊的權(quán)之和稱為路P的權(quán)，記為d(P)。如果路P*的權(quán)d(P*)是由vs到vt的所有路的權(quán)中的最小者，則稱P*是從vs到vt的最短路。最短路P*的權(quán)d(P*)稱為從vs到vt的距離，記為L(vs,vt)。 狄克斯拉算法（Dijkstra） 矩陣算法,第六章 圖與網(wǎng)絡分析,16,第三節(jié) 最短路問題狄克斯拉算法（1）,第六章 圖與網(wǎng)

7、絡分析,17,狄克斯拉算法也稱雙標號算法 假定(1，2)，(2，3)，(3，4)是點1到4的最短路 則(1，2)，(2，3)是點1到3的最短路； (2，3)，(3，4)是點2到4的最短路；,1,2,3,4,5,第三節(jié) 最短路問題狄克斯拉算法（2）,狄克斯拉算法流程： 用dij表示相鄰點vi與vj的距離，若vi與vj不相鄰，則 dij= ，dii = 0，用Lij表示最短距離，求s點到t點的最短路。 從s點出發(fā)，Lss=0。將Lss的值標示在點s上，表示s點已經(jīng)被標號。 找出與s點相鄰點中距離最短的一點，假設是r，則Lsr= Lss+ dsr，將Lsr的值標示在點r上。r點被標號。 從已標號的點

8、出發(fā)，找出與這些點相鄰的所有未標號點，如果有一點p滿足：Lsp = minLss + dsp，Lsr + drp ，則用Lsp的值對p點標號。 重復第3步，直至t點被標號。,第六章 圖與網(wǎng)絡分析,18,第三節(jié) 最短路問題狄克斯拉算法案例一(1),第六章 圖與網(wǎng)絡分析,19,L1=0,5,6,2,4,7,3,2,2,4,6,7,2,1,3,6,7,1,5,L3=2,Lr=minL1+d12,L1+d13=min0+5,0+2=2=L3,求1到7的最短路,第三節(jié) 最短路問題狄克斯拉算法案例一(2),第六章 圖與網(wǎng)絡分析,20,L1=0,5,6,2,4,7,3,2,2,4,6,7,2,1,3,6,7

9、,1,5,L3=2,L2=5,Lp=minL1+d12, L3+d34, L3+d36,=min0+5,2+7,2+4=5=L2,第三節(jié) 最短路問題狄克斯拉算法案例一(3),第六章 圖與網(wǎng)絡分析,21,L1=0,5,6,2,4,7,3,2,2,4,6,7,2,1,3,6,7,1,5,L3=2,L6=6,L2=5,Lp=minL2+d24, L2+d25,L3+d34, L3+d36,=min5+7,5+2,2+7, 2+4=6=L6,第三節(jié) 最短路問題狄克斯拉算法案例一(4),第六章 圖與網(wǎng)絡分析,22,L1=0,5,6,2,4,7,3,2,2,4,6,7,2,1,3,6,7,1,5,L3=2

10、,L2=5,L6=6,L4=7,L5=7,Lp=minL2+d24, L2+d25,L3+d34, L6+d67, L6+d64, L6+d65=min5+7,5+2,2+7, 6+2,6+1,6+6=7=L4=L5,第三節(jié) 最短路問題狄克斯拉算法案例一(5),第六章 圖與網(wǎng)絡分析,23,L1=0,5,6,2,4,7,3,2,2,4,6,7,2,1,3,6,7,1,5,L3=2,L2=5,L6=6,L4=7,L5=7,L7=10,Lp=minL5+d57, L6+d67=min7+3,6+6=10=L7,得到最短路,第三節(jié) 最短路問題狄克斯拉算法案例二,第六章 圖與網(wǎng)絡分析,24,2,3,7,

11、1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,狄克斯拉算法適用于權(quán)大于等于0的網(wǎng)絡。對有向圖、無向圖都適用。 在有向圖中： wij表示vi與vj的最短距離Lij cij表示相鄰點vi與vj的距離 dij,求上圖中從1到8的最短路徑,第六章 圖與網(wǎng)絡分析,25,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1, w1=0,min c12,c14,c16=min0+2,0+1,0+3=min2,1,3=1 X=1,4, w4=1,w1=0,第六章 圖與網(wǎng)絡分析,26,2,3,7,1,8,4,5,6,6,1,3,

12、4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,minc12,c16, w4+c42, w4+c47 = min2, 3,1+10,1+2 = min2,3,11,3 = 2 X=1,2,4, w2=2,w1=0,w4=1,w2=2,第六章 圖與網(wǎng)絡分析,27,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min c13, w2+c23, w2+c25, w4+c47 = min 0+3,2+6,2+5,1+2 = min 3,8,7,3 = 3 X=1,2,4,6, w6=3，w7=3,w2=2,w4=1,w1=0

13、,w6=3,w7=3,第六章 圖與網(wǎng)絡分析,28,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min w2+c23, w2+c25, w4+c47, w6+c67 = min2+6,2+5,1+2,3+4 = min8,7,3,7=3 X=1,2,4,6,7, w7=3,w2=2,w4=1,w1=0,w6=3,w7=3,第六章 圖與網(wǎng)絡分析,29,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min w2+c23, w2+c25, w7+c75, w7+

14、c78 = min2+6,2+5,3+3,3+8 = min8,7,6,11 = 6 X=1,2,4,5,6,7, w5=6,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,第六章 圖與網(wǎng)絡分析,30,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,minw2+c23, w5+c53, w5+c58, w7+c78 = min2+6,6+9,6+4,3+8 = min8,15,10,11 = 8 X=1,2,3,4,5,6,7, w3=8,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,第六

15、章 圖與網(wǎng)絡分析,31,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,min w3+c38, w5+c58, w7+c78 = min 8+6,6+4,3+7 = min 14,10,11 = 10 X=1,2,3,4,5,6,7,8, w8=10,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,第六章 圖與網(wǎng)絡分析,32,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到8的最短路徑為1，4，7，5，8，

16、長度為10。 1到3的最短距離為8,w2=2,w4=1,w1=0,w6=3,w7=3,w5=6,w3=8,w8=10,第三節(jié) 最短路問題矩陣算法,雙標號法能夠計算出網(wǎng)絡中任意一點到其他點的最短距離。 矩陣算法可以一次計算出網(wǎng)絡所有點之間的最短距離。 矩陣算法的基本思想與雙標號法一致。 假定1，2，2，3，3，4是點1到4的最短路 則1，2，2，3是點1到3的最短路； 2，3，3，4是點2到4的最短路；,第六章 圖與網(wǎng)絡分析,33,6,第三節(jié) 最短路問題矩陣算法（第一步）,第六章 圖與網(wǎng)絡分析,5,6,2,4,7,3,2,2,4,6,7,2,1,3,6,7,1,5,d12,d13,d14,d15

17、,d16,d17,d23,d24,d25,d26,d27,d34,d35,d36,d37,d45,d46,d47,d56,d57,d67,dij表示i與j的距離，i和j不相鄰，則令dij= ,34,5,2,2,7,7,4,6,2,1,3,第六章 圖與網(wǎng)絡分析,第三節(jié) 最短路問題矩陣算法（第二步）,先考慮i到j有一個中間點時的情況。 v1到v2的最短距離應該是mind11+d12, d12+d22, d13+d32, d14+d42, d15+d52, d16+d62, d17+d72。即min（d1r+dr2），r=1，2，7。 因此我們可以構(gòu)造一個新矩陣D（1），令dij=mindir+dr

18、j，r=1p。 那么這個矩陣就給出了網(wǎng)絡中直接到達及經(jīng)過一個中間點的最短距離。,35,第六章 圖與網(wǎng)絡分析,36,5,2,7,12,6,第三節(jié) 最短路問題矩陣算法（第三步）,在D（1）的基礎上，構(gòu)造一個新矩陣D（2），令dij（2）=mindir（1）+drj （1），r=1p。 這個矩陣就表示出了網(wǎng)絡中任意兩點，直接到達；經(jīng)過一個點、兩個點和三個點到達的最短距離。 dir（1）表示i直接到r，或i經(jīng)過pa到r， a=1p； drj（1）表示r直接到j，或r經(jīng)過pb到j， b=1p； 如果r=i，j：dij（2）表示i直接到j，或i經(jīng)過一點到j； 如i直接到r，r直接到j： dij（2）表示i

19、經(jīng)過r到j； 如i經(jīng)過pa到r，或r經(jīng)過pb到j： dij（2）表示i經(jīng)過兩點到j； 如i經(jīng)過pa到r，且r經(jīng)過pb到j： dij（2）表示i經(jīng)過三點到j；,第六章 圖與網(wǎng)絡分析,37,第三節(jié) 最短路問題矩陣算法（第k步）,通過歸納可知：dij(k) =mindir(k-1)+drj(k-1)，能夠表示網(wǎng)絡中任意兩點直接到達，或經(jīng)過一個、兩個（2k-1）個中間點到達的最短距離。 假設網(wǎng)絡有p個頂點，那么矩陣算法的結(jié)束條件是：,第六章 圖與網(wǎng)絡分析,38,第六章 圖與網(wǎng)絡分析,39,5,2,7,第四節(jié) 網(wǎng)絡最大流問題,弧的容量：對網(wǎng)絡上的每條弧給出一個最大通過能力c（vi，vj），簡記為cij，

20、c稱為弧的容量。 容量網(wǎng)絡：給定了弧的容量的有向圖D=（V，A，C）叫做一個容量網(wǎng)絡。 容量網(wǎng)絡中通常規(guī)定一個發(fā)點s（源點），一個收點t（匯點）。其他點稱為中間點。,第六章 圖與網(wǎng)絡分析,40,s,t,s,t,第四節(jié) 網(wǎng)絡最大流問題流和可行流,流：網(wǎng)絡上某些弧的一組負載量，?。╲i，vj）的負載量記作f（vi，vj），簡記為fij。若網(wǎng)絡上所有負載fij=0，則稱這個流為零流。 可行流：滿足下面條件的一組流稱為可行流。 容量限制：0 fij cij 中間點平衡： 中間點總流入量 = 總流出量 網(wǎng)絡最大流：就是流量最大的可行流，用v(f)表示從s到t的流量，網(wǎng)絡最大流問題實際上就是要求max v

21、(f)= 。是線性規(guī)劃問題。,第六章 圖與網(wǎng)絡分析,41,第六章 圖與網(wǎng)絡分析,割：將容量網(wǎng)絡中的發(fā)點和收點分割開，使s到t的流中斷的一組弧的集合。,第四節(jié) 網(wǎng)絡最大流問題割和流量,42,3,4,1,t,2,2(0),s,8(8),9(4),6(1),5(5),5(4),9(9),10(8),7(5),Cij(fij),K,第四節(jié) 網(wǎng)絡最大流問題增廣鏈,鏈的方向是從vs到vt，則s到t的弧叫正向弧，t到s的弧叫反向弧。 我們把網(wǎng)絡中fijcij的弧稱為飽和弧，fijcij的弧稱為非飽和??； 增廣鏈：設f是一個可行流，是從vs到vt的一條鏈，若滿足正向弧都是非飽和弧,反向弧都是非零流弧,則稱是可

22、行流f的一條增廣鏈。,第六章 圖與網(wǎng)絡分析,43,s,1,2,t,3,f1 c1,f4 c4,f2 0,f3 0,c2 f2 0,0 f4 c4,第四節(jié) 網(wǎng)絡最大流問題最大流最小割定理,可行流f是最大流的必要條件是圖中不存在關于f的增廣鏈。 網(wǎng)絡中s到t的最大流量等于網(wǎng)絡最小割集的容量。即：v*(f) = c*(V，V)。 求最大流的方法：從一個可行流f開始，尋求關于f的增廣鏈，沿增廣鏈增加可行流的流量得到流量大于f的可行流f*，重復這一過程，直到可行流無增廣鏈為止。 求最大流福德-?？松瓨颂査惴?。,第六章 圖與網(wǎng)絡分析,44,t點得到標號,第六章 圖與網(wǎng)絡分析,45,vs標號為(0, ),開

23、始,選擇已標號的點vi: 若有非飽和弧(vi,vj)，則vj標號(vi, (j)，其中(j) = min(i),uij； 若有非零弧(vj,vi)，則vj標號(vi, (j)，其中(j) = min(i),fji。,t點未標號，標號過程中斷,結(jié)束,2,1,fij=3,cij=5,流量間隙： uij=c12-f12=2 定義(i)表示上一個標號點到i點流量的最大允許調(diào)整值。,f +(t)增廣鏈正向弧 令f*= f (t)增廣鏈反向弧 f 非增廣鏈的弧,6(0),6(1),第四節(jié) 網(wǎng)絡最大流問題最大流標號算法實例(1),第六章 圖與網(wǎng)絡分析,46,46,3,4,1,t,2,2(0),s,8(8),

24、9(4),5(5),5(4),9(9),10(8),7(5),(0, ),(s, 2),(2, 2),(1, 2),(3, 1),(4, 1),9(5),5(3),10(9),7(6),標號vs,9(5),第四節(jié) 網(wǎng)絡最大流問題最大流標號算法實例(2),第六章 圖與網(wǎng)絡分析,47,6(0),3,4,1,t,2,2(0),s,8(8),5(5),5(3),9(9),10(9),7(6),(0, ),(s, 1),(2, 1),(1, 1),標號過程中斷，最大流v*(f) = 14，最小割集為(2,4),(3,t),給出一個初始的可行流零流fij=0,2,3,4,5,6,7,1,f=0,f=0,6

25、(0),2(0),4(0),3(0),7(0),4(0),3(0),1(0),7(0),9(0),8(0),8(0),第六章 圖與網(wǎng)絡分析,48,找到一條從1到7的增廣鏈f(1),2,3,4,5,6,7,1,f=0,(1,8),6(0),2(0),4(0),3(0),7(0),4(0),3(0),1(0),7(0),9(0),8(0),8(0),(0, ),(1,7),(3,1),(2,6),f=0,(3,4),(6,1),第六章 圖與網(wǎng)絡分析,49,最大可調(diào)整量： = 1；調(diào)整鏈的流量：fij(1)=fij+ ,2,3,4,5,6,7,1,f=1,(1,8),6(0),2(0),4(0),3

26、(0),7(1),4(0),3(0),1(1),7(0),9(0),8(1),8(0),(0, ),(1,6),(2,6),f=1,(3,4),(5,6),第六章 圖與網(wǎng)絡分析,50,(4,3),得到新的可行流f(2),最大可調(diào)整量： = 6；調(diào)整鏈的流量：fij(2)=fij(1)+ ,2,3,4,5,6,7,1,f=7,(1,2),6(6),2(0),4(0),3(0),7(1),4(0),3(0),1(1),7(0),9(6),8(1),8(6),(0, ),(1,6),f=7,(3,4),(5,3),(4,3),(4,4),(6,3),第六章 圖與網(wǎng)絡分析,51,得到新的可行流f(3)

27、,最大可調(diào)整量： = 3；調(diào)整鏈的流量：fij(3)=fij(2)+ ,2,3,4,5,6,7,1,f=0,(1,2),6(6),2(0),4(0),3(0),7(4),4(3),3(3),1(1),7(0),9(6),8(4),8(6),(0, ),(1,3),f=0,(3,1),(5,1),(4,1),第六章 圖與網(wǎng)絡分析,52,得到新的可行流f(4),最大可調(diào)整量： = 1；調(diào)整鏈的流量：fij(4)=fij(3)+ ,2,3,4,5,6,7,1,(1,2),6(6),2(0),4(1),3(0),7(5),4(4),3(3),1(1),7(0),9(7),8(4),8(6),(0, )

28、,(1,2),f=11,第六章 圖與網(wǎng)絡分析,53,f=11,已求得最大流v* (f) = c25+c34+c36 = 11,最小割 = (2,5),(3,4),(3, 6),第四節(jié) 網(wǎng)絡最大流問題最大流最小割的意義,網(wǎng)絡中容量決定了網(wǎng)絡的通過能力，最小割是網(wǎng)絡的瓶頸，要提高網(wǎng)絡的運輸能力，首要問題就是要改造最小割的通過能力。 最大流問題應用極為廣泛，例如在交通運輸網(wǎng)絡中有人流、車流、貨物流、供水系統(tǒng)中有水流，金融系統(tǒng)中有現(xiàn)金流，通訊系統(tǒng)中有信息流。 典型應用匹配問題。,第六章 圖與網(wǎng)絡分析,54,第五節(jié) 最小費用流問題,最小費用流問題：在一個關于流的網(wǎng)絡中，人們不僅需要流達到一定的流量，而且

29、每一個流量都有一定的費用，每條弧單位流量費用不一樣。流走的路線不同，總的費用不一樣。最小費用流問題就是在限定流費用基礎上，找出總費用最小的可行流。 最小費用流問題實際上是最短路問題和最大流問題的結(jié)合。 如取消費用限制，就是最大流問題。 如將單位流量的費用當成是兩點間的距離，從s到t調(diào)運一個單位流量的最小費用，等價于求s到t的最短距離。,第六章 圖與網(wǎng)絡分析,55,第五節(jié) 最小費用流問題最小費用流的規(guī)劃描述,設網(wǎng)絡有n個點，令fij為弧(i,j)上的流量，cij為弧的容量，dij為弧通過單位流量的費用，si代表i點的供應量或需求量。ss大于0，st小于0，中間點si =0，當供需平衡（即 si

30、=0）時，將各發(fā)點調(diào)運到各收點，總費用最小問題的線性規(guī)劃模型為：,第六章 圖與網(wǎng)絡分析,56,第五節(jié) 最小費用流問題最小費用流的圖形表示,第六章 圖與網(wǎng)絡分析,57,s2=-2,s4=3,s3=5,s5=-6,s6=-5,s1=5,d24=5,d46=1,d13=3,d35=2,d56=4,d34=4,d12=6,2,3,4,5,6,1,dij 單位流量的費用,若給定容量網(wǎng)絡G=(V,E,C)，除給出邊(vi , vj )E）上的容量（cij C）外，還給出流量的費用 dij0，記為G=(V,E,C,d)，求G的一個可行流 f=fij ，在總的流量W(f)=a(常數(shù))的情況下，使 =,第五節(jié)

31、最小費用流問題最小費用流的一般描述,第六章 圖與網(wǎng)絡分析,58,如要求可行流f必須是最大流，就是最小費用最大流問題。,第五節(jié) 最小費用流問題最小費用流的算法,最小費用流的算法主要有兩種： 原始算法 對偶算法 狄克斯拉算法適用于權(quán)大于等于0的網(wǎng)絡。對偶算法中經(jīng)常會出現(xiàn)權(quán)小于0的情況，因此在介紹對偶算法之前我們首先要介紹最短路的另一種算法逐次逼近算法。,第六章 圖與網(wǎng)絡分析,59,第五節(jié) 最小費用流問題逐次逼近算法(1),狄克斯拉算法計算s到t的最短路wst =minwss+dst,wss+ds1 =8,5=5。 而實際上s到t的最短路應該是(s,1),(1,t)， wst= 8 5 = 3。,第

32、六章 圖與網(wǎng)絡分析,60,s,1,t,Ls=0,Lt=5,-5,5,8,逐次逼近算法與狄克斯拉算法基本思想一致 假定(1，2)，(2，3)，(3，4)是點1到4的最短路 則(1，2)，(2，3)是點1到3的最短路； (2，3)，(3，4)是點2到4的最短路；,第五節(jié) 最小費用流問題逐次逼近算法(2),第六章 圖與網(wǎng)絡分析,61,第六章 圖與網(wǎng)絡分析,61,1,2,3,4,5,第五節(jié) 最小費用流問題逐次逼近算法(3),用wij表示i到j的最短距離，cij表示相鄰點i，j的距離，基于以上定理必有w1j=min(w1i+cij)，i=1n。表示從1到j直接到達或經(jīng)過1個點到達的最短距離。 構(gòu)造算法流

33、程： 令w1j(1) =c1j使用迭代公式w1j(k) =min(w1i(k-1)+cij)，j=1n。如進行到第k步出現(xiàn)w1j(k) =w1j(k-1)，則算法結(jié)束。 k小于等于n-1。也就是說算法最多執(zhí)行n-1步。,第六章 圖與網(wǎng)絡分析,62,第五節(jié) 最小費用流問題逐次逼近算法案例,第六章 圖與網(wǎng)絡分析,63,2,2,4,5,7,8,1,3,6,5,4,3,7,4,6,4,3,2,1,2,3,求1到8的最短路,w1j(1) = c1j = 0,2,5, 3, ,第六章 圖與網(wǎng)絡分析,64,2,2,4,5,7,8,1,3,6,5,4,3,7,4,6,4,3,2,1,2,3,w1j(2) =

34、minw1i(1) + cij = 0,2,0, 3, 6, 11, , ,w1j(2) = c1j = 0,2,0, 3, 6, 11, , ,第六章 圖與網(wǎng)絡分析,65,2,2,4,5,7,8,1,3,6,5,4,3,7,4,6,4,3,2,1,2,3,w1j(3) = minw1i(2) + cij = 0,2,0, 3, 6, 6, , 9,第五節(jié) 最小費用流問題對偶算法(1),求最小費用流的基本思想是：從零流f(0)開始，以費用作為邊的長度，用最短路方法，求出增廣鏈，調(diào)整流量，使可行流逐步達到要求的流量。 G=(V,E,C,d)，f為G的一個可行流 ，為關于f的增廣鏈，d()= 稱為

35、鏈的費用。 若*是s到t增廣鏈中費用最小的，稱*是最小費用增廣鏈。,第六章 圖與網(wǎng)絡分析,66,第五節(jié) 最小費用流問題對偶算法(2),+ = (s,1),(2,3),(3,4),(5,t) - = (2,1), (5,4) d() = (3+4+1+6) (5+7) = 2,第六章 圖與網(wǎng)絡分析,67,1,2,3,4,s,5,t,3,5,4,1,7,6,第五節(jié) 最小費用流問題對偶算法(3),長度網(wǎng)絡： 設網(wǎng)絡G=(V,E,C,d)有可行流f，保持網(wǎng)絡各點不變，用兩條方向相反的弧來代替*上的弧。 如(vi , vj )E，令Lij= 如(vj , vi )為原網(wǎng)絡邊的反向弧，則令 Lji=,第六

36、章 圖與網(wǎng)絡分析,68,第五節(jié) 最小費用流問題對偶算法(4),取零流為初始可行流，即f(0)=fij=0 若有f(k-1)，流量為W(f(k-1) )a，構(gòu)造L(f(k-1) 求長度網(wǎng)絡L(f(k-1)從s到t的最短路。若不存在，則f(k-1)為最大流，不存在流量等于a的可行流，算法終止。若存在則繼續(xù)執(zhí)行第4步。 在最短路的增廣鏈上調(diào)整流量： = f(k)的流量為W(f(k-1) )+，若流量=a則算法結(jié)束。否則執(zhí)行第二步。,第六章 圖與網(wǎng)絡分析,69,第五節(jié) 最小費用流問題對偶算法實例,第六章 圖與網(wǎng)絡分析,70,1,2,3,t,s,5(2),8(1),10(3),2(6),4(2),10(

37、4),第六章 圖與網(wǎng)絡分析,70,在上圖所示的運輸網(wǎng)絡上求流量為10的最小費用流。 弧上給出了弧的容量和單位費用，即cij(dij)。,7(1),Cij(dij),從f(0)開始，構(gòu)造L(f(0)，權(quán)dij0，可用狄克斯拉算法求出最短路(s,2),(2,1),(1,t),第六章 圖與網(wǎng)絡分析,71,1,2,3,t,s,2,1,3,6,2,4, = min8-0,5-0,7-0= 5,1,Cs1=7,Cs2=8,C21=5,按照 = 5 調(diào)整增廣鏈流量得到f(1),第六章 圖與網(wǎng)絡分析,72,第六章 圖與網(wǎng)絡分析,72,1,2,3,t,s,5(5,2),8(5,1),10(0,3),2(0,6)

38、,4(0,2),10(0,4),W(f(1)=510， d(f(1)=51+ 52 + 51=20,7(5,1),Cij(fij,dij),73,構(gòu)造長度網(wǎng)絡L(f(1),第六章 圖與網(wǎng)絡分析,73,第六章 圖與網(wǎng)絡分析,1,2,3,t,s,-2,1,3,6,2,4,由于有負權(quán)，采用逐次逼近法求出最短路(s,1),(1,t),-1,1,-1,10(0,4),7(7,1), =min(cs1 fs1), (c1t f1t) =min(10 0),(7 5) = 2，調(diào)整增廣鏈流量得到f(2),第六章 圖與網(wǎng)絡分析,74,W(f(2)=710， d(f(2)=42+51+ 52 + 71=30,1

39、,2,3,t,s,5(5,2),8(5,1),10(0,3),2(0,6),4(0,2),7(5,1),Cij(fij，dij),10(2,4),75,第六章 圖與網(wǎng)絡分析,75,構(gòu)造長度網(wǎng)絡L(f(2),第六章 圖與網(wǎng)絡分析,75,第六章 圖與網(wǎng)絡分析,1,2,3,t,s,-2,1,3,6,2,4,采用逐次逼近法求出最短路(s,2),(2,3) ,(3,t),-1,-1,-4, = min8 5,10 0,4 0 = 3，調(diào)整增廣鏈流量得到f(3),第六章 圖與網(wǎng)絡分析,76,W(f(3)=10，f(3)就是所求最小費用流，d(f(3)=42+81+ 52+ 33 + 32+ 71=48,1

40、,2,3,t,s,5(5,2),8(5,1),10(0,3),2(0,6),4(0,2),10(2,4),7(7,1),8(8,1),10(3,3),4(3,2),第六章 圖與網(wǎng)絡分析本章小結(jié)(1),樹：無圈的連通圖。 樹中必然存在次為1的點 n個頂點的樹，邊為n-1條 有n個頂點，n-1條邊的連通圖必然是樹。 最小部分樹：樹枝總長最小的部分樹。 避圈法 破圈法,第六章 圖與網(wǎng)絡分析,77,第六章 圖與網(wǎng)絡分析本章小結(jié)(2),最短路問題： 狄克斯拉算法 適用于權(quán)大于等于0的網(wǎng)絡。 能夠計算出網(wǎng)絡任意兩點間的最短距離。 矩陣算法 適用于任何網(wǎng)絡。 能夠計算出網(wǎng)絡所有點間的最短距離。,第六章 圖與網(wǎng)絡分析,78,第六章 圖與網(wǎng)絡分析本章小結(jié)(3),最大流問題 可行流 增廣鏈 正向弧 f 0 最大流最小割定理 v*(f) = c*(V，V)。 最大流標號算法,第六章 圖與網(wǎng)絡分析,79,第六章 圖與網(wǎng)絡分析本章小結(jié)(4),最小費用流問題 實際上是最短路問題和最大流問題的一種結(jié)合。 對偶算法 逐次逼近算法 長度網(wǎng)絡,第六章 圖與網(wǎng)絡分析,80,