圖論方法[共85頁(yè)]

《圖論方法[共85頁(yè)]》由會(huì)員分享，可在線閱讀，更多相關(guān)《圖論方法[共85頁(yè)]（85頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 引言 圖論是專(zhuān)門(mén)研究圖的理論的一門(mén)數(shù)學(xué)分支，屬于離散數(shù)學(xué)范疇，與運(yùn)籌學(xué)有交叉，它有200多年歷史，大體可劃分為三個(gè)階段：第一階段是從十八世紀(jì)中葉到十九世紀(jì)中葉，處于萌芽階段，多數(shù)問(wèn)題圍游戲而產(chǎn)生，最有代表性的工作是所謂的Euler七橋問(wèn)題，即一筆畫(huà)問(wèn)題。第二階段.第三階段BACDl 哥尼斯堡七橋問(wèn)題哥尼斯堡七橋問(wèn)題(Knigsberg Bridge Problem)l Leonhard Euler(1707-1783)在在1736年發(fā)表第一篇圖論方面年發(fā)表第一篇圖論方面的論文，奠基了圖論中的一些基本定理的論文，奠基了圖論中的一些基本定理.l 很多問(wèn)題都可以用點(diǎn)和線來(lái)表示，一般點(diǎn)表示實(shí)體，線表

2、示很多問(wèn)題都可以用點(diǎn)和線來(lái)表示，一般點(diǎn)表示實(shí)體，線表示實(shí)體間的關(guān)聯(lián)實(shí)體間的關(guān)聯(lián)ABCD例例6.16.1：哥尼斯堡七橋問(wèn)題：哥尼斯堡七橋問(wèn)題1 1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念l 一般研究無(wú)向圖l 樹(shù)圖：倒置的樹(shù)，根(root)在上，樹(shù)葉(leaf)在下l 多級(jí)輻射制的電信網(wǎng)絡(luò)、管理的指標(biāo)體系、家譜、分類(lèi)學(xué)、組織結(jié)構(gòu)等都是典型的樹(shù)圖C1C2C3C4根根葉葉 2 最小支撐樹(shù)最小支撐樹(shù)(生成樹(shù)生成樹(shù))一一 樹(shù)的定義及其性質(zhì)樹(shù)的定義及其性質(zhì)l 無(wú)圈連通圖稱(chēng)為樹(shù)無(wú)圈連通圖稱(chēng)為樹(shù)(treetree)，記為，記為T(mén) T 樹(shù)的性質(zhì)：樹(shù)的性質(zhì)：l 任何樹(shù)必存在次數(shù)為任何樹(shù)必存在次數(shù)為 1 1 的點(diǎn)的點(diǎn)l

3、 具有具有 n n 個(gè)節(jié)點(diǎn)的樹(shù)個(gè)節(jié)點(diǎn)的樹(shù) T T 的邊恰好為的邊恰好為 n n 1 1 條，反之，任何有條，反之，任何有n n 個(gè)節(jié)點(diǎn)，個(gè)節(jié)點(diǎn)，n n 1 1 條邊的連通圖必是一棵樹(shù)條邊的連通圖必是一棵樹(shù)ACDBACDBACDBADCB圖的生成樹(shù)圖的生成樹(shù):若圖若圖G G的一個(gè)支撐圖的一個(gè)支撐圖T T是一棵樹(shù)是一棵樹(shù),則稱(chēng)則稱(chēng)T T是是G G的一棵的一棵生成樹(shù)生成樹(shù)(spanning treespanning tree).).在賦權(quán)圖在賦權(quán)圖G G中，一棵生成樹(shù)所有邊上權(quán)的和，稱(chēng)為生成樹(shù)的權(quán)。中，一棵生成樹(shù)所有邊上權(quán)的和，稱(chēng)為生成樹(shù)的權(quán)。具有最小權(quán)的生成樹(shù)，稱(chēng)為具有最小權(quán)的生成樹(shù)，稱(chēng)為最小樹(shù)最

4、小樹(shù)（或最優(yōu)樹(shù)）（或最優(yōu)樹(shù)）,求最小樹(shù)有求最小樹(shù)有破圈破圈法法和和避圈法避圈法.定理 圖 G有生成樹(shù)的充分必要條件為圖是連通圖。定義（最優(yōu)樹(shù)）在賦權(quán)圖G中，一棵生成樹(shù)所有樹(shù)柱上權(quán)的和，稱(chēng)為生成樹(shù)的權(quán)。具有最小權(quán)的生成樹(shù)，稱(chēng)為最優(yōu)樹(shù)（或最小樹(shù)）。求最小樹(shù)的方法有破圈法和避圈法。3 最小枝杈樹(shù)問(wèn)題4：最短路問(wèn)題最短路問(wèn)題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問(wèn)題之一。許多優(yōu)化問(wèn)題都可以使用這個(gè)模型，如設(shè)備更新、管道的鋪設(shè)、線路的安排、廠區(qū)的布局等。最短路問(wèn)題的一般提法是：設(shè) 為連通圖，圖中各邊 有權(quán) (表示 ，之間沒(méi)有邊）,為圖中任意兩點(diǎn)，求一條道路 ，使它是從 到 的所有路中總權(quán)最小的路。即：),(EVG),

5、(jivvijlijliv,svjvtvsvtv),()(jivvijlL最小。最短路算法中1959年由 （狄克斯特洛）提出的算法被公認(rèn)為是目前最好的方法，我們稱(chēng)之為 算法。下面通過(guò)例子來(lái)說(shuō)明此法的基本思想。DijkstraDijkstra條件：所有的權(quán)數(shù) 0ijl思路：逐步探尋。1v2v3v5v7v8v6v4v46761519554471v2v3v5v7v8v6v4v4676151955447下求 到 的最短路：1v8v1）從 出發(fā)，向 走。首先，從 到 的距離為0，給 標(biāo)號(hào)（0）。畫(huà)第一個(gè)弧。（表明已 標(biāo)號(hào)，或已走出 ）1v8v1v1v1v1v1v)0(從 出發(fā)，只有兩條路可走 ，其距離為

6、1v),(21vv),(31vv2）,412l.613l1v2v3v5v7v8v6v4v4676151955447)0(可能最短路為46,4min,min,min13121312llkk),(21vv2v)4(給 劃成粗線。劃第二個(gè)弧。給 標(biāo)號(hào)（4）。1v2v3v5v7v8v6v4v4676151955447)0()4(表明走出 后走向 的最短路目前看是 ，最優(yōu)距離是4。1v8v),(21vv現(xiàn)已考察完畢第二個(gè)圈內(nèi)的路，或者說(shuō)，已完成 的標(biāo)號(hào)。,1v2v1v2v3v5v7v8v6v4v4676151955447)0()4(3）接著往下考察，有三條路可走：),(42vv),(31vv).,(52

7、vv可選擇的最短路為644,54,6min,min,min2512241213252413dldllkkk),(31vv3v)6(給 劃成粗線。劃第3個(gè)弧。給 標(biāo)號(hào)（6）。1v2v3v5v7v8v6v4676151955447)0()4()6(4）接著往下考察，有四條路可走：),(42vv).,(52vv可選擇的最短路為813,10,8,9min,min35342524kkkk5v4v),(43vv).,(53vv),(52vv)8(給 劃成粗線。劃第4個(gè)弧。給 標(biāo)號(hào)（8）。1v2v3v5v7v8v6v4676151955447)0()4()6(5）接著往下考察，有四條路可走：),(42vv可

8、選擇的最短路為914,13,10,9min,min57563424kkkk4v),(43vv),(65vv),(42vv)8().,(75vv4v)9(給 劃成粗線。劃第5個(gè)弧。給 標(biāo)號(hào)（9）。1v2v3v5v7v8v6v4676151955447)0()4()6(6）接著往下考察，有四條路可走：),(64vv可選擇的最短路為1314,13,16,18min,min57564746kkkk6v),(74vv),(65vv),(65vv)8().,(75vv4v)9()13(給 劃成粗線。劃第6個(gè)弧。給 標(biāo)號(hào)（13）。1v2v3v5v7v8v6v4676151955447)0()4()6(7）接

9、著往下考察，有四條路可走：可選擇的最短路為1414,18,14,16min,min68675747kkkk8v),(76vv),(75vv)8(),(75vv4v)9()13().,(86vv)14(),(74vv),(86vv,7v)14(同時(shí)給 劃成粗線。分別給 標(biāo)號(hào)（14）。最后，從 逆尋粗線到 ，得最短路：1v2v3v5v7v8v6v4676151955447)0()4()6()8(4v)9()13()14()14(8v1v86521vvvvv長(zhǎng)度為15。4v1v2v3v4v6v5v722561413412圖圖5-1 例例5-3網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖 0214201310464140143102

10、5642025207654321VVVVVVVD 1v 2v 3v 4v 5v 6v 7v 步驟步驟 考察點(diǎn)考察點(diǎn) T標(biāo)號(hào)點(diǎn)集標(biāo)號(hào)點(diǎn)集 標(biāo)標(biāo) 號(hào)（號(hào)（表表P標(biāo)號(hào)）標(biāo)號(hào)）1v1v2，v7v1 v2 v3 v4 v5 v6 v7 0 -0+20+5 2 5 -23456v2v3v4v5v6v3，v7v4，v7v5，v6，v7v5，v72+22+42+6 4 6 8 -4+14+3 5 8 7 -5+45+1 5+4 8 6 96+2 8 8v78+18反向追蹤，得到最優(yōu)路線：反向追蹤，得到最優(yōu)路線：v1 v2 v3 v4 v6 v7v5若先把若先把v7的標(biāo)號(hào)改為永久性標(biāo)號(hào)，的標(biāo)號(hào)改為永久性標(biāo)號(hào)，該

11、怎麼繼續(xù)作下去？該怎麼繼續(xù)作下去？56v6v7v5，v7v5v1 v2 v3 v4 v5 v6 v7 6+2 8 8 8+18 8 6 9 1v 第二講：最短路問(wèn)題的兩個(gè)應(yīng)用最短路問(wèn)題在圖論應(yīng)用中處于很重要的地位，下面舉兩個(gè)實(shí) 際應(yīng)用的例子。例 設(shè)備更新問(wèn)題某工廠使用一臺(tái)設(shè)備，每年年初工廠要作出決定：繼續(xù)使 用，購(gòu)買(mǎi)新的？如果繼續(xù)使用舊的，要負(fù)維修費(fèi)；若要購(gòu)買(mǎi) 一套新的，要負(fù)購(gòu)買(mǎi)費(fèi)。試確定一個(gè)5年計(jì)劃，使總支出最小若已知設(shè)備在各年的購(gòu)買(mǎi)費(fèi)，及不同機(jī)器役齡時(shí)的殘值與維修費(fèi)，如表所示.項(xiàng)目第1年第2年第3年第4年第5年購(gòu)買(mǎi)費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)56811

12、18殘值43210表8-21v2v3v4v5v6v131219284059151520294122213014解：把這個(gè)問(wèn)題化為最短路問(wèn)題。用點(diǎn) 表示第i年初購(gòu)進(jìn)一臺(tái)新設(shè)備，虛設(shè)一個(gè)點(diǎn) ，表示第5年底。6viv邊 表示第i年購(gòu)進(jìn)的設(shè)備一直使用到第j年初（即第j-1年底）。),(jivv1v2v3v4v5v6v131219284059151520294122213014邊 上的數(shù)字表示第i年初購(gòu)進(jìn)設(shè)備，一直使用到第j年初所需支付的購(gòu)買(mǎi)費(fèi)、維修的全部費(fèi)用（可由表8-2計(jì)算得到）。),(jivv1v2v3v4v5v6v131219284059151520294122213014這樣設(shè)備更新問(wèn)題就變?yōu)?/p>

13、：求從 到 的最短路問(wèn)題.1v6v)12(2v3v4v5v6v131219284059151520294122213014 1v)0(1259,40,28,19,12min,min1615141312kkkkk1v)0(),(21vv 給 劃成彩線。194112,2912,2012,1312,59,40,28,19min,min2625242316151413kkkkkkkk)12(2v)19(3v)28(4v5v6v1312192840591515202941222130141v)0(),(31vv 給 劃成彩線。2849,40,33,53,41,32,59,40,28min,min3635

14、34262524161514kkkkkkkkk),(41vv 給 劃成彩線。4050,43,49,35,43,41,59,40min,min4645363526251615kkkkkkkk)12(2v)19(3v)28(4v)40(5v6v1312192840591515202941222130141v)0(),(51vv 給 劃成彩線。)12(2v)19(3v)28(4v)40(5v6v1312192840591515202941222130141v)0(4955,50,49,53,59min,min5646362616kkkkk),(63vv 給 劃成彩線。計(jì)算結(jié)果：最短路631vvv)1

15、2(2v)19(3v)28(4v)40(5v6v13192840591515202941222130141v)0(12最短路路長(zhǎng)為49。即：在第一年、第三年初各購(gòu)買(mǎi)一臺(tái)新設(shè)備為最優(yōu)決策。這時(shí)5年的總費(fèi)用為49。例13(選址問(wèn)題)已知某地區(qū)的交通網(wǎng)絡(luò)如圖所示，其中點(diǎn)代表居民小區(qū)，邊代表公路，為小區(qū)間公路距離，問(wèn)區(qū)中心醫(yī)院應(yīng)建在哪個(gè)小區(qū)，可使離醫(yī)院最遠(yuǎn)的小區(qū)居民就診時(shí)所走的路程最近？1v6v3v2v4v5v7v301520301520256018解 求中心的問(wèn)題。解決方法：先求出 到其它各點(diǎn)的最短路長(zhǎng)如ivjd,max)(7211dddvD再求)(,),(),(min721vDvDvD即為所求。1

16、v)18(6v2v7v30152030152025185v60)0(4v比如求)(4vD 4v)0(1818,30,20min,min464543kkk),(64vv 給 劃成彩線。3v1v)18(6v2v7v30152030152025185v60)0(4v)20(3v2033,33,43,30,20min,min6762634543kkkkk),(34vv 給 劃成彩線。給 標(biāo)號(hào)20。3v1v)18(6v)33(2v7v3015203015202518)30(5v60)0(4v)20(3v3033,33,40,80,30min,min6762323545kkkkk),(54vv給 劃成彩線

17、。給 標(biāo)號(hào)30。5v1v)18(6v)33(2v3015203015202518)30(5v60)0(4v)20(3v3333,33,40min,min676232kkk),(26vv分別給 劃成彩線。分別給 標(biāo)號(hào)33。72,vv)33(7v),(76vv)60(1v)18(6v1v3015203015202518)30(5v60)0(4v)20(3v6363minmin21k給 劃成彩線。給 標(biāo)號(hào)63。),(12vv)33(7v)33(2v其它計(jì)算結(jié)果見(jiàn)下表：小區(qū)號(hào)0 30 50 63 93 45 609330 0 20 33 63 15 306350 20 0 20 50 25 40506

18、3 33 20 0 30 18 336393 63 50 30 0 48 639345 15 25 18 48 0 154860 30 40 33 63 15 063表 8.11v1v3v3v2v2v4v4v5v5v6v6v7v7v)(ivD由于 最小，所以醫(yī)院應(yīng)建在 ，此時(shí)離醫(yī)院最遠(yuǎn)的小區(qū) 距離為48。48)(6vD6v5v 一 概念l 網(wǎng)路流一般在有向圖上討論,弧的方向?yàn)榱鞯姆较騦 定義網(wǎng)路上支路的容量為其最大通過(guò)能力，記為 rij，支路上的實(shí)際流量記為 xij,網(wǎng)絡(luò)流為所有通過(guò)弧的流量的集合.l 圖中規(guī)定一個(gè)發(fā)點(diǎn)s，一個(gè)收點(diǎn)tl 節(jié)點(diǎn)沒(méi)有容量限制，流在節(jié)點(diǎn)不會(huì)存儲(chǔ)4 4 最大流問(wèn)題最大流

19、問(wèn)題可行流可行流滿(mǎn)足以下條件的流稱(chēng)為可行流：滿(mǎn)足以下條件的流稱(chēng)為可行流：1 1、每一個(gè)節(jié)點(diǎn)流量平衡、每一個(gè)節(jié)點(diǎn)流量平衡(流進(jìn)流進(jìn)=流出流出)2 2、00 x xijij u uijij(容量限制容量限制)總流量最大的可行流為總流量最大的可行流為最大流最大流tiftsisifxxjjijij,0鏈的前向弧鏈的前向弧,后向弧后向弧l 是網(wǎng)絡(luò)是網(wǎng)絡(luò)G G中一條從始點(diǎn)中一條從始點(diǎn)VsVs到終點(diǎn)到終點(diǎn)VtVt的鏈的鏈,在鏈中與鏈的方在鏈中與鏈的方向一致的弧稱(chēng)為鏈的向一致的弧稱(chēng)為鏈的前向弧前向弧,在鏈中與鏈的方向相反的弧稱(chēng)在鏈中與鏈的方向相反的弧稱(chēng)為鏈的為鏈的前向弧前向弧.746321vvvvvv前向弧集

20、合與后向弧集合為：前向弧集合與后向弧集合為：=(=(v v1 1,v v2 2),(),(v v3 3,v v6 6),),(v v4 4,v v7 7)=(=(v v3 3,v v2 2),(),(v v4 4,v v6 6)21xij=5rij=521xij=3rij=5飽和飽和、不飽和、不飽和、流量的間隙、流量的間隙（1，2）是飽和的）是飽和的2 2、如果、如果x xijijuuijij，邊從，邊從i i到到j(luò) j的方向是不飽和的；的方向是不飽和的；（1，2）是不飽和的）是不飽和的間隙為間隙為 12=r12-x12=5-3=21 1、如果、如果x xijij=u=uijij，邊從，邊從i

21、 i到到j(luò) j的方向是飽和的；的方向是飽和的；截集與截集容量截集與截集容量定義：把網(wǎng)絡(luò)的點(diǎn)集分割為兩個(gè)非空集合S和S,且S包含 Vs 點(diǎn)，另一個(gè)包含 Vt 點(diǎn),則把始點(diǎn)在S中,終點(diǎn)在S中的弧的集合稱(chēng)為分離Vs和Vt的一個(gè)截集.l 截量是指截集中所有弧的容量之和sjsiijrssr),(福特福特-富克森定理：富克森定理：網(wǎng)路的最大流等于最小截集容量網(wǎng)路的最大流等于最小截集容量st5342(4,0)(3,0)(2,0)(1,0)(1,0)(5,0)(3,0)(2,0)(5,0)增廣鏈增廣鏈(augmenting path)st5342(4,0)(3,0)(2,0)(1,0)(1,0)(5,0)(3

22、,0)(2,0)(5,0)7645231vvvvvvv 三三 確定網(wǎng)絡(luò)最大流的標(biāo)號(hào)法確定網(wǎng)絡(luò)最大流的標(biāo)號(hào)法l 從任一個(gè)初始可行流出發(fā)，如從任一個(gè)初始可行流出發(fā)，如 0 流流l 基本算法：找一條從基本算法：找一條從 s 到到 t 點(diǎn)的點(diǎn)的增廣鏈增廣鏈(augmenting path)l 若在當(dāng)前可行流下找不到增廣鏈，則已得到最大流若在當(dāng)前可行流下找不到增廣鏈，則已得到最大流l 增廣鏈中與增廣鏈中與 s 到到 t 方向一致的弧稱(chēng)為方向一致的弧稱(chēng)為前向弧前向弧，反之，反之后向弧后向弧 增廣過(guò)程：前向弧增廣過(guò)程：前向弧 f ij=fij+q q,后向弧后向弧 f ij=fij q q 增廣后仍是可行流

23、增廣后仍是可行流 st5432(3,0)(5,3)(1,1)(5,1)(1,1)q qs2=4q q5t=2q q45=3q q43=1q q32=1增增廣廣量量 q q =min q qij=min(4,1,1,3,2)=1st5432(3,1)(5,4)(1,0)(5,2)(1,0)后后向向弧弧前前向向弧弧ijijijijffcq q給出一個(gè)初始的可行流xij=02354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0找到所有的不飽和邊，以及各邊可以調(diào)整流

24、量的方向2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0找到一條從1到7的不飽和鏈鏈的間隙為：=min8,3,1,8=1調(diào)整鏈的流量：xij=xij+2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0=3=1=8=8x=0調(diào)整流量，f=1。繼續(xù)求出網(wǎng)絡(luò)的不飽和邊2354671f=1f=1u=6u=2u=4u=3u=7u=

25、4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=1x=1x=1x=1求出一條從1到7的不飽和鏈2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=1x=1x=1x=1=1=6=9=7=min 7,1,6,9=1,調(diào)整流量 xij=xij+1,f=f+1=2調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0 x=0 x=1x=0 x=0

26、 x=0 x=1x=1x=1x=1x=0求出一條從1到7的不飽和鏈2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0 x=0 x=1x=0 x=0 x=0 x=1x=1x=1x=1x=0=5=8=7=min 7,5,8=5,調(diào)整流量 xij=xij+5,f=f+5=2+5=7調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=0 x=1x=0 x=0 x=0 x=6x=1x=1x=6x=02354671f=7f=7u=6u=2u=4u=3u

27、=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=0 x=1x=0 x=0 x=0 x=6x=1x=1x=6x=0求出一條從1到7的不飽和鏈=min 6,7,4,3=3,調(diào)整流量 xij=xij+3,f=f+3=7+3=10=4=4=3=6調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊2354671f=10f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=3x=4x=3x=0 x=0 x=9x=1x=1x=6x=0求出一條從1到7的不飽和鏈2354671f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0

28、x=3x=4x=3x=0 x=0 x=9x=1x=1x=6x=0f=10=1=3=7=3=min 3,1,3,7=1,調(diào)整流量 xij=xij+1,f=f+1=10+1=11調(diào)整流量，繼續(xù)求出網(wǎng)絡(luò)的不飽和邊2354671f=11f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0 x=9x=2x=1x=6x=0已找不到一條從1到7的不飽和鏈，從1開(kāi)始可以到達(dá)的節(jié)點(diǎn)為1，2，3已求得最大流2354671f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0 x=4x=5x=3x=1x=0

29、 x=9x=2x=1x=6x=0f=11最大流f=11，最小割集為（2,5）（3,4）（3,5）u25+u34+u35=6+4+1=114 4最大流問(wèn)題最大流問(wèn)題l 最大流問(wèn)題：給一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱(chēng)之為容量，最大流問(wèn)題：給一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱(chēng)之為容量，在不超過(guò)每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。在不超過(guò)每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。一、最大流的數(shù)學(xué)模型一、最大流的數(shù)學(xué)模型 例例6 某石油公司擁有一個(gè)管道網(wǎng)絡(luò)，使用這個(gè)網(wǎng)絡(luò)可以把石油從采地某石油公司擁有一個(gè)管道網(wǎng)絡(luò)，使用這個(gè)網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷(xiāo)售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一部分如

30、下圖所示。由于管道的直徑運(yùn)送到一些銷(xiāo)售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（的變化，它的各段管道（vi,vj）的流量）的流量cij（容量）也是不一樣的。（容量）也是不一樣的。cij的的單位為萬(wàn)加侖單位為萬(wàn)加侖/小時(shí)。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從采地小時(shí)。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從采地 v1向銷(xiāo)地向銷(xiāo)地 v7運(yùn)送石運(yùn)送石油，問(wèn)每小時(shí)能運(yùn)送多少加侖石油？油，問(wèn)每小時(shí)能運(yùn)送多少加侖石油？v563522241263v1v2v7v4v3v6圖圖11-264 4最大流問(wèn)題最大流問(wèn)題 我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型：我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型：設(shè)弧設(shè)弧(vi,vj)上流量

31、為上流量為fij，網(wǎng)絡(luò)上的總的流量為，網(wǎng)絡(luò)上的總的流量為F，則有：，則有：1 41 22 32 51 44 34 64 72 34 33 53 62 53 55 73 64 66 75 76 74 71 21 4,1,2,6;1,2,70,1,2,6;1,2,71 2ijijijm a xF=fffffffffffffffffffffffffcijfij目 標(biāo) 函 數(shù)：約 束 條 件：5 5最小費(fèi)用最大流問(wèn)題最小費(fèi)用最大流問(wèn)題l 最小費(fèi)用最大流問(wèn)題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對(duì)每一條弧最小費(fèi)用最大流問(wèn)題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對(duì)每一條?。╲i,vj），除了給出容量），除了給出容量cij外，還給

32、出了這條弧的單位流量的費(fèi)用外，還給出了這條弧的單位流量的費(fèi)用bij，要，要求一個(gè)最大流求一個(gè)最大流F，并使得總運(yùn)送費(fèi)用最小。，并使得總運(yùn)送費(fèi)用最小。一、最小費(fèi)用最大流的數(shù)學(xué)模型一、最小費(fèi)用最大流的數(shù)學(xué)模型 例例7 由于輸油管道的長(zhǎng)短不一，所以在例由于輸油管道的長(zhǎng)短不一，所以在例6中每段管道（中每段管道（vi,vj）除）除了有不同的流量限制了有不同的流量限制cij外，還有不同的單位流量的費(fèi)用外，還有不同的單位流量的費(fèi)用bij，cij的單位為萬(wàn)的單位為萬(wàn)加侖加侖/小時(shí)，小時(shí)，bij的單位為百元的單位為百元/萬(wàn)加侖。如圖。從采地萬(wàn)加侖。如圖。從采地 v1向銷(xiāo)地向銷(xiāo)地 v7運(yùn)送石運(yùn)送石油，怎樣運(yùn)送才能

33、運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最小？求出最大流油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最小？求出最大流量和最小費(fèi)用。量和最小費(fèi)用。(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)5 5最小費(fèi)用最大流問(wèn)題最小費(fèi)用最大流問(wèn)題 這個(gè)最小費(fèi)用最大流問(wèn)題也是一個(gè)線性規(guī)劃的問(wèn)題。這個(gè)最小費(fèi)用最大流問(wèn)題也是一個(gè)線性規(guī)劃的問(wèn)題。解：我們用線性規(guī)劃來(lái)求解此題，可以分兩步走。解：我們用線性規(guī)劃來(lái)求解此題，可以分兩步走。第一步，先求出此網(wǎng)絡(luò)圖中的最大流量第一步，先求出此網(wǎng)絡(luò)圖中的最大流量F，這已在例，這已在例6中建中

34、建立了線性規(guī)劃的模型，通過(guò)管理運(yùn)籌學(xué)軟件已經(jīng)獲得結(jié)果。立了線性規(guī)劃的模型，通過(guò)管理運(yùn)籌學(xué)軟件已經(jīng)獲得結(jié)果。第二步，在最大流量第二步，在最大流量F的所有解中，找出一個(gè)最小費(fèi)用的的所有解中，找出一個(gè)最小費(fèi)用的解，我們來(lái)建立第二步中的線性規(guī)劃模型如下：解，我們來(lái)建立第二步中的線性規(guī)劃模型如下：仍然設(shè)?。ㄈ匀辉O(shè)?。╲i,vj）上的流量為）上的流量為fij，這時(shí)已知網(wǎng)絡(luò)中最大流量，這時(shí)已知網(wǎng)絡(luò)中最大流量為為F，只要在例，只要在例6的約束條件上，再加上總流量必須等于的約束條件上，再加上總流量必須等于F的約的約束條件：束條件：f12=f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的即得此線性規(guī)劃的約束條件

35、，此線性規(guī)劃的目標(biāo)函數(shù)顯然是求其流量的最小費(fèi)用目標(biāo)函數(shù)顯然是求其流量的最小費(fèi)用 。由此得到線性規(guī)劃模型如下：由此得到線性規(guī)劃模型如下：(,)iji ji jvvAfb5 5最小費(fèi)用最大流問(wèn)題最小費(fèi)用最大流問(wèn)題 1214252343(,)355736464767121412232514434647234335362535573646675767471214min63452473384.10,(1,2,6;ijijijvvAijijfbfffffffffffs tffFfffffffffffffffffffffffcij2,3,7),0,(1,2,6;2,3,7),ijfij5 5最小費(fèi)用最大流問(wèn)

36、題最小費(fèi)用最大流問(wèn)題 用運(yùn)籌學(xué)軟件，可求得如下結(jié)果：用運(yùn)籌學(xué)軟件，可求得如下結(jié)果：f f1212=4,f=4,f1414=6,=6,f f2525=3,f=3,f2323=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)值(最小費(fèi)用最小費(fèi)用)=145)=145。對(duì)照前面例。對(duì)照前面例6 6的結(jié)果，可對(duì)最小費(fèi)用最的結(jié)果，可對(duì)最小費(fèi)用最大流的概念有一個(gè)深刻的理解。大流的概念有一個(gè)深刻的理解。如果我們把例如果我們把例7 7的問(wèn)題改為：每小時(shí)運(yùn)送的問(wèn)題改為：每

37、小時(shí)運(yùn)送6 6萬(wàn)加侖的石油萬(wàn)加侖的石油從采地從采地v v1 1到銷(xiāo)地到銷(xiāo)地v v7 7最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了一個(gè)最小費(fèi)用流的問(wèn)題。一般來(lái)說(shuō)，所謂最小費(fèi)用流的問(wèn)題一個(gè)最小費(fèi)用流的問(wèn)題。一般來(lái)說(shuō)，所謂最小費(fèi)用流的問(wèn)題就是：在給定了收點(diǎn)和發(fā)點(diǎn)并對(duì)每條弧就是：在給定了收點(diǎn)和發(fā)點(diǎn)并對(duì)每條弧(v(vi i,v,vj j)賦權(quán)以容量賦權(quán)以容量c cijij及單位費(fèi)用及單位費(fèi)用b bijij的網(wǎng)絡(luò)中，求一個(gè)給定值的網(wǎng)絡(luò)中，求一個(gè)給定值f f的流量的最小費(fèi)用，的流量的最小費(fèi)用，這個(gè)給定值這個(gè)給定值f f的流量應(yīng)小于等于最大流量的流量應(yīng)小于等于最大流量F F，否則無(wú)解。求最，否則無(wú)解。求最小費(fèi)用流的問(wèn)題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模小費(fèi)用流的問(wèn)題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模型中的約束條件中的發(fā)點(diǎn)流量型中的約束條件中的發(fā)點(diǎn)流量F F改為改為f f即可。在例即可。在例6 6中只要把中只要把f f1212+f+f1414=F=F改為改為f f1212+f+f1414=f=6=f=6得到了最小費(fèi)用流的線性規(guī)劃的模型得到了最小費(fèi)用流的線性規(guī)劃的模型了。了。