運(yùn)籌學(xué)-圖與網(wǎng)絡(luò)模型以及最小費(fèi)用最大流培訓(xùn)資料

1、福建師范大學(xué)經(jīng)濟(jì)學(xué)院管管 理理 運(yùn)運(yùn) 籌籌 學(xué)學(xué)運(yùn)籌學(xué)-圖與網(wǎng)絡(luò)模型以及最小費(fèi)用最大流近代圖論的歷史可追溯到近代圖論的歷史可追溯到18世紀(jì)的七橋問(wèn)題世紀(jì)的七橋問(wèn)題穿過(guò)穿過(guò)Knigsberg城的七座橋，要求每座橋通過(guò)一次且僅通過(guò)一次。城的七座橋，要求每座橋通過(guò)一次且僅通過(guò)一次。 這就是著名這就是著名的的“哥尼斯堡哥尼斯堡 7 橋橋”難題。難題。Euler1736年證明了不可能存在這樣年證明了不可能存在這樣的路線。的路線。 圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。 一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲一般情況下圖中點(diǎn)

2、的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，則圖若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(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)之間有連線。(v1)趙(v2)錢(qián)孫(v3) 李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(qián)(v3)孫(

3、v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見(jiàn)圖論中的圖與幾何圖、工程圖是不一樣的?？梢?jiàn)圖論中的圖與幾何圖、工程圖是不一樣的。例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)表示。表示。a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙趙(v2)錢(qián)錢(qián)(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)線就很難刻畫(huà)他們之間的關(guān)的關(guān)系，那么只用兩點(diǎn)之

4、間的聯(lián)線就很難刻畫(huà)他們之間的關(guān)系了，這是我們引入系了，這是我們引入一個(gè)帶箭頭的聯(lián)線，稱為弧一個(gè)帶箭頭的聯(lián)線，稱為弧。圖。圖11-311-3就就是一個(gè)反映這七人是一個(gè)反映這七人“認(rèn)識(shí)認(rèn)識(shí)”關(guān)系的圖。相互認(rèn)識(shí)用兩條反向關(guān)系的圖。相互認(rèn)識(shí)用兩條反向的弧表示。的弧表示。 定義定義: : 圖中的點(diǎn)用圖中的點(diǎn)用v v表示，邊用表示，邊用e e表示。對(duì)每條邊可用它所表示。對(duì)每條邊可用它所連接的點(diǎn)表示，記作：連接的點(diǎn)表示，記作：e e1 1=v=v1 1,v,v1 1; e; e2 2=v=v1 1,v,v2 2; ; v3e7e4e8e5e6e1e2e3v1v2v4v5若有邊若有邊e可表示為可表示為e=vi

5、,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)與同一條邊關(guān)聯(lián)，稱點(diǎn)聯(lián)，稱點(diǎn)vi和和vj相鄰；若邊相鄰；若邊ei和和ej具具有公共的端點(diǎn)，稱邊有公共的端點(diǎn)，稱邊ei和和ej相鄰相鄰。 如果邊如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)環(huán)。如右圖中邊。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱為之間多于一條，稱為多重邊多重邊，如右圖，如右圖中的中的e4和和e5，對(duì)無(wú)環(huán)、無(wú)多重邊的圖，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作稱作簡(jiǎn)單圖簡(jiǎn)單圖。v3e7e4e8e5e6e1e2e3v1v2v4

6、v5 圖中某些點(diǎn)和邊的交替序列，若其圖中某些點(diǎn)和邊的交替序列，若其中各邊互不相同，且對(duì)任意中各邊互不相同，且對(duì)任意Vi-1,Vi 和和vi+1均相鄰稱為均相鄰稱為鏈鏈。用。用表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5,110kkvevev 起點(diǎn)與終點(diǎn)重合的鏈稱作起點(diǎn)與終點(diǎn)重合的鏈稱作圈圈。如。如果每一對(duì)頂點(diǎn)之間至少存在一條果每一對(duì)頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為鏈，稱這樣的圖為連通圖連通圖，否則，否則稱稱圖不連通圖不連通。 ）(P232)(P232)設(shè)圖設(shè)圖G（V，E），對(duì)），對(duì)G的每一條邊的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊稱

7、為邊(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)用、通過(guò)能力可以代表距離、費(fèi)用、通過(guò)能力(容量容量)等等。等等。端點(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無(wú)向圖無(wú)向圖：由點(diǎn)和邊構(gòu)成的圖，記作：由點(diǎn)和邊構(gòu)成的圖，記作G=（V，E）。）。有向圖有向圖：由點(diǎn)和弧構(gòu)成的圖，記作：由點(diǎn)和弧構(gòu)成的圖，記作D=（V，A）。）。連通圖連通圖：對(duì)無(wú)向圖：對(duì)無(wú)向圖G，若，若兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則

8、G為連通圖。為連通圖?；芈坊芈罚喝袈返牡谝粋€(gè)點(diǎn)和最后一個(gè)點(diǎn)相同，則該路為回路。：若路的第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)相同，則該路為回路。賦權(quán)圖賦權(quán)圖：對(duì)一個(gè)無(wú)向圖：對(duì)一個(gè)無(wú)向圖G的每一條邊的每一條邊(vi,vj)，相應(yīng)地有一個(gè)數(shù)，相應(yīng)地有一個(gè)數(shù)wij，則稱，則稱圖圖G為賦權(quán)圖，為賦權(quán)圖，wij稱為邊稱為邊(vi,vj)上的權(quán)。上的權(quán)。網(wǎng)絡(luò)網(wǎng)絡(luò)：在：在中指定一點(diǎn)，稱為發(fā)點(diǎn)，指定另一點(diǎn)稱為收點(diǎn)，中指定一點(diǎn)，稱為發(fā)點(diǎn)，指定另一點(diǎn)稱為收點(diǎn)，其它點(diǎn)稱為中間點(diǎn)，并把其它點(diǎn)稱為中間點(diǎn)，并把D中的每一條弧的賦權(quán)數(shù)稱為弧的容量，中的每一條弧的賦權(quán)數(shù)稱為弧的容量，D就就稱為網(wǎng)絡(luò)。稱為網(wǎng)絡(luò)。 如何用最短的線路將三部電話連起來(lái)

9、？如何用最短的線路將三部電話連起來(lái)？ 此問(wèn)題可抽象為設(shè)此問(wèn)題可抽象為設(shè)ABC為等邊三角形，連接三頂點(diǎn)為等邊三角形，連接三頂點(diǎn)的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個(gè)，其中最短路的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個(gè)，其中最短路線者顯然是二邊之和（如線者顯然是二邊之和（如ABAC）。）。ABCABCP 但若增加一個(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ǎng)絡(luò)不僅比原來(lái)節(jié)省材料，而且穩(wěn)定性也更好

10、。而且穩(wěn)定性也更好。 要求：要求：就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路點(diǎn)之間距離最短的一條路 .有些問(wèn)題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投有些問(wèn)題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問(wèn)題，也可以歸結(jié)為求資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問(wèn)題，也可以歸結(jié)為求最短路的問(wèn)題。因此這類問(wèn)題在生產(chǎn)實(shí)際中得到廣泛應(yīng)最短路的問(wèn)題。因此這類問(wèn)題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。用。一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過(guò)河一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過(guò)河到北岸，河上只有一條獨(dú)木舟，每次除了人以外

11、，只能到北岸，河上只有一條獨(dú)木舟，每次除了人以外，只能帶一樣?xùn)|西；另外，如果人不在，狼就要吃羊，羊就要帶一樣?xùn)|西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，問(wèn)應(yīng)該怎樣安排渡河，才能做到既把所有東西吃白菜，問(wèn)應(yīng)該怎樣安排渡河，才能做到既把所有東西都運(yùn)過(guò)河去，并且在河上來(lái)回次數(shù)最少？這個(gè)問(wèn)題就可都運(yùn)過(guò)河去，并且在河上來(lái)回次數(shù)最少？這個(gè)問(wèn)題就可以用求最短路方法解決。以用求最短路方法解決。 1）人）人M（Man），狼），狼W（Wolf），）， 羊羊G（Goat），）， 草草H（Hay） 2） 點(diǎn)點(diǎn) Vi 表示河岸的狀態(tài)表示河岸的狀態(tài) 3） 邊邊 ek 表示由狀態(tài)表示由狀態(tài) vi 經(jīng)一次渡河到狀態(tài)經(jīng)一

12、次渡河到狀態(tài) vj 4） 權(quán)權(quán)邊邊 ek 上的權(quán)定為上的權(quán)定為 1我們可以得到下面的加權(quán)有向圖我們可以得到下面的加權(quán)有向圖： 狀態(tài)說(shuō)明：狀態(tài)說(shuō)明： 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 1 的最短路問(wèn)題。的最短路問(wèn)題。v1v2v3v4v5u5u4u3u2u1 求最短路有兩種算法求最短路有兩種算法: : 狄克斯屈拉狄克斯屈拉(Dijkstra)（雙標(biāo)號(hào)）算法（雙標(biāo)號(hào)）算法 逐次逼近算

13、法逐次逼近算法最短路問(wèn)題：最短路問(wèn)題：對(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的距離。的距離。若序列若序列 vs,v1.vn-1,vn 是從是從vs到到vt間的最短路，則序列間的最短路，則序列 vs,v1.vn-1 必為從必為從vs 到到vn-1的最短路。的最短路。假定假定v1v2 v3

14、v4是是v1 v4的最短路，則的最短路，則v1 v2 v3一定是一定是v1 v3的最短路，的最短路，v2 v3 v4也一定是也一定是v2 v4的的最短路。最短路。v1v2v3v4v51.給出點(diǎn)V1以標(biāo)號(hào)(0,s)2.找出已標(biāo)號(hào)的點(diǎn)的集合I，沒(méi)標(biāo)號(hào)的點(diǎn)的集合J以及弧的集合3. 如果上述弧的集合是空集，則計(jì)算結(jié)束。如果vt已標(biāo)號(hào)（lt,kt），則 vs到vt的距離為lt，而從 vs到vt的最短路徑，則可以從kt 反向追蹤到起點(diǎn)vs 而得到。如果vt 未標(biāo)號(hào)，則可以斷言不存在從 vs到vt的有向路。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。4. 對(duì)上述弧的集合中的每一條弧，計(jì)算 sij=li+cij

15、。在所有的 sij中，找到其值為最小的弧。不妨設(shè)此弧為（Vc,Vd），則給此弧的終點(diǎn)以雙標(biāo)號(hào)（scd,c）,返回步驟2。( ,)|,ijijv vvI vJ(P233)例例1 求下圖中求下圖中v1到到v6的最短路的最短路解：采用解：采用Dijkstra算法，可解得最短路徑為算法，可解得最短路徑為v1 v3 v4 v6 各點(diǎn)的標(biāo)號(hào)圖如下：各點(diǎn)的標(biāo)號(hào)圖如下：v23527531512v1v6v5v3v4(3,1)v23527531512 V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4( P234) 例例2 電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問(wèn)如何架設(shè)使電信公司準(zhǔn)備在甲、乙兩地

16、沿路架設(shè)一條光纜線，問(wèn)如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長(zhǎng)度（單位：公里）。的長(zhǎng)度（單位：公里）。 解：這是一個(gè)求無(wú)向圖的最短路的問(wèn)題?？梢园褵o(wú)向圖的每一邊解：這是一個(gè)求無(wú)向圖的最短路的問(wèn)題?？梢园褵o(wú)向圖的每一邊（vi,vj）都用方向相反的兩條?。ǎ┒加梅较蛳喾吹膬蓷l?。╲i,vj）和（）和（vj,vi）代替，就化為有向圖，）代替，就化為有向圖，即可用即可用Dijkstra算法來(lái)求解。也可直接在無(wú)向圖中用算法來(lái)求解。也可直接在無(wú)向圖中用Dijkstra算法來(lái)求解。算法來(lái)求解。只要在算法中把

17、從已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)的弧的集合改成已標(biāo)號(hào)的點(diǎn)到只要在算法中把從已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)的弧的集合改成已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)的邊的集合即可。未標(biāo)號(hào)的點(diǎn)的邊的集合即可。 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 設(shè)備更新問(wèn)題。某公司使用一臺(tái)設(shè)備，在每年年初，公司就要設(shè)備更新問(wèn)題。某公司使用一臺(tái)設(shè)備，在每年年初，公司就要決定是購(gòu)買新的設(shè)備還是繼續(xù)使用舊設(shè)

18、備。如果購(gòu)置新設(shè)備，就要支付一決定是購(gòu)買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購(gòu)置新設(shè)備，就要支付一定的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省定的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購(gòu)置費(fèi)，但維修費(fèi)用就高了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，去購(gòu)置費(fèi)，但維修費(fèi)用就高了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。使得五年內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。 已知：設(shè)備每年年初的價(jià)格表已知：設(shè)備每年年初的價(jià)格表 設(shè)備維修費(fèi)如下表設(shè)備維修費(fèi)如下表年份年份12345年初價(jià)格年初價(jià)格1111121213使用年數(shù)使用年數(shù)

19、0-11-22-33-44-5每年維修每年維修費(fèi)用費(fèi)用5681118例例3的解：的解： 將問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，如下圖：將問(wèn)題轉(zhuǎn)化為最短路問(wèn)題，如下圖： 用用vi表示表示“第第i年年初購(gòu)進(jìn)一臺(tái)新設(shè)備年年初購(gòu)進(jìn)一臺(tái)新設(shè)備”,?。ɑ。╲i,vj）表示第）表示第i年年初購(gòu)進(jìn)年年初購(gòu)進(jìn)的的設(shè)備一直使用到第設(shè)備一直使用到第j年年初。年年初。把所有弧的權(quán)數(shù)計(jì)算如下表：把所有弧的權(quán)數(shù)計(jì)算如下表：v1v2v3v4v5v6123456116223041592162230413172331417235186 (繼上頁(yè)繼上頁(yè)) 把權(quán)數(shù)賦到圖中，再用把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。算法求最短路。 最

20、終得到下圖，可知，最終得到下圖，可知，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) 課堂練習(xí)：課堂練習(xí)：1. 用用Dijkstra算法求下圖從算法求下圖從v1到到v6的最短距離及路線。的最短距離及路線。v3v54v1v2v4v635222421v1到到v6的最短路為：的最短路為：65

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

22、適用于全部權(quán)為非負(fù)情況，如果某邊上權(quán)為負(fù)的，算法失效。此時(shí)可采用逐次某邊上權(quán)為負(fù)的，算法失效。此時(shí)可采用逐次逼近算法。逼近算法。 例例6.7 如右圖所示中按如右圖所示中按dijkstra算法可得算法可得P(v1)=5為從為從vsv1的的最短路長(zhǎng)顯然是錯(cuò)誤的，從最短路長(zhǎng)顯然是錯(cuò)誤的，從vsv2v1路長(zhǎng)只有路長(zhǎng)只有3。v2vsv15-58 樹(shù)是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)樹(shù)是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)域應(yīng)用極為廣泛。領(lǐng)域應(yīng)用極為廣泛。 例例6.2 乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。如下圖所示。

23、AB CDEF GH運(yùn)動(dòng)員運(yùn)動(dòng)員 例例 某企業(yè)的組織機(jī)構(gòu)圖也可用樹(shù)圖表示。某企業(yè)的組織機(jī)構(gòu)圖也可用樹(shù)圖表示。廠長(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)開(kāi)發(fā)科開(kāi)發(fā)科技術(shù)科技術(shù)科生產(chǎn)科生產(chǎn)科設(shè)備科設(shè)備科供應(yīng)科供應(yīng)科銷售科銷售科檢驗(yàn)科檢驗(yàn)科動(dòng)力科動(dòng)力科任何樹(shù)中必存在次為任何樹(shù)中必存在次為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)的樹(shù)必有個(gè)頂點(diǎn)的樹(shù)必有n-1 條邊。條邊。樹(shù)中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。樹(shù)中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。樹(shù)連通，但去掉任一條邊，必變?yōu)椴贿B通。樹(shù)連通，但去

24、掉任一條邊，必變?yōu)椴贿B通。樹(shù)無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰樹(shù)無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)圈。得到一個(gè)圈。v1v2v3v4v5v6 樹(shù)是圖論中的重要概念，所謂樹(shù)就是一個(gè)無(wú)圈的連通圖。樹(shù)是圖論中的重要概念，所謂樹(shù)就是一個(gè)無(wú)圈的連通圖。 圖圖11-11中，中，(a)就是一個(gè)樹(shù)，而就是一個(gè)樹(shù)，而(b)因?yàn)閳D中有圈所以就不因?yàn)閳D中有圈所以就不是樹(shù)，是樹(shù)， (c)因?yàn)椴贿B通所以也不是樹(shù)。因?yàn)椴贿B通所以也不是樹(shù)。圖圖11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c) 如果如果G2是是G1的部分圖，

25、又是樹(shù)圖，則稱的部分圖，又是樹(shù)圖，則稱G2是是G1的部分樹(shù)的部分樹(shù)（或支撐樹(shù)）。樹(shù)圖的各條邊稱為樹(shù)枝，一般圖（或支撐樹(shù)）。樹(shù)圖的各條邊稱為樹(shù)枝，一般圖G1含有多含有多個(gè)部分樹(shù)，其中樹(shù)枝總長(zhǎng)最小的部分樹(shù)，稱為該圖的最小個(gè)部分樹(shù)，其中樹(shù)枝總長(zhǎng)最小的部分樹(shù)，稱為該圖的最小部分樹(shù)（或最小支撐樹(shù)）。部分樹(shù)（或最小支撐樹(shù)）。v1v2v3v4v5v1v2v3v4v5G1G2 給了一個(gè)無(wú)向圖給了一個(gè)無(wú)向圖G=(V,E)，我們保留，我們保留G的所有點(diǎn)，而刪掉部分的所有點(diǎn)，而刪掉部分G的邊或者的邊或者說(shuō)保留一部分說(shuō)保留一部分G的邊，所獲得的圖的邊，所獲得的圖G，稱之為，稱之為G的生成子圖。在圖的生成子圖。在圖11

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

27、v2v5：任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521邊數(shù)邊數(shù)n-1=5v1v2v3v4v5v643521得到最小樹(shù)得到最小樹(shù)：Min C(T)=15去掉去掉G中所有邊，得到中所有邊，得到n個(gè)孤立點(diǎn)；然后加邊。個(gè)孤立點(diǎn)；然后加邊。加邊的原則為：從最短邊開(kāi)始添加，加邊的過(guò)程中不能加邊的原則為：從最短邊開(kāi)始添加，加邊的過(guò)程中不能形成圈，直到點(diǎn)點(diǎn)連通形成圈，直到點(diǎn)點(diǎn)連通(即即:n-1條邊條邊)。5v1v2v3v4v5v6843752618v1v2v3v4v5v6435215v1v2v3v4v5v

28、6843752618Min C(T)=153749346321Min C(T)=12Min C(T)=15254173314475答案：34122323242Min C(T)=12213638534567454321Min C(T)=18 例例5、某大學(xué)準(zhǔn)備對(duì)其所屬的、某大學(xué)準(zhǔn)備對(duì)其所屬的7個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，這個(gè)網(wǎng)絡(luò)的可個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑如下圖，圖中能聯(lián)通的途徑如下圖，圖中v1,v7 表示表示7個(gè)學(xué)院辦公室，請(qǐng)?jiān)O(shè)計(jì)一個(gè)網(wǎng)個(gè)學(xué)院辦公室，請(qǐng)?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)能聯(lián)通絡(luò)能聯(lián)通7個(gè)學(xué)院辦公室，并使總的線路長(zhǎng)度為最短。個(gè)學(xué)院辦公室，并使總的線路長(zhǎng)度為最短。 解：此問(wèn)題實(shí)際上是

29、求圖解：此問(wèn)題實(shí)際上是求圖11-1411-14的最小生成樹(shù)，這在例的最小生成樹(shù)，這在例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é)軟件”有專門(mén)的子程序可以解決最小生成樹(shù)問(wèn)題。有專門(mén)的子程序可以解決最小生成樹(shù)問(wèn)題。v1331728541034v7v6v5v4v2v3圖圖11-14 如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問(wèn)題。這就是一個(gè)網(wǎng)

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

31、的實(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)絡(luò)中從st的流量，則有：的流量，則有： 0),(),()(tjjsvvfvvffv結(jié)論結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）可行流

32、）網(wǎng)絡(luò)最大流問(wèn)題：網(wǎng)絡(luò)最大流問(wèn)題：指滿足容量限制條件和中間點(diǎn)平衡的條件下，使指滿足容量限制條件和中間點(diǎn)平衡的條件下，使v(f)v(f)值達(dá)到最大。值達(dá)到最大。一、最大流的數(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ò)的一部分如下圖所示。由于管道的直徑運(yùn)送到一些銷售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一部分如下圖所示。由于管道的直徑的變化，它的各段管道（的變化，它的各段管道（vi,vj）的流量）的流量cij（容量）也是不一樣的。（容量）也是不一樣的。cij的的單位為萬(wàn)加侖單位為萬(wàn)加侖/小時(shí)

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

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

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

36、以下的結(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)值（最大流量）（最大流量）=10=10。二、最大流問(wèn)題網(wǎng)絡(luò)圖論的解法二、最大流問(wèn)題網(wǎng)絡(luò)圖論的解法 對(duì)網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。為省去弧的方向，如下圖對(duì)網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。為省去弧的方向，如下圖: (a)和和(b)、(c)和和(d)的意義相同。的意義相同。 用以上方法對(duì)例用以上方法

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

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

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

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

41、路，路上的每一條弧順流容量都大于零，運(yùn)算停止。得到最大流量為每一條弧順流容量都大于零，運(yùn)算停止。得到最大流量為10。 最大流量圖如下圖：最大流量圖如下圖：22v1v2v5v7v4v3v6123522355 “管理運(yùn)籌學(xué)軟件管理運(yùn)籌學(xué)軟件”中還有專門(mén)的子程序用于解決最大流問(wèn)題。中還有專門(mén)的子程序用于解決最大流問(wèn)題。 最小費(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外，外，還給出了這條弧的單位流量的費(fèi)用還給出了這條弧的單位流量的費(fèi)用bij，要，要求一個(gè)最大流求一個(gè)最大流F，并使得總運(yùn)送費(fèi)用

42、最小。，并使得總運(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向銷地向銷地 v7運(yùn)送石運(yùn)送石油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最?。壳蟪鲎畲罅饔?，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最??？求出最大

43、流量和最小費(fèi)用。量和最小費(fèi)用。(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 vAfb 這個(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中建中建立了線性規(guī)劃的模型，通過(guò)管理運(yùn)籌學(xué)軟件已經(jīng)獲得結(jié)果。立了線性規(guī)劃的模型，通過(guò)管理運(yùn)籌學(xué)軟件已經(jīng)獲得結(jié)果。 第二步，

44、在最大流量第二步，在最大流量F的所有解中，找出一個(gè)最小費(fèi)用的的所有解中，找出一個(gè)最小費(fèi)用的解，我們來(lái)建立第二步中的線性規(guī)劃模型如下：解，我們來(lái)建立第二步中的線性規(guī)劃模型如下： 仍然設(shè)弧（仍然設(shè)?。╲i,vj）上的流量為）上的流量為fij，這時(shí)已知中最大流量為，這時(shí)已知中最大流量為F，只要在例只要在例6的約束條件上，再加上總流量必須等于的約束條件上，再加上總流量必須等于F的約束條件：的約束條件：f12=f14=F,即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標(biāo)函數(shù)即得此線性規(guī)劃的約束條件，此線性規(guī)劃的目標(biāo)函數(shù)顯然是求其流量的最小費(fèi)用顯然是求其流量的最小費(fèi)用 fij . bij 。 由此得到線性規(guī)劃模

45、型如下：由此得到線性規(guī)劃模型如下： 1214252343(,)355736464767121412232514434647234335362535573646675767471214min63452473384. .10,(1,2,6;ijijijv vAijijfbfffffffffffstffFfffffffffffffffffffffffcij2,3,7),0,(1,2,6;2,3,7),ijfij 用管理運(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=

46、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)題改為：每小時(shí)運(yùn)送6 6萬(wàn)加侖的石油萬(wàn)加侖的石油從采地從采地v v1 1到銷地到銷地v v7 7最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了一個(gè)最小費(fèi)用流的問(wèn)題。一般來(lái)說(shuō)，所謂

47、最小費(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改

48、為改為f f即可。在例即可。在例6 6中只要把中只要把f f1212+f+f1414=F=F改為改為f f1212+f+f1414=f=6=f=6得到了最小費(fèi)用流的線性規(guī)劃的模型得到了最小費(fèi)用流的線性規(guī)劃的模型了。了。二、最小費(fèi)用最大流的網(wǎng)絡(luò)圖論解法二、最小費(fèi)用最大流的網(wǎng)絡(luò)圖論解法對(duì)網(wǎng)絡(luò)上?。▽?duì)網(wǎng)絡(luò)上?。╲i,vj）的（）的（cij,bij）的表示作如下改動(dòng)，用）的表示作如下改動(dòng)，用(b)來(lái)表示來(lái)表示(a)。用上述方法對(duì)例用上述方法對(duì)例7中的圖形進(jìn)行改進(jìn)，得圖如下頁(yè)：中的圖形進(jìn)行改進(jìn)，得圖如下頁(yè)：vivjvivj（cij,bij ）（0,-bij ）（a）（b）（cij,bij ）（cij,b

49、ij ）vivj（cji,bji ）（cij,bij ）vivj（cji,bji ）（0,-bji)（0,-bji)（c）（d） 求最小費(fèi)用最大流的基本算法求最小費(fèi)用最大流的基本算法 在對(duì)弧的標(biāo)號(hào)作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費(fèi)用最大流的基本算法與求在對(duì)弧的標(biāo)號(hào)作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費(fèi)用最大流的基本算法與求最大流的基本算法完全一樣，不同的只是在步驟（最大流的基本算法完全一樣，不同的只是在步驟（1）中要選擇一條總的）中要選擇一條總的單位費(fèi)用最小的路，而不是包含邊數(shù)最小的路。單位費(fèi)用最小的路，而不是包含邊數(shù)最小的路。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2

50、,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用上述方法對(duì)例用上述方法對(duì)例7求解：求解： 第一次迭代：找到最短路第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后總流量為第一次迭代后總流量為1，總，總費(fèi)用費(fèi)用10。v5(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-2911-29第二次迭代：找到最短路第二次迭代：找到最短路v1 v4 v7。第二次迭代后總流量為第二次迭代后總流量為3，總費(fèi)，總費(fèi)用用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(