運籌學-圖與網(wǎng)絡模型以及最小費用最大流

1、圖與網(wǎng)絡的基本概念與模型圖與網(wǎng)絡的基本概念與模型最短路問題最短路問題最小生成樹問題最小生成樹問題最大流問題最大流問題最小費用最大流問題最小費用最大流問題 長江漢江您能從武漢理工大學出發(fā)走過您能從武漢理工大學出發(fā)走過每座橋且只走一次然后回到學每座橋且只走一次然后回到學校嗎校嗎? ?近代圖論的歷史可追溯到近代圖論的歷史可追溯到18世紀的七橋問題世紀的七橋問題穿過穿過Knigsberg城的七座橋，要求每座橋通過一次且僅通過一次。城的七座橋，要求每座橋通過一次且僅通過一次。 這就是著名這就是著名的的“哥尼斯堡哥尼斯堡 7 橋橋”難題。難題。Euler1736年證明了不可能存在這樣年證明了不可能存在這樣

2、的路線。的路線。 圖論中圖是由點和邊構成，可以反映一些對象之間的關系。圖論中圖是由點和邊構成，可以反映一些對象之間的關系。 一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關系并不是重要的。直，對于反映對象之間的關系并不是重要的。若用點表示研究的對象，用邊表示這些對象之間的聯(lián)系，則圖若用點表示研究的對象，用邊表示這些對象之間的聯(lián)系，則圖G可以定義為點和邊的集合，記作：可以定義為點和邊的集合，記作：,EVG 其中其中: : V點集點集 E邊集邊集 圖圖G區(qū)別于幾何學中的圖。這里只關心圖中有多少個點以及哪區(qū)別于幾何學

3、中的圖。這里只關心圖中有多少個點以及哪些點之間有連線。些點之間有連線。(v1)趙(v2)錢孫(v3) 李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的?？梢妶D論中的圖與幾何圖、工程圖是不一樣的。例如：在一個人群中，對相互認識這個關系我們可以用圖來例如：在一個人群中，對相互認識這個關系我們可以用圖來表示。表示。6a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙趙(v2)錢錢(v3)孫孫(v4)李李(v5)周周(v6)吳吳(

4、v7)陳陳圖圖11-3 如果我們把上面例子中的如果我們把上面例子中的“相互認識相互認識”關系改為關系改為“認識認識” ” 的關系，那么只用兩點之間的聯(lián)線就很難刻畫他們之間的關的關系，那么只用兩點之間的聯(lián)線就很難刻畫他們之間的關系了，這是我們引入系了，這是我們引入一個帶箭頭的聯(lián)線，稱為弧一個帶箭頭的聯(lián)線，稱為弧。圖。圖11-311-3就就是一個反映這七人是一個反映這七人“認識認識”關系的圖。相互認識用兩條反向關系的圖。相互認識用兩條反向的弧表示。的弧表示。 定義定義: : 圖中的點用圖中的點用v v表示，邊用表示，邊用e e表示。對每條邊可用它所表示。對每條邊可用它所連接的點表示，記作：連接的點

5、表示，記作：e e1 1=v=v1 1,v,v1 1; e; e2 2=v=v1 1,v,v2 2; ; v3e7e4e8e5e6e1e2e3v1v2v4v5若有邊若有邊e可表示為可表示為e=vi,vj，稱，稱vi和和vj是邊是邊e的的端點端點，反之稱邊，反之稱邊e為點為點vi或或vj的的關聯(lián)邊關聯(lián)邊。若點。若點vi、vj與同一條邊關與同一條邊關聯(lián)，稱點聯(lián)，稱點vi和和vj相鄰；若邊相鄰；若邊ei和和ej具具有公共的端點，稱邊有公共的端點，稱邊ei和和ej相鄰相鄰。 如果邊如果邊e的兩個端點相重，稱該邊為的兩個端點相重，稱該邊為環(huán)環(huán)。如右圖中邊。如右圖中邊e1為環(huán)。如果兩個點為環(huán)。如果兩個點之

6、間多于一條，稱為之間多于一條，稱為多重邊多重邊，如右圖，如右圖中的中的e4和和e5，對無環(huán)、無多重邊的圖，對無環(huán)、無多重邊的圖稱作稱作簡單圖簡單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5 圖中某些點和邊的交替序列，若其圖中某些點和邊的交替序列，若其中各邊互不相同，且對任意中各邊互不相同，且對任意Vi-1,Vi 和和vi+1均相鄰稱為均相鄰稱為鏈鏈。用。用表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5,110kkvevev 起點與終點重合的鏈稱作起點與終點重合的鏈稱作圈圈。如。如果每一對頂點之間至少存在一條果每一對頂點之間至少存在一條鏈，稱這樣的圖為鏈，稱這樣的圖

7、為連通圖連通圖，否則，否則稱稱圖不連通圖不連通。 ）(P232)(P232)設圖設圖G（V，E），對），對G的每一條邊的每一條邊(vi,vj)相應賦予數(shù)量指標相應賦予數(shù)量指標wij，wij稱為邊稱為邊(vi,vj)的權的權,賦予權的圖賦予權的圖G稱為稱為網(wǎng)絡網(wǎng)絡(或賦權圖）?；蛸x權圖）。權權可以代表距離、費用、通過能力可以代表距離、費用、通過能力(容量容量)等等。等等。端點無序的賦權圖稱為端點無序的賦權圖稱為無向網(wǎng)絡無向網(wǎng)絡，端點有序的賦權圖稱為，端點有序的賦權圖稱為有有向網(wǎng)絡。向網(wǎng)絡。910201571419256無向圖無向圖：由點和邊構成的圖，記作：由點和邊構成的圖，記作G=（V，E）。）

8、。有向圖有向圖：由點和弧構成的圖，記作：由點和弧構成的圖，記作D=（V，A）。）。連通圖連通圖：對無向圖：對無向圖G，若，若兩個不同的點之間，至少存在一條鏈，則兩個不同的點之間，至少存在一條鏈，則G為連通圖。為連通圖?；芈坊芈罚喝袈返牡谝粋€點和最后一個點相同，則該路為回路。：若路的第一個點和最后一個點相同，則該路為回路。賦權圖賦權圖：對一個無向圖：對一個無向圖G的每一條邊的每一條邊(vi,vj)，相應地有一個數(shù)，相應地有一個數(shù)wij，則稱，則稱圖圖G為賦權圖，為賦權圖，wij稱為邊稱為邊(vi,vj)上的權。上的權。網(wǎng)絡網(wǎng)絡：在：在中指定一點，稱為發(fā)點，指定另一點稱為收點，中指定一點，稱為發(fā)點

9、，指定另一點稱為收點，其它點稱為中間點，并把其它點稱為中間點，并把D中的每一條弧的賦權數(shù)稱為弧的容量，中的每一條弧的賦權數(shù)稱為弧的容量，D就就稱為網(wǎng)絡。稱為網(wǎng)絡。11 如何用最短的線路將三部電話連起來？如何用最短的線路將三部電話連起來？ 此問題可抽象為設此問題可抽象為設ABC為等邊三角形，連接三頂點為等邊三角形，連接三頂點的路線（稱為網(wǎng)絡）。這種網(wǎng)絡有許多個，其中最短路的路線（稱為網(wǎng)絡）。這種網(wǎng)絡有許多個，其中最短路線者顯然是二邊之和（如線者顯然是二邊之和（如ABAC）。）。ABCABCP 但若增加一個周轉(zhuǎn)站（新點但若增加一個周轉(zhuǎn)站（新點P），連接），連接4點的新網(wǎng)絡的最短點的新網(wǎng)絡的最短路線

10、為路線為PAPBPC。最短新路徑之長。最短新路徑之長N比原來只連三點比原來只連三點的最短路徑的最短路徑O要短。這樣得到的網(wǎng)絡不僅比原來節(jié)省材料，要短。這樣得到的網(wǎng)絡不僅比原來節(jié)省材料，而且穩(wěn)定性也更好。而且穩(wěn)定性也更好。 要求：要求：就是從給定的網(wǎng)絡圖中找出一點到各點或任意兩就是從給定的網(wǎng)絡圖中找出一點到各點或任意兩點之間距離最短的一條路點之間距離最短的一條路 .有些問題，如選址、管道鋪設時的選線、設備更新、投有些問題，如選址、管道鋪設時的選線、設備更新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結為求資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結為求最短路的問題。因此這類問題在生產(chǎn)實際中得到

11、廣泛應最短路的問題。因此這類問題在生產(chǎn)實際中得到廣泛應用。用。一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過河一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過河到北岸，河上只有一條獨木舟，每次除了人以外，只能到北岸，河上只有一條獨木舟，每次除了人以外，只能帶一樣東西；另外，如果人不在，狼就要吃羊，羊就要帶一樣東西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，問應該怎樣安排渡河，才能做到既把所有東西吃白菜，問應該怎樣安排渡河，才能做到既把所有東西都運過河去，并且在河上來回次數(shù)最少？這個問題就可都運過河去，并且在河上來回次數(shù)最少？這個問題就可以用求最短路方法解決。以用求最短路方法解決。 1）人）人M

12、（Man），狼），狼W（Wolf），）， 羊羊G（Goat），）， 草草H（Hay） 2） 點點 Vi 表示河岸的狀態(tài)表示河岸的狀態(tài) 3） 邊邊 ek 表示由狀態(tài)表示由狀態(tài) vi 經(jīng)一次渡河到狀態(tài)經(jīng)一次渡河到狀態(tài) vj 4） 權權邊邊 ek 上的權定為上的權定為 1我們可以得到下面的加權有向圖我們可以得到下面的加權有向圖： 狀態(tài)說明：狀態(tài)說明： v1,u1 =( M,W,G,H ); v2,u2 =(M,W,G); v3,u3 =(M,W,H); v4,u4=(M,G,H); v5,u5 =(M,G)此游戲轉(zhuǎn)化為在下面的二部圖中求從此游戲轉(zhuǎn)化為在下面的二部圖中求從 v v1 1 到到 u u1

13、 1 的最短路問題。的最短路問題。v1v2v3v4v5u5u4u3u2u1 求最短路有兩種算法求最短路有兩種算法: : 狄克斯屈拉狄克斯屈拉(Dijkstra)（雙標號）算法（雙標號）算法 逐次逼近算法逐次逼近算法最短路問題：最短路問題：對一個賦權的有向圖對一個賦權的有向圖D中的指定的兩個點中的指定的兩個點Vs和和Vt找找到一條從到一條從 Vs 到到 Vt 的路，使得這條路上所有弧的權數(shù)的總和最小，的路，使得這條路上所有弧的權數(shù)的總和最小，這條路被稱之為從這條路被稱之為從Vs到到Vt的最短路。這條路上所有弧的權數(shù)的總的最短路。這條路上所有弧的權數(shù)的總和被稱為從和被稱為從Vs到到Vt的距離。的距

14、離。若序列若序列 vs,v1.vn-1,vn 是從是從vs到到vt間的最短路，則序列間的最短路，則序列 vs,v1.vn-1 必為從必為從vs 到到vn-1的最短路。的最短路。假定假定v1v2 v3 v4是是v1 v4的最短路，則的最短路，則v1 v2 v3一定是一定是v1 v3的最短路，的最短路，v2 v3 v4也一定是也一定是v2 v4的的最短路。最短路。v1v2v3v4v51.給出點給出點V1以標號以標號(0,s)2.找出已標號的點的集合找出已標號的點的集合I，沒標號的點的集合，沒標號的點的集合J以及弧的集合以及弧的集合3. 如果上述弧的集合是空集，則計算結束。如果如果上述弧的集合是空集

15、，則計算結束。如果vt已標號（已標號（lt,kt），），則則 vs到到vt的距離為的距離為lt，而從，而從 vs到到vt的最短路徑，則可以從的最短路徑，則可以從kt 反向反向追蹤到起點追蹤到起點vs 而得到。如果而得到。如果vt 未標號，則可以斷言不存在從未標號，則可以斷言不存在從 vs到到vt的有向路。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。的有向路。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。4. 對上述弧的集合中的每一條弧，計算對上述弧的集合中的每一條弧，計算 sij=li+cij 。在所有的。在所有的 sij中，中，找到其值為最小的弧。不妨設此弧為（找到其值為最小的弧。不妨設此弧為（Vc,

16、Vd），則給此弧的終），則給此弧的終點以雙標號（點以雙標號（scd,c）,返回步驟返回步驟2。( ,)|,ijijv vvI vJ(P233)例例1 求下圖中求下圖中v1到到v6的最短路的最短路解：采用解：采用Dijkstra算法，可解得最短路徑為算法，可解得最短路徑為v1 v3 v4 v6 各點的標號圖如下：各點的標號圖如下：v23527531512v1v6v5v3v4(3,1)v23527531512 V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4( P234) 例例2 電信公司準備在甲、乙兩地沿路架設一條光纜線，問如何架設使電信公司準備在甲、乙兩地沿路架設一條光纜線，問如何

17、架設使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權數(shù)表示兩地間公路其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權數(shù)表示兩地間公路的長度（單位：公里）。的長度（單位：公里）。 解：這是一個求無向圖的最短路的問題。可以把無向圖的每一邊解：這是一個求無向圖的最短路的問題?？梢园褵o向圖的每一邊（vi,vj）都用方向相反的兩條弧（）都用方向相反的兩條?。╲i,vj）和（）和（vj,vi）代替，就化為有向圖，）代替，就化為有向圖，即可用即可用Dijkstra算法來求解。也可直接在無向圖中用算法來求解。也可直接在無向圖中用Dijkstra算法來求解。算法來求解。只要在算法中把從已標號的點到未標號的點的

18、弧的集合改成已標號的點到只要在算法中把從已標號的點到未標號的點的弧的集合改成已標號的點到未標號的點的邊的集合即可。未標號的點的邊的集合即可。 V1 （甲地）（甲地）151762444 31065v2V7 （乙地）（乙地）v3v4v5v6（0,s） V1 （甲地）（甲地）1517624431065(13,3) v2 (22,6)V7 （乙地）（乙地）V5(14,3)V6(16,5) V3(10,1) V4(18,5) 例例3 3 設備更新問題。某公司使用一臺設備，在每年年初，公司就要設備更新問題。某公司使用一臺設備，在每年年初，公司就要決定是購買新的設備還是繼續(xù)使用舊設備。如果購置新設備，就要支

19、付一決定是購買新的設備還是繼續(xù)使用舊設備。如果購置新設備，就要支付一定的購置費，當然新設備的維修費用就低。如果繼續(xù)使用舊設備，可以省定的購置費，當然新設備的維修費用就低。如果繼續(xù)使用舊設備，可以省去購置費，但維修費用就高了。請設計一個五年之內(nèi)的更新設備的計劃，去購置費，但維修費用就高了。請設計一個五年之內(nèi)的更新設備的計劃，使得五年內(nèi)購置費用和維修費用總的支付費用最小。使得五年內(nèi)購置費用和維修費用總的支付費用最小。 已知：設備每年年初的價格表已知：設備每年年初的價格表 設備維修費如下表設備維修費如下表年份年份12345年初價格年初價格1111121213使用年數(shù)使用年數(shù)0-11-22-33-44

20、-5每年維修每年維修費用費用5681118例例3的解：的解： 將問題轉(zhuǎn)化為最短路問題，如下圖：將問題轉(zhuǎn)化為最短路問題，如下圖： 用用vi表示表示“第第i年年初購進一臺新設備年年初購進一臺新設備”,弧（?。╲i,vj）表示第）表示第i年年初購進年年初購進的的設備一直使用到第設備一直使用到第j年年初。年年初。把所有弧的權數(shù)計算如下表：把所有弧的權數(shù)計算如下表：v1v2v3v4v5v6123456116223041592162230413172331417235186 (繼上頁繼上頁) 把權數(shù)賦到圖中，再用把權數(shù)賦到圖中，再用Dijkstra算法求最短路。算法求最短路。 最終得到下圖，可知，最終得到

21、下圖，可知，v1到到v6的距離是的距離是53，最短路徑有兩條：，最短路徑有兩條： v1 v3 v6和和 v1 v4 v6v1v2v3v4v5v6162230415916223041312317181723 V1（0,s）v3v4(41,1) v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4) 課堂練習：課堂練習：1. 用用Dijkstra算法求下圖從算法求下圖從v1到到v6的最短距離及路線。的最短距離及路線。v3v54v1v2v4v635222421v1到到v6的最短路為：的最短路為：6521vvvv 2. 求從求

22、從v1到到v8的最短路徑的最短路徑237184566134105275934682237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10 v1到到v8的最短路徑為的最短路徑為v1v4v7v5v8，最短距離為，最短距離為10 3. 求下圖中求下圖中v1點到另外任意一點的最短路徑點到另外任意一點的最短路徑v1v2v3v4v6v5322762133v1V2V3V4 V6V5322762133024714v1V2V3V4 V6V5322762133024714 Dijkstra算法只適用于全部權為非負情況，如果算法只適用于全部權為非負情況，如

23、果某邊上權為負的，算法失效。此時可采用逐次某邊上權為負的，算法失效。此時可采用逐次逼近算法。逼近算法。 例例6.7 如右圖所示中按如右圖所示中按dijkstra算法可得算法可得P(v1)=5為從為從vsv1的的最短路長顯然是錯誤的，從最短路長顯然是錯誤的，從vsv2v1路長只有路長只有3。v2vsv15-58 樹是圖論中結構最簡單但又十分重要的圖。在自然和社會樹是圖論中結構最簡單但又十分重要的圖。在自然和社會領域應用極為廣泛。領域應用極為廣泛。 例例6.2 乒乓求單打比賽抽簽后，可用圖來表示相遇情況，乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。如下圖所示。AB CDEF GH運動員

24、運動員 例例 某企業(yè)的組織機構圖也可用樹圖表示。某企業(yè)的組織機構圖也可用樹圖表示。廠長廠長人事科人事科財務科財務科總工總工程師程師生產(chǎn)副生產(chǎn)副廠長廠長經(jīng)營副經(jīng)營副廠長廠長開發(fā)科開發(fā)科技術科技術科生產(chǎn)科生產(chǎn)科設備科設備科供應科供應科銷售科銷售科檢驗科檢驗科動力科動力科任何樹中必存在次為任何樹中必存在次為1的點。的點。(一個點一個點Vi的相關聯(lián)邊的數(shù)目稱為點的相關聯(lián)邊的數(shù)目稱為點Vi的次的次)n 個頂點的樹必有個頂點的樹必有n-1 條邊。條邊。樹中任意兩個頂點之間，恰有且僅有一條鏈。樹中任意兩個頂點之間，恰有且僅有一條鏈。樹連通，但去掉任一條邊，必變?yōu)椴贿B通。樹連通，但去掉任一條邊，必變?yōu)椴贿B通。

25、樹無回圈，但不相鄰的兩個點之間加一條邊，恰樹無回圈，但不相鄰的兩個點之間加一條邊，恰得到一個圈。得到一個圈。v1v2v3v4v5v6 樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。37 圖圖11-11中，中，(a)就是一個樹，而就是一個樹，而(b)因為圖中有圈所以就不因為圖中有圈所以就不是樹，是樹， (c)因為不連通所以也不是樹。因為不連通所以也不是樹。圖圖11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c) 如果如果G2是是G1的部分圖，又是樹圖，則稱的部分圖

26、，又是樹圖，則稱G2是是G1的部分樹的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖G1含有多含有多個部分樹，其中樹枝總長最小的部分樹，稱為該圖的最小個部分樹，其中樹枝總長最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。部分樹（或最小支撐樹）。v1v2v3v4v5v1v2v3v4v5G1G2 44 給了一個無向圖給了一個無向圖G=(V,E)，我們保留，我們保留G的所有點，而刪掉部分的所有點，而刪掉部分G的邊或者的邊或者說保留一部分說保留一部分G的邊，所獲得的圖的邊，所獲得的圖G，稱之為，稱之為G的生成子圖。在圖的生成子圖。在圖11-12中，中，(

27、b)和和(c)都是都是(a)的生成子圖。的生成子圖。 如果圖如果圖G的一個生成子圖還是一個樹，則稱這個生成子圖為生成樹，在的一個生成子圖還是一個樹，則稱這個生成子圖為生成樹，在圖圖11-12中，中，(c)就是就是(a)的生成樹。的生成樹。 最小生成樹問題就是指在一個賦權的連通的無向圖最小生成樹問題就是指在一個賦權的連通的無向圖G中找出一個生成樹，中找出一個生成樹，并使得這個生成樹的所有邊的權數(shù)之和為最小。并使得這個生成樹的所有邊的權數(shù)之和為最小。圖圖11-12(a)(b)(c)部分樹v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5：任取一

28、圈，去掉圈中最長邊，直到無圈。任取一圈，去掉圈中最長邊，直到無圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521邊數(shù)邊數(shù)n-1=5v1v2v3v4v5v643521得到最小樹得到最小樹：Min C(T)=15去掉去掉G中所有邊，得到中所有邊，得到n個孤立點；然后加邊。個孤立點；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過程中不能加邊的原則為：從最短邊開始添加，加邊的過程中不能形成圈，直到點點連通形成圈，直到點點連通(即即:n-1條邊條邊)。5v1v2v3v4v5v6843752618v1v2v3v4v5v6435215v1v2v3v4v5v68437526

29、18Min C(T)=153749346321Min C(T)=12Min C(T)=15254173314475答案：34122323242Min C(T)=12213638534567454321Min C(T)=18 例例5、某大學準備對其所屬的、某大學準備對其所屬的7個學院辦公室計算機聯(lián)網(wǎng)，這個網(wǎng)絡的可個學院辦公室計算機聯(lián)網(wǎng)，這個網(wǎng)絡的可能聯(lián)通的途徑如下圖，圖中能聯(lián)通的途徑如下圖，圖中v1,v7 表示表示7個學院辦公室，請設計一個網(wǎng)個學院辦公室，請設計一個網(wǎng)絡能聯(lián)通絡能聯(lián)通7個學院辦公室，并使總的線路長度為最短。個學院辦公室，并使總的線路長度為最短。74 解：此問題實際上是求圖解：此問

30、題實際上是求圖11-1411-14的最小生成樹，這在例的最小生成樹，這在例4 4中已經(jīng)求得，中已經(jīng)求得，也即按照圖也即按照圖11-1311-13的的(f)(f)設計，可使此網(wǎng)絡的總的線路長度為最短，為設計，可使此網(wǎng)絡的總的線路長度為最短，為1919百米。百米。 “ “管理運籌學軟件管理運籌學軟件”有專門的子程序可以解決最小生成樹問題。有專門的子程序可以解決最小生成樹問題。v1331728541034v7v6v5v4v2v3圖圖11-14 如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個網(wǎng)絡最大流問題。這就是一個網(wǎng)絡最大流問題

31、。 基本概念：基本概念：隊網(wǎng)絡上的每條弧隊網(wǎng)絡上的每條弧(v(vii,v,vj j) )都給出一個最大的都給出一個最大的通過能力，稱為該弧的通過能力，稱為該弧的，簡記為，簡記為c cij ij。容量網(wǎng)絡中通常。容量網(wǎng)絡中通常規(guī)定一個規(guī)定一個( (也稱源點，記為也稱源點，記為s) s)和一個和一個( (也稱匯點，也稱匯點，記為記為t) t)，網(wǎng)絡中其他點稱為，網(wǎng)絡中其他點稱為。st48441226792. 2. 網(wǎng)絡的最大流網(wǎng)絡的最大流是指網(wǎng)絡中從發(fā)點到收點之間允許通過的最大流量。是指網(wǎng)絡中從發(fā)點到收點之間允許通過的最大流量。3. 3. 流與可行流流與可行流 流流是指加在網(wǎng)絡各條弧上的實際流量，

32、對加在弧是指加在網(wǎng)絡各條弧上的實際流量，對加在弧(vi,vj)上上的負載量記為的負載量記為fij。若。若fij=0，稱為零流。，稱為零流。滿足以下條件的一組流稱為滿足以下條件的一組流稱為可行流可行流。 容量限制條件。容量網(wǎng)絡上所有的弧滿足：容量限制條件。容量網(wǎng)絡上所有的弧滿足：0fijcij 中間點平衡條件。中間點平衡條件。),(0),(),(tsivvfvvfijji 若以若以v(f)表示網(wǎng)絡中從表示網(wǎng)絡中從st的流量，則有：的流量，則有： 0),(),()(tjjsvvfvvffv結論結論：任何網(wǎng)絡上一定存在可行流。（零流即是：任何網(wǎng)絡上一定存在可行流。（零流即是可行流）可行流）網(wǎng)絡最大流

33、問題：網(wǎng)絡最大流問題：指滿足容量限制條件和中間點平衡的條件下，使指滿足容量限制條件和中間點平衡的條件下，使v(f)v(f)值達到最大。值達到最大。一、最大流的數(shù)學模型一、最大流的數(shù)學模型 例例6 某石油公司擁有一個管道網(wǎng)絡，使用這個網(wǎng)絡可以把石油從采地某石油公司擁有一個管道網(wǎng)絡，使用這個網(wǎng)絡可以把石油從采地運送到一些銷售點，這個網(wǎng)絡的一部分如下圖所示。由于管道的直徑運送到一些銷售點，這個網(wǎng)絡的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（的變化，它的各段管道（vi,vj）的流量）的流量cij（容量）也是不一樣的。（容量）也是不一樣的。cij的的單位為萬加侖單位為萬加侖/小時。如果使用這

34、個網(wǎng)絡系統(tǒng)從采地小時。如果使用這個網(wǎng)絡系統(tǒng)從采地 v1向銷地向銷地 v7運送石運送石油，問每小時能運送多少加侖石油？油，問每小時能運送多少加侖石油？79v563522241263v1v2v7v4v3v6圖圖11-26 1412232514434647234335362535573646675767471214,1,2,6;1,2,70,1,2,6;1,2,712ijijijmaxF = fffffffffffffffffffffffffcijfij目標函數(shù)：約束條件：80 我們可以為此例題建立線性規(guī)劃數(shù)學模型：我們可以為此例題建立線性規(guī)劃數(shù)學模型： 設弧設弧(vi,vj)上流量為上流量為fij

35、，網(wǎng)絡上的總的流量為，網(wǎng)絡上的總的流量為F，則有：，則有： 81 在這個線性規(guī)劃模型中，其約束條件中的前在這個線性規(guī)劃模型中，其約束條件中的前6 6個方程表示個方程表示了網(wǎng)絡中的流量必須滿足守恒條件，了網(wǎng)絡中的流量必須滿足守恒條件，發(fā)點的流出量必須等于發(fā)點的流出量必須等于收點的總流入量收點的總流入量；其余的點稱之為；其余的點稱之為中間點中間點，它的總流入量必，它的總流入量必須等于總流出量。其后面幾個約束條件表示對每一條弧須等于總流出量。其后面幾個約束條件表示對每一條弧(v(vi i,v,vj j) )的流量的流量fij要滿足流量的可行條件，應小于等于弧要滿足流量的可行條件，應小于等于弧(v(v

36、i i,v,vj j) )的容的容量量c cijij，并大于等于零，即，并大于等于零，即0 0f fijij c cijij。我們把滿足守恒條件。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡流及流量可行條件的一組網(wǎng)絡流 ffijij 稱之為稱之為可行流可行流，（即線性，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點總流規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點總流出量最大）的稱之為出量最大）的稱之為最大流最大流（即線性規(guī)劃的最優(yōu)解）。（即線性規(guī)劃的最優(yōu)解）。 我們把例我們把例6 6的數(shù)據(jù)代入以上線性規(guī)劃模型，用的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運籌管理運籌學軟件學軟件”，馬上得

37、到以下的結果：，馬上得到以下的結果：f f1212=5=5，f f1414=5=5，f f2323=2=2，f f2525=3=3，f f4343=2=2，f f4646=1=1，f f4747=2=2，f f3535=2=2，f f3636=2=2，f f5757=5=5，f f6767=3=3。最優(yōu)值。最優(yōu)值（最大流量）（最大流量）=10=10。二、最大流問題網(wǎng)絡圖論的解法二、最大流問題網(wǎng)絡圖論的解法 對網(wǎng)絡上弧的容量的表示作改進。為省去弧的方向，如下圖對網(wǎng)絡上弧的容量的表示作改進。為省去弧的方向，如下圖: (a)和和(b)、(c)和和(d)的意義相同。的意義相同。 用以上方法對例用以上方

38、法對例6的圖的容量標號作改進，得下圖的圖的容量標號作改進，得下圖82vivjvivjcij0（a）（b） cijcijvivj（cji）（c）vivj cij cji（d）63522241263v1v2v5v7v4v3v600000000000 求最大流的基本算法求最大流的基本算法（1）找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量）找出一條從發(fā)點到收點的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。都大于零。如果不存在這樣的路，則已經(jīng)求得最大流。（2）找出這條路上各條弧的最小的順流的容量）找出這條路上各條弧的最小的順流的容量pf，通過這條

39、路增加網(wǎng)絡的流，通過這條路增加網(wǎng)絡的流量量pf。（3）在這條路上，減少每一條弧的順流容量）在這條路上，減少每一條弧的順流容量pf ，同時增加這些弧的逆流容，同時增加這些弧的逆流容量量pf，返回步驟（，返回步驟（1）。）。 用此方法對例用此方法對例6求解：求解： 第一次迭代：選擇路為第一次迭代：選擇路為v1 v4 v7 。?。ā；。?v4 , v7 ）的順流容量為）的順流容量為2，決定了決定了pf=2，改進的網(wǎng)絡流量圖如下圖：，改進的網(wǎng)絡流量圖如下圖：8363522241263v1v2v5v7v4v3v6000000000004202 第二次迭代：選擇路為第二次迭代：選擇路為v1 v2 v5 v

40、7 ?；。??；。?v2 , v5 ）的順流容量為）的順流容量為3，決定了，決定了pf=3，改進的網(wǎng)絡流量圖如下圖：，改進的網(wǎng)絡流量圖如下圖： 第三次迭代：選擇路為第三次迭代：選擇路為v1 v4 v6 v7 ?；。??；。?v4 , v6 ）的順流容量為）的順流容量為1，決定了，決定了pf=1，改進的網(wǎng)絡流量圖如下圖：，改進的網(wǎng)絡流量圖如下圖：84635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v600000042022033333013 第四次迭代：選擇路為第四次迭代：選擇路為v1 v4 v3 v6 v7 。?。??；。?v3

41、 , v6 ）的順流容）的順流容量為量為2，決定了，決定了pf=2，改進的網(wǎng)絡流量圖如下圖：，改進的網(wǎng)絡流量圖如下圖： 第五次迭代：選擇路為第五次迭代：選擇路為v1 v2 v3 v5 v7 。?。??；。?v2 , v3 ）的順流容）的順流容量為量為2，決定了，決定了pf=2，改進的網(wǎng)絡流量圖如下圖：，改進的網(wǎng)絡流量圖如下圖：8522243v1v2v5v7v4v3v6100001203203335031200231322v1v2v5v7v4v3v61012020333501202313150020205 經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點到收點的一條路，路上的經(jīng)過第五次迭代后在圖中已經(jīng)找不到

42、從發(fā)點到收點的一條路，路上的每一條弧順流容量都大于零，運算停止。得到最大流量為每一條弧順流容量都大于零，運算停止。得到最大流量為10。 最大流量圖如下圖：最大流量圖如下圖：8622v1v2v5v7v4v3v6123522355 “管理運籌學軟件管理運籌學軟件”中還有專門的子程序用于解決最大流問題。中還有專門的子程序用于解決最大流問題。 最小費用最大流問題：給了一個帶收發(fā)點的網(wǎng)絡，對每一條弧最小費用最大流問題：給了一個帶收發(fā)點的網(wǎng)絡，對每一條弧（vi,vj），除了給出容量），除了給出容量cij外，外，還給出了這條弧的單位流量的費用還給出了這條弧的單位流量的費用bij，要，要求一個最大流求一個最大

43、流F，并使得總運送費用最小。，并使得總運送費用最小。一、最小費用最大流的數(shù)學模型一、最小費用最大流的數(shù)學模型 例例7 由于輸油管道的長短不一，所以在例由于輸油管道的長短不一，所以在例6中每段管道（中每段管道（ vi,vj ）除）除了有不同的流量限制了有不同的流量限制cij外，還有不同的單位流量的費用外，還有不同的單位流量的費用bij ，cij的單位為萬的單位為萬加侖加侖/小時，小時， bij的單位為百元的單位為百元/萬加侖。如圖。從采地萬加侖。如圖。從采地 v1向銷地向銷地 v7運送石運送石油，怎樣運送才能運送最多的石油并使得總的運送費用最??？求出最大流油，怎樣運送才能運送最多的石油并使得總的

44、運送費用最小？求出最大流量和最小費用。量和最小費用。87(6,6)(3,4)(5,7)v1v2v5v7(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v4v3v6(6,3) (,)ijijijv vAfb88 這個最小費用最大流問題也是一個線性規(guī)劃的問題。這個最小費用最大流問題也是一個線性規(guī)劃的問題。 解：我們用線性規(guī)劃來求解此題，可以分兩步走。解：我們用線性規(guī)劃來求解此題，可以分兩步走。 第一步，先求出此網(wǎng)絡圖中的最大流量第一步，先求出此網(wǎng)絡圖中的最大流量F，這已在例，這已在例6中建中建立了線性規(guī)劃的模型，通過管理運籌學軟件已經(jīng)獲得結果。立了線性規(guī)劃的模型，通過管理運籌

45、學軟件已經(jīng)獲得結果。 第二步，在最大流量第二步，在最大流量F的所有解中，找出一個最小費用的的所有解中，找出一個最小費用的解，我們來建立第二步中的線性規(guī)劃模型如下：解，我們來建立第二步中的線性規(guī)劃模型如下： 仍然設?。ㄈ匀辉O?。╲i,vj）上的流量為）上的流量為fij，這時已知中最大流量為，這時已知中最大流量為F，只要在例只要在例6的約束條件上，再加上總流量必須等于的約束條件上，再加上總流量必須等于F的約束條件：的約束條件：f12=f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標函數(shù)即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標函數(shù)顯然是求其流量的最小費用顯然是求其流量的最小費用 fij .

46、bij 。 由此得到線性規(guī)劃模型如下：由此得到線性規(guī)劃模型如下： 1214252343(,)355736464767121412232514434647234335362535573646675767471214min63452473384. .10,(1,2,6;ijijijv vAijijfbfffffffffffstffFfffffffffffffffffffffffcij2,3,7),0,(1,2,6;2,3,7),ijfij89 90 用管理運籌學軟件，可求得如下結果：用管理運籌學軟件，可求得如下結果：f f1212=4,f=4,f1414=6,=6,f f2525=3,f=3,f2

47、323=1,f=1,f4343=3,F=3,F5757=5,f=5,f3636=2,f=2,f4646=1,f=1,f4747=2,f=2,f6767=3,f=3,f3535=2=2。其最。其最優(yōu)值優(yōu)值( (最小費用最小費用)=145)=145。對照前面例。對照前面例6 6的結果，可對最小費用最的結果，可對最小費用最大流的概念有一個深刻的理解。大流的概念有一個深刻的理解。 如果我們把例如果我們把例7 7的問題改為：每小時運送的問題改為：每小時運送6 6萬加侖的石油萬加侖的石油從采地從采地v v1 1到銷地到銷地v v7 7最小費用是多少？應怎樣運送？這就變成了最小費用是多少？應怎樣運送？這就變

48、成了一個最小費用流的問題。一般來說，所謂最小費用流的問題一個最小費用流的問題。一般來說，所謂最小費用流的問題就是：就是：在給定了收點和發(fā)點并對每條弧在給定了收點和發(fā)點并對每條弧(v(vi i,v,vj j) )賦權以容量賦權以容量c cijij及單位費用及單位費用b bijij的網(wǎng)絡中，求一個給定值的網(wǎng)絡中，求一個給定值f f的流量的最小費用，的流量的最小費用，這個給定值這個給定值f f的流量應的流量應小于等于最大流量小于等于最大流量F F，否則無解。，否則無解。求最求最小費用流的問題的線性規(guī)劃的模型只要把最小費用最大流模小費用流的問題的線性規(guī)劃的模型只要把最小費用最大流模型中的約束條件中的發(fā)

49、點流量型中的約束條件中的發(fā)點流量F F改為改為f f即可。在例即可。在例6 6中只要把中只要把f f1212+f+f1414=F=F改為改為f f1212+f+f1414=f=6=f=6得到了最小費用流的線性規(guī)劃的模型得到了最小費用流的線性規(guī)劃的模型了。了。二、最小費用最大流的網(wǎng)絡圖論解法二、最小費用最大流的網(wǎng)絡圖論解法對網(wǎng)絡上?。▽W(wǎng)絡上弧（vi,vj）的（）的（cij,bij）的表示作如下改動，用）的表示作如下改動，用(b)來表示來表示(a)。用上述方法對例用上述方法對例7中的圖形進行改進，得圖如下頁：中的圖形進行改進，得圖如下頁：91vivjvivj（cij,bij ）（0,-bij ）

50、（a）（b）（cij,bij ）（cij,bij ）vivj（cji,bji ）（cij,bij ）vivj（cji,bji ）（0,-bji)（0,-bji)（c）（d） 求最小費用最大流的基本算法求最小費用最大流的基本算法 在對弧的標號作了改進的網(wǎng)絡圖上求最小費用最大流的基本算法與求在對弧的標號作了改進的網(wǎng)絡圖上求最小費用最大流的基本算法與求最大流的基本算法完全一樣，不同的只是在步驟（最大流的基本算法完全一樣，不同的只是在步驟（1）中要選擇一條總的）中要選擇一條總的單位費用最小的路，而不是包含邊數(shù)最小的路。單位費用最小的路，而不是包含邊數(shù)最小的路。92(6,6)(3,4)(5,7)(2,5

51、)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）圖圖11-2811-28用上述方法對例用上述方法對例7求解：求解： 第一次迭代：找到最短路第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后總流量為第一次迭代后總流量為1，總，總費用費用10。93v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖圖11-291