圖論方法[共85頁]

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

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

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

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

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

5、(jivvijlijliv,svjvtvsvtv),()(jivvijlL最小。最短路算法中1959年由 （狄克斯特洛）提出的算法被公認(rèn)為是目前最好的方法，我們稱之為 算法。下面通過例子來說明此法的基本思想。DijkstraDijkstra條件：所有的權(quán)數(shù) 0ijl思路：逐步探尋。1v2v3v5v7v8v6v4v46761519554471v2v3v5v7v8v6v4v4676151955447下求 到 的最短路：1v8v1）從 出發(fā)，向 走。首先，從 到 的距離為0，給 標(biāo)號(hào)（0）。畫第一個(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)的路，或者說，已完成 的標(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長度為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 第二講：最短路問題的兩個(gè)應(yīng)用最短路問題在圖論應(yīng)用中處于很重要的地位，下面舉兩個(gè)實(shí) 際應(yīng)用的例子。例 設(shè)備更新問題某工廠使用一臺(tái)設(shè)備，每年年初工廠要作出決定：繼續(xù)使 用，購買新的？如果繼續(xù)使用舊的，要負(fù)維修費(fèi)；若要購買 一套新的，要負(fù)購買費(fèi)。試確定一個(gè)5年計(jì)劃，使總支出最小若已知設(shè)備在各年的購買費(fèi)，及不同機(jī)器役齡時(shí)的殘值與維修費(fèi)，如表所示.項(xiàng)目第1年第2年第3年第4年第5年購買費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)56811

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

13、：求從 到 的最短路問題.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最短路路長為49。即：在第一年、第三年初各購買一臺(tái)新設(shè)備為最優(yōu)決策。這時(shí)5年的總費(fèi)用為49。例13(選址問題)已知某地區(qū)的交通網(wǎng)絡(luò)如圖所示，其中點(diǎn)代表居民小區(qū)，邊代表公路，為小區(qū)間公路距離，問區(qū)中心醫(yī)院應(yīng)建在哪個(gè)小區(qū)，可使離醫(yī)院最遠(yuǎn)的小區(qū)居民就診時(shí)所走的路程最近？1v6v3v2v4v5v7v301520301520256018解 求中心的問題。解決方法：先求出 到其它各點(diǎn)的最短路長如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é)果見下表：小區(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)路上支路的容量為其最大通過能力，記為 rij，支路上的實(shí)際流量記為 xij,網(wǎng)絡(luò)流為所有通過弧的流量的集合.l 圖中規(guī)定一個(gè)發(fā)點(diǎn)s，一個(gè)收點(diǎn)tl 節(jié)點(diǎn)沒有容量限制，流在節(jié)點(diǎn)不會(huì)存儲(chǔ)4 4 最大流問題最大流

19、問題可行流可行流滿足以下條件的流稱為可行流：滿足以下條件的流稱為可行流：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的鏈的鏈,在鏈中與鏈的方在鏈中與鏈的方向一致的弧稱為鏈的向一致的弧稱為鏈的前向弧前向弧,在鏈中與鏈的方向相反的弧稱在鏈中與鏈的方向相反的弧稱為鏈的為鏈的前向弧前向弧.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中的弧的集合稱為分離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 方向一致的弧稱為方向一致的弧稱為前向弧前向弧，反之，反之后向弧后向弧 增廣過程：前向弧增廣過程：前向弧 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開始可以到達(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最大流問題最大流問題l 最大流問題：給一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，最大流問題：給一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。在不超過每條弧的容量的前提下，求出從發(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)送到一些銷售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一部分如

30、下圖所示。由于管道的直徑運(yùn)送到一些銷售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（的變化，它的各段管道（vi,vj）的流量）的流量cij（容量）也是不一樣的。（容量）也是不一樣的。cij的的單位為萬加侖單位為萬加侖/小時(shí)。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從采地小時(shí)。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從采地 v1向銷地向銷地 v7運(yùn)送石運(yùn)送石油，問每小時(shí)能運(yùn)送多少加侖石油？油，問每小時(shí)能運(yùn)送多少加侖石油？v563522241263v1v2v7v4v3v6圖圖11-264 4最大流問題最大流問題 我們可以為此例題建立線性規(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)用最大流問題最小費(fèi)用最大流問題l 最小費(fèi)用最大流問題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對(duì)每一條弧最小費(fèi)用最大流問題：給了一個(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 由于輸油管道的長短不一，所以在例由于輸油管道的長短不一，所以在例6中每段管道（中每段管道（vi,vj）除）除了有不同的流量限制了有不同的流量限制cij外，還有不同的單位流量的費(fèi)用外，還有不同的單位流量的費(fèi)用bij，cij的單位為萬的單位為萬加侖加侖/小時(shí)，小時(shí)，bij的單位為百元的單位為百元/萬加侖。如圖。從采地萬加侖。如圖。從采地 v1向銷地向銷地 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)用最大流問題最小費(fèi)用最大流問題 這個(gè)最小費(fèi)用最大流問題也是一個(gè)線性規(guī)劃的問題。這個(gè)最小費(fèi)用最大流問題也是一個(gè)線性規(guī)劃的問題。解：我們用線性規(guī)劃來求解此題，可以分兩步走。解：我們用線性規(guī)劃來求解此題，可以分兩步走。第一步，先求出此網(wǎng)絡(luò)圖中的最大流量第一步，先求出此網(wǎng)絡(luò)圖中的最大流量F，這已在例，這已在例6中建中

34、建立了線性規(guī)劃的模型，通過管理運(yùn)籌學(xué)軟件已經(jīng)獲得結(jié)果。立了線性規(guī)劃的模型，通過管理運(yùn)籌學(xué)軟件已經(jīng)獲得結(jié)果。第二步，在最大流量第二步，在最大流量F的所有解中，找出一個(gè)最小費(fèi)用的的所有解中，找出一個(gè)最小費(fèi)用的解，我們來建立第二步中的線性規(guī)劃模型如下：解，我們來建立第二步中的線性規(guī)劃模型如下：仍然設(shè)?。ㄈ匀辉O(shè)弧（vi,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)用最大流問題最小費(fèi)用最大流問題 1214252343(,)355736464767121412232514434647234335362535573646675767471214min63452473384.10,(1,2,6;ijijijvvAijijfbfffffffffffs tffFfffffffffffffffffffffffcij2,3,7),0,(1,2,6;2,3,7),ijfij5 5最小費(fèi)用最大流問

36、題最小費(fèi)用最大流問題 用運(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的問題改為：每小時(shí)運(yùn)送的問題改為：每

37、小時(shí)運(yùn)送6 6萬加侖的石油萬加侖的石油從采地從采地v v1 1到銷地到銷地v v7 7最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了一個(gè)最小費(fèi)用流的問題。一般來說，所謂最小費(fèi)用流的問題一個(gè)最小費(fèi)用流的問題。一般來說，所謂最小費(fèi)用流的問題就是：在給定了收點(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，否則無解。求最，否則無解。求最小費(fèi)用流的問題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模小費(fèi)用流的問題的線性規(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ī)劃的模型了。了。