運(yùn)籌學(xué)圖與網(wǎng)絡(luò)模型以及最小費(fèi)用最大流PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 長(zhǎng)江漢江您能從武漢理工大學(xué)出發(fā)走您能從武漢理工大學(xué)出發(fā)走過每座橋且只走一次然后回過每座橋且只走一次然后回到學(xué)校嗎到學(xué)校嗎? ?第1頁(yè)/共100頁(yè)近代圖論的歷史可追溯到近代圖論的歷史可追溯到18世紀(jì)的七橋問題世紀(jì)的七橋問題穿過穿過Knigsberg城的七座橋，要求每座橋通過一次且僅通過一次城的七座橋，要求每座橋通過一次且僅通過一次。 這就是著名的這就是著名的“哥尼斯堡哥尼斯堡 7 橋橋”難題。難題。Euler1736年證明了年證明了不可能存在這樣的路線。不可能存在這樣的路線。第2頁(yè)/共100頁(yè)若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，則若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間

2、的聯(lián)系，則圖圖G可以定義為點(diǎn)和邊的集合，記作：可以定義為點(diǎn)和邊的集合，記作：,EVG 其中其中: : V點(diǎn)集點(diǎn)集 E邊集邊集 圖圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪些點(diǎn)之間有連線。些點(diǎn)之間有連線。第3頁(yè)/共100頁(yè)(v1)趙(v2)錢孫(v3) 李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的?？梢妶D論中的圖與幾何圖、工程圖是不一樣的。例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)

3、表示。例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)表示。第4頁(yè)/共100頁(yè)6a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙趙(v2)錢錢(v3)孫孫(v4)李李(v5)周周(v6)吳吳(v7)陳陳圖圖11-3 如果我們把上面例子中的如果我們把上面例子中的“相互認(rèn)識(shí)相互認(rèn)識(shí)”關(guān)系改為關(guān)系改為“認(rèn)識(shí)認(rèn)識(shí)” ” 的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個(gè)帶箭頭的聯(lián)線，稱為弧一個(gè)帶箭頭的聯(lián)線，稱為弧。圖。圖11-311-3就是一個(gè)反映這七人就是一個(gè)反映這七人

4、“認(rèn)識(shí)認(rèn)識(shí)”關(guān)系的圖。相互認(rèn)識(shí)用兩條反向的弧表示。關(guān)系的圖。相互認(rèn)識(shí)用兩條反向的弧表示。第5頁(yè)/共100頁(yè)v3e7e4e8e5e6e1e2e3v1v2v4v5若有邊若有邊e可表示為可表示為e=vi,vj，稱，稱vi和和vj是邊是邊e的的端點(diǎn)端點(diǎn)，反之稱邊，反之稱邊e為點(diǎn)為點(diǎn)vi或或vj的的關(guān)聯(lián)邊關(guān)聯(lián)邊。若點(diǎn)。若點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和和vj相鄰；若邊相鄰；若邊ei和和ej具有公共的端點(diǎn)，稱邊具有公共的端點(diǎn)，稱邊ei和和ej相鄰相鄰。第6頁(yè)/共100頁(yè) 如果邊如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)環(huán)。如右圖中邊。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)

5、之間多于一條，稱為為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱為多重邊多重邊，如右圖中的，如右圖中的e4和和e5，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作簡(jiǎn)單圖簡(jiǎn)單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5第7頁(yè)/共100頁(yè) 圖中某些點(diǎn)和邊的交替序列，若其中各邊互不相同，且對(duì)任意圖中某些點(diǎn)和邊的交替序列，若其中各邊互不相同，且對(duì)任意Vi-1,Vi 和和vi+1均相鄰稱為均相鄰稱為鏈鏈。用。用表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5,110kkvevev 起點(diǎn)與終點(diǎn)重合的鏈稱作起點(diǎn)與終點(diǎn)重合的鏈稱作圈圈。如果每一對(duì)頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為。如果每一

6、對(duì)頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為連通圖連通圖，否則稱，否則稱圖不連通圖不連通。第8頁(yè)/共100頁(yè) ）(P232)(P232)設(shè)圖設(shè)圖G（V，E），對(duì)），對(duì)G的每一條邊的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊稱為邊(vi,vj)的權(quán)的權(quán),賦予權(quán)的圖賦予權(quán)的圖G稱為稱為網(wǎng)絡(luò)網(wǎng)絡(luò)(或賦權(quán)圖）。或賦權(quán)圖）。權(quán)權(quán)可以代表距離、費(fèi)用、通過能力可以代表距離、費(fèi)用、通過能力(容量容量)等等。等等。端點(diǎn)無(wú)序的賦權(quán)圖稱為端點(diǎn)無(wú)序的賦權(quán)圖稱為無(wú)向網(wǎng)絡(luò)無(wú)向網(wǎng)絡(luò)，端點(diǎn)有序的賦權(quán)圖稱為，端點(diǎn)有序的賦權(quán)圖稱為有向網(wǎng)絡(luò)。有向網(wǎng)絡(luò)。910201571419256第9頁(yè)/共100頁(yè)11第

7、10頁(yè)/共100頁(yè)ABC第11頁(yè)/共100頁(yè)ABCP但若增加一個(gè)周轉(zhuǎn)站（新點(diǎn)但若增加一個(gè)周轉(zhuǎn)站（新點(diǎn)P），連接），連接4點(diǎn)的新網(wǎng)絡(luò)的最短路線為點(diǎn)的新網(wǎng)絡(luò)的最短路線為PAPBPC。最短新路徑之長(zhǎng)。最短新路徑之長(zhǎng)N比原來(lái)只連三點(diǎn)的最短路徑比原來(lái)只連三點(diǎn)的最短路徑O要短。這樣得到的網(wǎng)絡(luò)不僅比原來(lái)節(jié)省材料，而且穩(wěn)定性也更好。要短。這樣得到的網(wǎng)絡(luò)不僅比原來(lái)節(jié)省材料，而且穩(wěn)定性也更好。第12頁(yè)/共100頁(yè)第13頁(yè)/共100頁(yè)第14頁(yè)/共100頁(yè)我們可以得到下面的加權(quán)有向圖我們可以得到下面的加權(quán)有向圖：第15頁(yè)/共100頁(yè)此游戲轉(zhuǎn)化為在下面的二部圖中求從此游戲轉(zhuǎn)化為在下面的二部圖中求從 v v1 1 到到

8、u u1 1 的最短路問題。的最短路問題。v1v2v3v4v5u5u4u3u2u1第16頁(yè)/共100頁(yè) 狄克斯屈拉狄克斯屈拉(Dijkstra)（雙標(biāo)號(hào)）算法（雙標(biāo)號(hào)）算法 逐次逼近算法逐次逼近算法最短路問題：最短路問題：對(duì)一個(gè)賦權(quán)的有向圖對(duì)一個(gè)賦權(quán)的有向圖D中的指定的兩個(gè)點(diǎn)中的指定的兩個(gè)點(diǎn)Vs和和Vt找找到一條從到一條從 Vs 到到 Vt 的路，使得這條路上所有弧的權(quán)數(shù)的總和最小的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從，這條路被稱之為從Vs到到Vt的最短路。這條路上所有弧的權(quán)數(shù)的的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從總和被稱為從Vs到到Vt的距離。的距離。第17頁(yè)/共

9、100頁(yè)假定假定v1v2 v3 v4是是v1 v4的最短路，則的最短路，則v1 v2 v3一定是一定是v1 v3的最短路，的最短路，v2 v3 v4也一定是也一定是v2 v4的最短路。的最短路。v1v2v3v4v5第18頁(yè)/共100頁(yè)此弧為（此弧為（Vc,Vd），則給此弧的終點(diǎn)以雙標(biāo)號(hào)），則給此弧的終點(diǎn)以雙標(biāo)號(hào)（scd,c）,返回步驟返回步驟2。( ,)|,ijijv vvI vJ第19頁(yè)/共100頁(yè)v23527531512v1v6v5v3v4(3,1)v23527531512 V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4第20頁(yè)/共100頁(yè) V1 （甲地）（甲地）151762

10、444 31065v2V7 （乙地）（乙地）v3v4v5v6第21頁(yè)/共100頁(yè)（0,s） V1 （甲地）（甲地）1517624431065(13,3) v2 (22,6)V7 （乙地）（乙地）V5(14,3)V6(16,5) V3(10,1) V4(18,5)第22頁(yè)/共100頁(yè)年份年份12345年初價(jià)格年初價(jià)格1111121213使用年數(shù)使用年數(shù)0-11-22-33-44-5每年維修每年維修費(fèi)用費(fèi)用5681118第23頁(yè)/共100頁(yè)v1v2v3v4v5v6123456116223041592162230413172331417235186第24頁(yè)/共100頁(yè)v1v2v3v4v5v61622

11、30415916223041312317181723 V1（0,s）v3v4(41,1) v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)第25頁(yè)/共100頁(yè)v3v54v1v2v4v635222421v1到到v6的最短路為：的最短路為：6521vvvv第26頁(yè)/共100頁(yè)237184566134105275934682第27頁(yè)/共100頁(yè)237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路徑為的最短路徑為v1v4v7v5v8，最短距

12、離為，最短距離為10第28頁(yè)/共100頁(yè)v1v2v3v4v6v5322762133第29頁(yè)/共100頁(yè)v1V2V3V4 V6V5322762133024714第30頁(yè)/共100頁(yè)v1V2V3V4 V6V5322762133024714第31頁(yè)/共100頁(yè)例例6.7 如右圖所示中按如右圖所示中按dijkstra算法可得算法可得P(v1)=5為從為從vsv1的最短路長(zhǎng)顯然是錯(cuò)誤的，從的最短路長(zhǎng)顯然是錯(cuò)誤的，從vsv2v1路長(zhǎng)只有路長(zhǎng)只有3。v2vsv15-58第32頁(yè)/共100頁(yè)樹是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)域應(yīng)用極為廣泛。樹是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)

13、域應(yīng)用極為廣泛。例例6.2 乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。ABCDEFGH運(yùn)動(dòng)員運(yùn)動(dòng)員第33頁(yè)/共100頁(yè)廠長(zhǎng)廠長(zhǎng)人事科人事科財(cái)務(wù)科財(cái)務(wù)科總工總工程師程師生產(chǎn)副生產(chǎn)副廠長(zhǎng)廠長(zhǎng)經(jīng)營(yíng)副經(jīng)營(yíng)副廠長(zhǎng)廠長(zhǎng)開發(fā)科開發(fā)科技術(shù)科技術(shù)科生產(chǎn)科生產(chǎn)科設(shè)備科設(shè)備科供應(yīng)科供應(yīng)科銷售科銷售科檢驗(yàn)科檢驗(yàn)科動(dòng)力科動(dòng)力科第34頁(yè)/共100頁(yè)任何樹中必存在次為任何樹中必存在次為1的點(diǎn)。的點(diǎn)。(一個(gè)點(diǎn)一個(gè)點(diǎn)Vi的相關(guān)聯(lián)邊的數(shù)目稱為點(diǎn)的相關(guān)聯(lián)邊的數(shù)目稱為點(diǎn)Vi的次的次)n 個(gè)頂點(diǎn)的樹必有個(gè)頂點(diǎn)的樹必有n-1 條邊。條邊。樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅

14、有一條鏈。樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。樹連通，但去掉任一條邊，必變?yōu)椴贿B通。樹連通，但去掉任一條邊，必變?yōu)椴贿B通。樹無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)圈。樹無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)圈。v1v2v3v4v5v6第35頁(yè)/共100頁(yè)37 圖圖11-11中，中，(a)就是一個(gè)樹，而就是一個(gè)樹，而(b)因?yàn)閳D中有圈所以就不是樹，因?yàn)閳D中有圈所以就不是樹， (c)因?yàn)椴贿B通所以也不是樹。因?yàn)椴贿B通所以也不是樹。圖圖11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)第36頁(yè)/

15、共100頁(yè) 如果如果G2是是G1的部分圖，又是樹圖，則稱的部分圖，又是樹圖，則稱G2是是G1的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖G1含有多個(gè)部分樹，其中樹枝總長(zhǎng)最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。含有多個(gè)部分樹，其中樹枝總長(zhǎng)最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。v1v2v3v4v5v1v2v3v4v5G1G2第37頁(yè)/共100頁(yè)第38頁(yè)/共100頁(yè)第39頁(yè)/共100頁(yè)第40頁(yè)/共100頁(yè)第41頁(yè)/共100頁(yè)第42頁(yè)/共100頁(yè)44 給了一個(gè)無(wú)向圖給了一個(gè)無(wú)向圖G=(V,E)，我們保留，我們保留G的所有

16、點(diǎn)，而刪掉部分的所有點(diǎn)，而刪掉部分G的邊或的邊或者說保留一部分者說保留一部分G的邊，所獲得的圖的邊，所獲得的圖G，稱之為，稱之為G的生成子圖。在圖的生成子圖。在圖11-12中，中，(b)和和(c)都是都是(a)的生成子圖。的生成子圖。 如果圖如果圖G的一個(gè)生成子圖還是一個(gè)樹，則稱這個(gè)生成子圖為生成樹，在的一個(gè)生成子圖還是一個(gè)樹，則稱這個(gè)生成子圖為生成樹，在圖圖11-12中，中，(c)就是就是(a)的生成樹。的生成樹。 最小生成樹問題就是指在一個(gè)賦權(quán)的連通的無(wú)向圖最小生成樹問題就是指在一個(gè)賦權(quán)的連通的無(wú)向圖G中找出一個(gè)生成樹中找出一個(gè)生成樹，并使得這個(gè)生成樹的所有邊的權(quán)數(shù)之和為最小。，并使得這個(gè)

17、生成樹的所有邊的權(quán)數(shù)之和為最小。圖圖11-12(a)(b)(c)第43頁(yè)/共100頁(yè)第44頁(yè)/共100頁(yè)部分樹第45頁(yè)/共100頁(yè)v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5第46頁(yè)/共100頁(yè)：任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521邊數(shù)邊數(shù)n-1=5第47頁(yè)/共100頁(yè)v1v2v3v4v5v643521得到最小樹得到最小樹：Min C(T)=15第48頁(yè)/共100頁(yè)5v1v2v3v4v5v6843752618第49頁(yè)/共1

18、00頁(yè)v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15第50頁(yè)/共100頁(yè)第51頁(yè)/共100頁(yè)第52頁(yè)/共100頁(yè)第53頁(yè)/共100頁(yè)第54頁(yè)/共100頁(yè)第55頁(yè)/共100頁(yè)第56頁(yè)/共100頁(yè)第57頁(yè)/共100頁(yè)第58頁(yè)/共100頁(yè)第59頁(yè)/共100頁(yè)第60頁(yè)/共100頁(yè)第61頁(yè)/共100頁(yè)第62頁(yè)/共100頁(yè)第63頁(yè)/共100頁(yè)第64頁(yè)/共100頁(yè)第65頁(yè)/共100頁(yè)第66頁(yè)/共100頁(yè)第67頁(yè)/共100頁(yè)第68頁(yè)/共100頁(yè)第69頁(yè)/共100頁(yè)第70頁(yè)/共100頁(yè)3749346321Min C(T)=12Min C(T)=1525417

19、3314475答案：第71頁(yè)/共100頁(yè)34122323242Min C(T)=12213638534567454321Min C(T)=18第72頁(yè)/共100頁(yè)74 解：此問題實(shí)際上是求圖解：此問題實(shí)際上是求圖11-1411-14的最小生成樹，這在例的最小生成樹，這在例4 4中已經(jīng)求得中已經(jīng)求得，也即按照?qǐng)D，也即按照?qǐng)D11-1311-13的的(f)(f)設(shè)計(jì)，可使此網(wǎng)絡(luò)的總的線路長(zhǎng)度為最短，為設(shè)計(jì)，可使此網(wǎng)絡(luò)的總的線路長(zhǎng)度為最短，為1919百米。百米。 “ “管理運(yùn)籌學(xué)軟件管理運(yùn)籌學(xué)軟件”有專門的子程序可以解決最小生成樹問題。有專門的子程序可以解決最小生成樹問題。v1331728541034

20、v7v6v5v4v2v3圖圖11-14第73頁(yè)/共100頁(yè)第74頁(yè)/共100頁(yè)st4844122679第75頁(yè)/共100頁(yè)3. 3. 流與可行流流與可行流 流流是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對(duì)加在弧是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對(duì)加在弧(vi,vj)上的負(fù)載量記為上的負(fù)載量記為fij。若。若fij=0，稱為零流。，稱為零流。滿足以下條件的一組流稱為滿足以下條件的一組流稱為可行流可行流。 容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足：容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足：0fijcij 中間點(diǎn)平衡條件。中間點(diǎn)平衡條件。),(0),(),(tsivvfvvfijji 若以若以v(f)表示網(wǎng)絡(luò)中從表示網(wǎng)

21、絡(luò)中從st的流量，則有：的流量，則有： 0),(),()(tjjsvvfvvffv第76頁(yè)/共100頁(yè)結(jié)論結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）網(wǎng)絡(luò)最大流問題：網(wǎng)絡(luò)最大流問題：指滿足容量限制條件和中間點(diǎn)平衡的條件下，使指滿足容量限制條件和中間點(diǎn)平衡的條件下，使v(f)v(f)值達(dá)到最大。值達(dá)到最大。第77頁(yè)/共100頁(yè)79v563522241263v1v2v7v4v3v6圖圖11-26第78頁(yè)/共100頁(yè)1412232514434647234335362535573646675767471214,1,2,6;1,2,70,1,2,6;1

22、,2,712ijijijmaxF = fffffffffffffffffffffffffcijfij目標(biāo)函數(shù)：約束條件：80 我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型：我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型： 設(shè)弧設(shè)弧(vi,vj)上流量為上流量為fij，網(wǎng)絡(luò)上的總的流量為，網(wǎng)絡(luò)上的總的流量為F，則有：，則有：第79頁(yè)/共100頁(yè)81 在這個(gè)線性規(guī)劃模型中，其約束條件中的前在這個(gè)線性規(guī)劃模型中，其約束條件中的前6 6個(gè)方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，個(gè)方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件，發(fā)點(diǎn)的流出量必須等于收點(diǎn)的總流入量發(fā)點(diǎn)的流出量必須等于收點(diǎn)的總流入量；其余的點(diǎn)稱之為；其余的點(diǎn)稱之為中

23、間點(diǎn)中間點(diǎn)，它的總流入量必須等于總流出量。其后面幾個(gè)約束條件表示對(duì)每一條弧，它的總流入量必須等于總流出量。其后面幾個(gè)約束條件表示對(duì)每一條弧(v(vi i,v,vj j) )的流量的流量fij要滿足流量的可行條件，應(yīng)小于等于弧要滿足流量的可行條件，應(yīng)小于等于弧(v(vi i,v,vj j) )的容量的容量c cijij，并大于等于零，即，并大于等于零，即0 0f fijij c cijij。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流 ffijij 稱之為稱之為可行流可行流，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點(diǎn)總流出量最大）的稱之

24、為，（即線性規(guī)劃的可行解），可行流中一組流量最大（也即發(fā)出點(diǎn)總流出量最大）的稱之為最大流最大流（即線性規(guī)劃的最優(yōu)解）。（即線性規(guī)劃的最優(yōu)解）。 我們把例我們把例6 6的數(shù)據(jù)代入以上線性規(guī)劃模型，用的數(shù)據(jù)代入以上線性規(guī)劃模型，用“管理運(yùn)籌學(xué)軟件管理運(yùn)籌學(xué)軟件”，馬上得到以下的結(jié)果：，馬上得到以下的結(jié)果：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)值（最大流

25、量）=10=10。第80頁(yè)/共100頁(yè)82vivjvivjcij0（a）（b） cijcijvivj（cji）（c）vivj cij cji（d）63522241263v1v2v5v7v4v3v600000000000第81頁(yè)/共100頁(yè)8363522241263v1v2v5v7v4v3v6000000000004202第82頁(yè)/共100頁(yè)84635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v600000042022033333013第83頁(yè)/共100頁(yè)8522243v1v2v5v7v4v3v610000120320333

26、5031200231322v1v2v5v7v4v3v61012020333501202313150020205第84頁(yè)/共100頁(yè)8622v1v2v5v7v4v3v6123522355 “管理運(yùn)籌學(xué)軟件管理運(yùn)籌學(xué)軟件”中還有專門的子程序用于解決最大流問題。中還有專門的子程序用于解決最大流問題。第85頁(yè)/共100頁(yè)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)第86頁(yè)/共100頁(yè)(,)ijijijv vAfb88 這個(gè)最小費(fèi)用最大流問題也是一個(gè)線性規(guī)劃的問題。這個(gè)最小費(fèi)用最大流問題也是一個(gè)線性規(guī)劃的問

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

28、例，只要在例6的約束條件上，再加上總流量必須等于的約束條件上，再加上總流量必須等于F的約束條件：的約束條件：f12=f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標(biāo)函數(shù)顯然是求其流量的最小費(fèi)用即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標(biāo)函數(shù)顯然是求其流量的最小費(fèi)用 fij . bij 。 由此得到線性規(guī)劃模型如下：由此得到線性規(guī)劃模型如下：第87頁(yè)/共100頁(yè)1214252343(,)355736464767121412232514434647234335362535573646675767471214min63452473384. .10,(1,2,6;ijijijv vAijijfbf

29、ffffffffffstffFfffffffffffffffffffffffcij2,3,7),0,(1,2,6;2,3,7),ijfij89第88頁(yè)/共100頁(yè)90 用管理運(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é)果，

30、可對(duì)最小費(fèi)用最大流的概念有一個(gè)深刻的理解。的結(jié)果，可對(duì)最小費(fèi)用最大流的概念有一個(gè)深刻的理解。 如果我們把例如果我們把例7 7的問題改為：每小時(shí)運(yùn)送的問題改為：每小時(shí)運(yùn)送6 6萬(wàn)加侖的石油從采地萬(wàn)加侖的石油從采地v v1 1到銷地到銷地v v7 7最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了一個(gè)最小費(fèi)用流的問題。一般來(lái)說，所謂最小費(fèi)用流的問題就是：最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了一個(gè)最小費(fèi)用流的問題。一般來(lá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)

31、絡(luò)中，求一個(gè)給定值的網(wǎng)絡(luò)中，求一個(gè)給定值f f的流量的最小費(fèi)用，這個(gè)給定值的流量的最小費(fèi)用，這個(gè)給定值f f的流量應(yīng)的流量應(yīng)小于等于最大流量小于等于最大流量F F，否則無(wú)解。，否則無(wú)解。求最小費(fèi)用流的問題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模型中的約束條件中的發(fā)點(diǎn)流量求最小費(fèi)用流的問題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模型中的約束條件中的發(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ī)劃的模型了。第89頁(yè)/共100頁(yè)91

32、vivjvivj（cij,bij ）（0,-bij ）（a）（b）（cij,bij ）（cij,bij ）vivj（cji,bji ）（cij,bij ）vivj（cji,bji ）（0,-bji)（0,-bji)（c）（d）第90頁(yè)/共100頁(yè)92(6,6)(3,4)(5,7)(2,5)(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-11-2828第91頁(yè)/共100頁(yè)93v5(6,6)(3,4)(5,7

33、)(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-11-2929第92頁(yè)/共100頁(yè)94(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖圖11-11-3030第93頁(yè)/共100頁(yè)95(6,6)(3,4)(5,7)(2,5)(0,-4)（0,3）(1,4)(0,3)(0,8)（1,2）v1v2v5v7v4v3v6(1,3)(5,-3)(2,-8