圖與網絡分析 - 最大流問題

1、 圖與網絡分析圖與網絡分析 (Graph Theory and Network Analysis) 趙芳玲 圖論是運籌學的一個重要分支，它是建立圖論是運籌學的一個重要分支，它是建立和處理和處理離散類離散類數學模型的一個重要工具數學模型的一個重要工具。用圖。用圖論的方法往往能幫助人們解決一些用其它方法論的方法往往能幫助人們解決一些用其它方法難于解決的問題。圖論的發(fā)展可以追溯到難于解決的問題。圖論的發(fā)展可以追溯到1736年歐拉所發(fā)表的一篇關于解決著名的年歐拉所發(fā)表的一篇關于解決著名的“哥尼斯哥尼斯堡七橋問題堡七橋問題”的論文。由于的論文。由于這種數學模型和方這種數學模型和方法直觀形象，富有啟發(fā)性和

2、趣味性，法直觀形象，富有啟發(fā)性和趣味性，深受人們深受人們的青睞。到目前為止，已被廣泛地應用于系統(tǒng)的青睞。到目前為止，已被廣泛地應用于系統(tǒng)工程、通訊工程、計算機科學及經濟領域。傳工程、通訊工程、計算機科學及經濟領域。傳統(tǒng)的物理、化學、生命科學也越來越廣泛地使統(tǒng)的物理、化學、生命科學也越來越廣泛地使用了圖論模型方法。用了圖論模型方法。圖與網絡分析圖與網絡分析 (Graph Theory and Network Analysis)圖的基本知識圖的基本知識最短路問題最短路問題 樹及最小生成樹樹及最小生成樹最大流問題最大流問題最小費用最大流問題最小費用最大流問題 四、四、 最大流問題最大流問題（一）、（

3、一）、 基本概念基本概念1、網絡網絡：設一個：設一個賦權有向圖賦權有向圖D=（V, A）,在在V中指定一中指定一個發(fā)點個發(fā)點vs和一個收點和一個收點vt ,其它的點叫做中間點。對于其它的點叫做中間點。對于D中的中的每一個?。恳粋€?。╲i , vj）A ,都有一個非負數都有一個非負數cij,叫做弧的容量叫做弧的容量。我們把這樣的圖。我們把這樣的圖D叫做一個容量網絡，簡稱網絡，記做叫做一個容量網絡，簡稱網絡，記做D=（V，A，C，Vs，Vt）。2、流量、可行流、流出量、流入量流量、可行流、流出量、流入量：（1）流量：流量：是指定義在網絡是指定義在網絡D上的每一條弧上的一個上的每一條弧上的一個函數

4、函數 其中其中f(vi ,vj) =fij 叫做弧叫做弧(vi，vj)上的流量。上的流量。 ),()(jijifvvfaf （2）可行流可行流：稱滿足下列條件的流為可行流：稱滿足下列條件的流為可行流： 1）容量約束：對于每一個?。ǎ┤萘考s束：對于每一個弧（vi ,vj）A有有 0 fij cij 。 2）守恒條件：對于所用的中間點守恒條件：對于所用的中間點),tsvvVv 有有 EvvEvvi jjijiijff),(),(頂點頂點vi 的流的流入量入量頂點頂點vi的流的流出量出量則稱則稱f 為為D上的可行流。其流量上的可行流。其流量v(f )為為 EvvEvvsjjsjssjfffv),()

5、,()( EvvjtEvvt jjttjfffv),(),()(發(fā)點發(fā)點vs )(收點收點vt ) （5）零流弧零流弧： fij0 的弧叫做零流弧。的弧叫做零流弧。（6）非零流弧非零流?。?fij0 的弧為非零流弧。的弧為非零流弧。 （3）飽和弧飽和?。嚎尚辛髦锌尚辛髦?fijcij 的弧叫做飽和弧。的弧叫做飽和弧。 （4）非飽和?。悍秋柡突。嚎尚辛髦锌尚辛髦衒ijcij的弧叫做非飽和弧。的弧叫做非飽和弧。2vsv3v4v5v6vtv 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)例例6 6 下圖給出一個可行流下圖給出

6、一個可行流（容量約束、守恒條件容量約束、守恒條件）2vsv3v4v5v6vtv 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1) 圖中圖中 為零流弧，其余為非飽和弧、非零流弧。為零流弧，其余為非飽和弧、非零流弧。) , (63vv例例7 7 下圖給出一個可行流下圖給出一個可行流流量流量v v( (f f ) =8) =8 最最 大大 流流 網絡上的流量最大的可行流稱作的最大流網絡上的流量最大的可行流稱作的最大流所謂最大流問題就是求給定網絡的最大流所謂最大流問題就是求給定網絡的最大流（二）最大流的算法最大流的算法1 1、由

7、圖編寫程序、由圖編寫程序2 2、由、由lingo8.0lingo8.0軟件求最大流軟件求最大流例例8 8 現需要將城市現需要將城市s s 的石油通過管道運送到城市的石油通過管道運送到城市t t, ,中間有中間有4 4個中轉站個中轉站v v1 1, ,v v2 2, ,v v3 3 和和v v4 4，城市與中轉站的，城市與中轉站的連接以及管道的容量如下圖所示，求從城市連接以及管道的容量如下圖所示，求從城市s s 到城到城市市t t 的最大流的最大流 29 5v1v2v3v4 s t 8 79 6 5 10 29 5v1v2v3v4 s t 8 79 6 5 10附程序附程序MODEL:sets:

8、nodes/s,1,2,3,4,t/;arcs(nodes,nodes)/ s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/:c,f;endsetsdata: c= 8 7 5 9 9 2 5 6 10;enddatamax = flow;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)=0);sum(arcs(i,j)|i #eq# 1:f(i,j) = flow;for(arcs:bnd(0,f,c);ENDAi,j,cfs,ti, ti

9、vsi,vffvijijffAj,iVjjiAi,jVjijf )(0 0, t . smax)()( 程序結構程序結構1、集合定義部分（、集合定義部分（sets到到endsets) 2、數據輸入部分（、數據輸入部分（data到到enddata)3、其他部分（優(yōu)化目標和約束）、其他部分（優(yōu)化目標和約束） Global optimal solution found at iteration: 6 Objective value: 14.00000 Variable Value Reduced Cost FLOW 14.00000 0.000000 C( S, 1) 8.000000 0.0000

10、00 C( S, 2) 7.000000 0.000000 C( 1, 2) 5.000000 0.000000 C( 1, 3) 9.000000 0.000000 C( 2, 4) 9.000000 0.000000 C( 3, 2) 2.000000 0.000000 C( 3, T) 5.000000 0.000000 C( 4, 3) 6.000000 0.000000 C( 4, T) 10.00000 0.000000 F( S, 1) 7.000000 0.000000 F( S, 2) 7.000000 0.000000 F( 1, 2) 2.000000 0.000000

11、F( 1, 3) 5.000000 0.000000 F( 2, 4) 9.000000 -1.000000 F( 3, 2) 0.000000 0.000000 F( 3, T) 5.000000 -1.000000 F( 4, 3) 0.000000 1.000000 F( 4, T) 9.000000 0.000000 Global optimal solution found at iteration: 6 Objective value: 14.00000 Variable Value Reduced Cost FLOW 14.00000 0.000000 F( S, 1) 7.00

12、0000 0.000000 F( S, 2) 7.000000 0.000000 F( 1, 2) 2.000000 0.000000 F( 1, 3) 5.000000 0.000000 F( 2, 4) 9.000000 -1.000000 F( 3, 2) 0.000000 0.000000 F( 3, T) 5.000000 -1.000000 F( 4, 3) 0.000000 1.000000 F( 4, T) 9.000000 0.000000 (2,0)(9,5) (5,2)v1v2v3v4 s t( 8,7) (7,7)(9,9)(6,0) (5,5) (10,9)例例9 9

13、 求右圖中網求右圖中網絡絡D D的最大流。的最大流。sets:nodes/s,1,2,3,t/;arcs(nodes,nodes)/ s,1 s,2 s,3 1,2 1,t 2,3 2,t 3,t/:c,f;endsetsdata: c= 5 7 8 5 7 4 6 7;enddatamax = flow;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)=0);sum(arcs(i,j)|i #eq# 1:f(i,j) = flow;for(arcs:bnd(0,f

14、,c);END Global optimal solution found at iteration: 5 Objective value: 18.00000 Variable Value Reduced Cost FLOW 18.00000 0.000000 C( S, 1) 5.000000 0.000000 C( S, 2) 7.000000 0.000000 C( S, 3) 8.000000 0.000000 C( 1, 2) 5.000000 0.000000 C( 1, T) 7.000000 0.000000 C( 2, 3) 4.000000 0.000000 C( 2, T

15、) 6.000000 0.000000 C( 3, T) 7.000000 0.000000 F( S, 1) 5.000000 -1.000000 F( S, 2) 6.000000 0.000000 F( S, 3) 7.000000 0.000000 F( 1, 2) 0.000000 1.000000 F( 1, T) 5.000000 0.000000 F( 2, 3) 0.000000 0.000000 F( 2, T) 6.000000 -1.000000 F( 3, T) 7.000000 -1.000000 F( S, 1) 5.000000 -1.00000 F( S, 2

16、) 6.000000 0.000000 F( S, 3) 7.000000 0.00000 F( 1, 2) 0.000000 1.000000 F( 1, T) 5.000000 0.000000 F( 2, 3) 0.000000 0.000000 F( 2, T) 6.000000 -1.000000 F( 3, T) 7.000000 -1.000000FLOW 18.00000 例例10 10 （多發(fā)點多收點網絡的最大流問題）某種物（多發(fā)點多收點網絡的最大流問題）某種物資有兩個產地資有兩個產地s s1 1和和s s2 2，三個銷地，三個銷地，t t1 1,t,t2 2和和t t3 3

17、。運輸。運輸系統(tǒng)如圖系統(tǒng)如圖7-187-18所示，其中所示，其中v v1 1和和v v2 2是兩個中轉站。所是兩個中轉站。所標數字是線路的最大運輸能力。求從產地到銷地的標數字是線路的最大運輸能力。求從產地到銷地的最大運輸量最大運輸量 。解解 這是一個多發(fā)點多收點的網絡。為了能夠用前面介這是一個多發(fā)點多收點的網絡。為了能夠用前面介紹的算法求它的最大流紹的算法求它的最大流, ,需要把它化成需要把它化成只有一個發(fā)點和只有一個發(fā)點和一個收點的網絡一個收點的網絡. .這并不困難這并不困難. .在網絡中添一個發(fā)點在網絡中添一個發(fā)點v vs s和和一個收點一個收點v vt t以及以及v vs s到到s s1

18、 1, ,s s2 2的弧的弧,t,t1 1,t,t2 2,t,t3 3到到v vt t弧弧 sets:nodes/vs,s1,s2,v1,v2,t1,t2,t3,vt/;arcs(nodes,nodes)/ vs,s1 vs,s2 s1,t1 s1,v1 s1,v2 s2,v2 s2,t3 v1,t1 v1,t2 v2,v1 v2,t2 v2,t3 t1,vt t2,vt t3,vt/:c,f;endsetsdata: c= 27 27 10 5 12 15 12 8 6 3 6 10 18 12 22 ;enddatamax = flow;for(nodes(i)|i #ne# 1 #an

19、d# i #ne# size(nodes): sum(arcs(i,j):f(i,j)-sum(arcs(j,i):f(j,i)=0);sum(arcs(i,j)|i #eq# 1:f(i,j) = flow;for(arcs:bnd(0,f,c);ENDGlobal optimal solution found at iteration: 10 Objective value: 46.00000 Variable Value Reduced Cost FLOW 46.00000 0.000000 F( VS, S1) 19.00000 0.000000 F( VS, S2) 27.00000

20、 0.000000 F( S1, T1) 10.00000 -1.000000 F( S1, V1) 5.000000 -1.000000 F( S1, V2) 4.000000 0.000000 F( S2, V2) 15.00000 0.000000 F( S2, T3) 12.00000 0.000000 F( V1, T1) 8.000000 0.000000 F( V1, T2) 0.000000 0.000000 F( V2, V1) 3.000000 -1.000000 F( V2, T2) 6.000000 -1.000000 F( V2, T3) 10.00000 0.000

21、000 F( T1, VT) 18.00000 0.000000 F( T2, VT) 6.000000 0.000000 F( T3, VT) 22.00000 -1.000000 這個運這個運輸系統(tǒng)的輸系統(tǒng)的最大運量最大運量為為 練習：練習：求下圖網絡的最大流，最大流的流量和最小截集。求下圖網絡的最大流，最大流的流量和最小截集。圖中弧旁的數字是弧的容量。圖中弧旁的數字是弧的容量。20)()(max fva36)()(max fvb2v1v3v4v5v6v7v 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)圖圖c c

22、sets:nodes/v1,v2,v3,v4,v5,v6,v7/;arcs(nodes,nodes)/ v1,v2 v1,v3 v2,v5 v2,v4 v3,v2 v3,v4 v3,v6 v4,v5 v4,v7 v4,v6 v5,v7 v6,v7/:c,f;endsetsdata: c= 13 9 5 6 4 5 5 5 4 4 9 10 ;enddatamax = flow;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)=0);sum(arcs(i,j)|i #eq# 1:f(i,j) = flow;for(arcs:bnd(0,f,c);END2v1v3v4v5v6v7v 13 (11)9 (9)4 (0)5 (5)6(6)5 (4)5 (4)5 (5)4 (2)4 (4)9 (9)10 (9)20)()(max fvcVariable Value Reduced CostVariable Value Reduced Cost