指導(dǎo)chap7圖論與網(wǎng)絡(luò)優(yōu)化模型

1、第七章 圖論與網(wǎng)絡(luò)優(yōu)化模型 7.1 圖論基本概念與最小生成樹7.2 最短路問題7.3 網(wǎng)絡(luò)最大流7.4 二分圖與鎖具裝箱問題y實(shí)際背景 例1（公路連接問題）某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來，使得從其中一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市。假定已經(jīng)知道了任意兩個(gè)城市之間修建高速公路的成本，那么如何決定在哪些城市間修建高速公路總成本最?。坷?（最短路問題）一名貨車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨車的運(yùn)行速度是恒定的，那么這個(gè)問題相當(dāng)于需要找到一條從甲地到乙地的

2、最短路。例3（運(yùn)輸問題）某種原材料有m個(gè)產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往n個(gè)使用工廠。假定m個(gè)產(chǎn)地的產(chǎn)量和n個(gè)工廠的需求量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么，如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？實(shí)際背景 例4（指派問題）一家公司經(jīng)理準(zhǔn)備安排n名員工去完成n項(xiàng)任務(wù)，每人一項(xiàng)。由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的收益不同，如何分配工作方案使總回報(bào)最大？例5（中國郵遞員問題）一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他設(shè)計(jì)一條最短的投遞路線？即從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局。例6（旅行商問題）一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他設(shè)

3、計(jì)一條最短的旅行路線？即從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地。實(shí)際背景 共同特點(diǎn)：（1）它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為優(yōu)化問題。（2）它們都易于用圖形的形式直觀的描述和表達(dá)，數(shù)學(xué)上把這種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡(luò)，與圖和網(wǎng)絡(luò)相關(guān)的優(yōu)化問題稱為網(wǎng)絡(luò)優(yōu)化。哥尼斯堡七橋問題 在無孤立結(jié)點(diǎn)的圖g中,若存在一條回路,它經(jīng)過圖中每條邊一次且僅一次,稱此回路為歐拉回路. 無向圖g具有歐拉回路,當(dāng)且僅當(dāng)g是連通的,且所有結(jié)點(diǎn)的度都是偶數(shù).圖論基本概念與最小生成樹一、 圖 的 概 念1、圖的定義2、頂點(diǎn)的次數(shù) 3、子圖二、 圖 的 矩 陣 表 示

4、1、 關(guān)聯(lián)矩陣2、 鄰接矩陣三、 最 小 生 成 樹定義有序二元組g=(v,e )稱為一個(gè)圖.1 是有窮非空集，稱為頂點(diǎn)集 其中的元素叫圖g的頂點(diǎn)。2 e稱為邊集，其中的元素稱為圖g的邊。 例設(shè)g=(v,e),其中g(shù)的圖解如圖12,nvv vv123412345,vv v v vee e e e e定義定義在圖 g 中，與 v 中的有序偶(vi， vj)對(duì)應(yīng)的邊 e，稱為圖的有有向向邊邊（或?。?，而與 v 中頂點(diǎn)的無序偶 vivj相對(duì)應(yīng)的邊 e，稱為圖的無無向向邊邊.每一條邊都是無向邊的圖，叫無無向向圖圖；每一條邊都是有向邊的圖，稱為有有向向圖圖；既有無向邊又有有向邊的圖稱為混混合合圖圖.定

5、義定義若將圖 g 的每一條邊 e 都對(duì)應(yīng)一個(gè)實(shí)數(shù) w(e)，稱 w(e)為邊的權(quán)權(quán)，并稱圖 g 為賦賦權(quán)權(quán)圖圖.規(guī)定用記號(hào)和分別表示圖的頂點(diǎn)數(shù)和邊數(shù).關(guān)聯(lián)矩陣對(duì)無向圖，其關(guān)聯(lián)矩陣)(ijm，其中：不關(guān)聯(lián)與若相關(guān)聯(lián)與若jijiijevevm01m=43215432110110011000101110001vvvveeeee對(duì)有向圖，其關(guān)聯(lián)矩陣)(ijm，其中：不關(guān)聯(lián)與若的終點(diǎn)是若的起點(diǎn)是若jijijiijevevevm011注：假設(shè)圖為簡單圖鄰接矩陣對(duì)無向圖，其鄰接矩陣)(ijaa，其中：不相鄰與若相鄰與若jijiijvvvva01注：假設(shè)圖為簡單圖a=432143210111101011011

6、010vvvvvvvv對(duì)有向圖（，） ，其鄰接矩陣)(ijaa，其中：evvevvajijiij），若（），若（01對(duì)有向賦權(quán)圖，其鄰接矩陣)(ijaa，其中：evvjiwevvwajiijjiijij),(0,),(若若為其權(quán)且若無向賦權(quán)圖的鄰接矩陣可類似定義a=4321432105375083802720vvvvvvvv樹的等價(jià)定義樹的等價(jià)定義無回路的連通圖無回路的連通圖.無回路且無回路且=v-1 其中其中是是t的邊數(shù)的邊數(shù),v是是t的結(jié)點(diǎn)數(shù)的結(jié)點(diǎn)數(shù).連通的且連通的且=v-1.無回路但添加一條新邊則得到一條僅有的回路無回路但添加一條新邊則得到一條僅有的回路.連通的連通的,但刪去任一條邊但刪

7、去任一條邊,t便不連通便不連通.每對(duì)結(jié)點(diǎn)之間有一條且僅有一條路每對(duì)結(jié)點(diǎn)之間有一條且僅有一條路. 如果圖如果圖g的生成子圖是樹的生成子圖是樹, 則稱此樹為則稱此樹為g的的生成樹生成樹.例：某地要建例：某地要建5個(gè)工廠，擬修筑道路連接這個(gè)工廠，擬修筑道路連接這5處。經(jīng)勘測處。經(jīng)勘測其道路可依下圖的無向邊鋪設(shè)。為使這其道路可依下圖的無向邊鋪設(shè)。為使這5處都有道路處都有道路相通，問至少要鋪設(shè)幾條路？怎樣鋪設(shè)？相通，問至少要鋪設(shè)幾條路？怎樣鋪設(shè)？v1v4v5v2v3v1v4v5v2v3v1v4v5v2v3最小生成樹（最小生成樹（kruskal（克魯斯克爾）算法）（克魯斯克爾）算法） 設(shè)圖設(shè)圖g有有n個(gè)結(jié)

8、點(diǎn)，以下算法產(chǎn)生的是最小生成樹個(gè)結(jié)點(diǎn)，以下算法產(chǎn)生的是最小生成樹1）選取最小權(quán)邊）選取最小權(quán)邊e1，置邊數(shù)，置邊數(shù)i1；2）i=n-1結(jié)束，否則轉(zhuǎn)入結(jié)束，否則轉(zhuǎn)入3）；）；3）設(shè)已選擇邊為）設(shè)已選擇邊為e1,e2,ei, 在在g中選取不同于中選取不同于e1,e2,ei的邊的邊ei+1，使，使e1,e2,ei,ei+1中無回路且中無回路且ei+1是滿足此條件的最小邊；是滿足此條件的最小邊；4） ii1,轉(zhuǎn)入轉(zhuǎn)入2）。）。注意：最小生成樹不唯一，但不同的最小生成樹的邊權(quán)之和是唯一的邊按升序排序邊按升序排序:邊邊(vi, vj)記成記成eij邊權(quán)邊權(quán)e28e34e23e38e17e24e45e57e

9、16e78e56e35e46e67e58e12e181 1 2 2 2 3 3 3 4 4 4 5 6 6 7 7 8v1 v5 v4v2 v3v8 v6v7 12213772486653443v1 v5 v4v2 v3v8 v6v7 1212433 to mtlb(kruskl.m)驗(yàn)證：p95例11最短路問題及其算法一、基本概念二、固定起點(diǎn)的最短路三、每對(duì)頂點(diǎn)之間的最短路基 本 概 念通路44112544141vevevevevwvv道路4332264521141vevevevevevtvv路徑4521141vevevpvv定義定義（）任意兩點(diǎn)均有路徑的圖稱為連通圖連通圖（）起點(diǎn)與終點(diǎn)重合

10、的路徑稱為圈圈（）連通而無圈的圖稱為樹樹定定義義（）設(shè) p(u,v)是賦權(quán)圖 g 中從 u 到 v的路徑， 則稱)()()(peeewpw為路徑 p 的權(quán)權(quán)(2) 在賦權(quán)圖 g 中，從頂點(diǎn) u 到頂點(diǎn) v的具有最小權(quán)的路 ),(*vup，稱為 u 到 v的最最短短路路固定起點(diǎn)的最短路最短路是一條路徑 假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u(píng)0為根的樹 因此, 可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路dijkstra 算法算法：求 g 中從頂點(diǎn) u0到其余頂點(diǎn)的最短路設(shè) g 為賦權(quán)有向圖或無向圖，g 邊上的權(quán)均非負(fù)對(duì)每個(gè)頂點(diǎn)，定義兩個(gè)標(biāo)記（l v( )

11、，z v( )） ，其中: l v( )：表從頂點(diǎn) u0到 v 的一條路的權(quán) z v( )：v 的父親點(diǎn)，用以確定最短路的路線算法的過程就是在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終l v( )為從頂點(diǎn)u0到 v 的最短路的權(quán)s：具有永久標(biāo)號(hào)的頂點(diǎn)集輸入: g 的帶權(quán)鄰接矩陣),(vuw算法步驟：（3） 設(shè)v*是使l v( )取最小值的s中的頂點(diǎn)，則令 s=sv*， uv*（4） 若s ，轉(zhuǎn) 2，否則，停止.（2）更新l v( )、z v( )： vsvs,若l v( )l uw u v( )( , ) 則令l v( )=l uw u v( )( , ),z v( )= u例例 求下圖從頂點(diǎn) u1到其余頂

12、點(diǎn)的最短路先寫出帶權(quán)鄰接矩陣： 03064093021509701608120w因 g 是無向圖，故 w是對(duì)稱陣 to mtlb(dijkstr.m)(iul迭代次數(shù)1u2u3u 4u5u6u 7u 8u2345678 0 2 8 10 8 3 10 8 6 10 12 7 1012 9 12 12最后標(biāo)記:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5u)(iul1u2u3u 4u5u6u 7u 8u最后標(biāo)記:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5uu1u2u3u4u5u6u7u8驗(yàn)證

13、：p97例1每對(duì)頂點(diǎn)之間的最短路1、求距離矩陣的方法2、求路徑矩陣的方法3、查找最短路路徑的方法（一）算法的基本思想（二）算法原理（三）算法步驟算法的基本思想 直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次構(gòu)造出個(gè)矩陣 d(1)、 d(2)、 、d()，使最后得到的矩陣 d()成為圖的距離矩陣，同時(shí)也求出插入點(diǎn)矩陣以便得到兩點(diǎn)間的最短路徑算法原理 求距離矩陣的方法把帶權(quán)鄰接矩陣 w 作為距離矩陣的初值，即 d(0)=)()0(ijd=w（）d(1)= )() 1 (ijd，其中)0(1)0() 1 (,miniijijddd)0(1jd)1(ijd是從 vi到 vj的只允許以 v1作為中間點(diǎn)的路

14、徑中最短路的長度（2）d(2)= )()2(ijd，其中) 1 (2) 1 ()2(,miniijijddd)1 (2 jd )2(ijd是從 vi到 vj的只允許以 v1 、 v2作為中間點(diǎn)的路徑中最短路的長度（）d()=)()(ijd，其中)1()1()(,miniijijddd)1( jd)(ijd是從 vi到 vj的只允許以 v1、v2、v作為中間點(diǎn)的路徑中最短路的長度即是從 vi到 vj中間可插入任何頂點(diǎn)的路徑中最短路的長，因此d()即是距離矩陣算法原理 求路徑矩陣的方法r=)(ijr, rij的含義是從 vi到 vj的最短路要經(jīng)過點(diǎn)號(hào)為 rij的點(diǎn))()0()0(ijrr, jri

15、j)0(每求得一個(gè) d(k)時(shí)，按下列方式產(chǎn)生相應(yīng)的新的 r(k)否則若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距離矩陣的同時(shí)可建立路徑矩陣r 即當(dāng)vk被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在r(k)中，依次求 時(shí)求得 ，可由 來查找任何點(diǎn)對(duì)之間最短路的路徑)(d)(r)(rij算法原理查找最短路路徑的方法若1)(prij，則點(diǎn) p1是點(diǎn) i 到點(diǎn) j 的最短路的中間點(diǎn).然后用同樣的方法再分頭查找若：（） 向點(diǎn) i 追朔得：2)(1prip,3)(2prip,kipprk)(（） 向點(diǎn) j 追朔得：1)(1qrjp,2)(1qrjq,jrjqm)(pkp2p1

16、p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：jqqqpppimk,21, 12算法步驟floyd 算法：算法：求任意兩點(diǎn)間的最短路d(i,j)：i 到 j 的距離r(i,j)：i 到 j 之間的插入點(diǎn)輸入: 帶權(quán)鄰接矩陣 w(i,j)（） 賦初值：對(duì)所有 i,j, d(i,j)w(i,j), r(i,j)j, k1(2) 更新 d(i,j), r(i,j)對(duì)所有 i,j，若 d(i,k)+d(k,j)d(i,j)，則 d(i,j)d(i,k)+d(k,j), r(i,j)k(3) 若 k=，停止否則 kk+1，轉(zhuǎn)（） 例、求下圖任意兩點(diǎn)之間的最短路徑的長度654321654321654321

17、654321654321654321r,022203230142221034301210d例例 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑 to mtlb(rod2(floyd)5333434331543243332344441,0646960243420256420793570rd951d，故從 v5到 v1的最短路為51r由 v4向 v5追朔：3, 35354rr;由 v4向 v1追朔：141r所以從 v5到 v1的最短路徑為：1435.可化為最短路問題的多階段決策問題最短路的應(yīng)用（2）弧集 e=(,)v vij，i=1,2,3,4,5; ij6,弧(,)v vij表第 i 年初購進(jìn)一臺(tái)設(shè)備一

18、直使用到第 j 年初的決策，其權(quán) w(,)v vij表由這一決策在第 i 年初到第 j 年初的總費(fèi)用，如w(,)v v14=11+5+6+8=30.（2） 計(jì)算在各點(diǎn)iv設(shè)立服務(wù)設(shè)施的最大服務(wù)距離)(ivs max)(1ijjidvs , 2 , 1i 選址問題-中心問題例例 2某城市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如圖所示問應(yīng)設(shè)在那個(gè)區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短（1）用 floyd 算法求出距離矩陣 d=)(ijd（3）求出頂點(diǎn)kv，使)(min)(1iikvsvs則kv就是要求的建立消防站的地點(diǎn)此點(diǎn)稱為圖的中心點(diǎn)中心點(diǎn) to mtlb(rod3(floyd)05 .15 .55

19、 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .42502545 .24720375 .5710530ds(v1)=10, s(v2)=7, s(v3)=6, s(v4)=8.5, s(v5)=7, s(v6)=7, s(v7)=8.5s(v3)=6,故應(yīng)將消防站設(shè)在v3處。 7.3 7.3 網(wǎng)絡(luò)流問題網(wǎng)絡(luò)流問題 1、 網(wǎng)絡(luò)流圖2 、最大流問題及其解法3 、最小費(fèi)用問題及其解法問題1：7種設(shè)備要用5架飛機(jī)運(yùn)往目的地，每種設(shè)備各有4臺(tái)，這5架飛機(jī)的容量分別為8，8，5，4，4臺(tái)，問能否有一種裝載法，使同一種類型的設(shè)備不會(huì)有兩臺(tái)在同一架飛機(jī)上。問

20、題2：設(shè)有王二、張三、李四、趙五四人及小提琴、大提琴、鋼琴和吉他四種樂器，已知四人的特長如下： 王二擅長拉大提琴和彈鋼琴； 張三擅長拉小提琴、大提琴和吉他； 李四擅長拉小提琴和大提琴； 趙五只會(huì)彈吉他；今假設(shè)四人同臺(tái)演出，每人奏一種樂器，問四人同時(shí)各演奏一種樂器時(shí)所有可能的方案。網(wǎng)絡(luò)流圖是滿足下列條件的有向賦權(quán)圖網(wǎng)絡(luò)流圖是滿足下列條件的有向賦權(quán)圖),(wevg （1 1）有一個(gè)發(fā)點(diǎn)）有一個(gè)發(fā)點(diǎn) 和收點(diǎn)和收點(diǎn)（2 2）每條邊都有一個(gè)容量（權(quán)）每條邊都有一個(gè)容量（權(quán)）ss),(jivvw 實(shí)際含義是發(fā)點(diǎn)可以看作運(yùn)輸問題的起點(diǎn)，收點(diǎn)可以看作運(yùn)實(shí)際含義是發(fā)點(diǎn)可以看作運(yùn)輸問題的起點(diǎn)，收點(diǎn)可以看作運(yùn)輸問題

21、的終點(diǎn)，邊可以看作運(yùn)輸路線，權(quán)數(shù)可以看作該線路的輸問題的終點(diǎn)，邊可以看作運(yùn)輸路線，權(quán)數(shù)可以看作該線路的運(yùn)輸能力。運(yùn)輸能力。 設(shè)設(shè) 是定義在有向賦權(quán)圖是定義在有向賦權(quán)圖 邊集邊集 上的上的一個(gè)數(shù)值函數(shù)，滿足：一個(gè)數(shù)值函數(shù)，滿足：),(jivvf),(wevg e（2）除過發(fā)點(diǎn)和起點(diǎn)外，),(),( , ),(),(xvvyvyfxvfiiyixi和的邊。和離開分別是進(jìn)入iivv),(),(jijivvwvvf（1 1）一、網(wǎng)絡(luò)流圖的流。是則稱),(),(. 0),(),(wevgvvfqysfsxfjiyx該定義的實(shí)際意義分別為：1、每條邊的實(shí)際流量不超過它的容量。2、流入和流出每個(gè)節(jié)點(diǎn)的流量相

22、等。（物質(zhì)不滅，無損耗）3、從發(fā)點(diǎn)流出的流量等于流入收點(diǎn)的流量。稱 的流值。為流)(),(),()(,jiyxvvfsyfxsffq3、二、最大流問題及其求解方法 （一）最大流問題最大流問題 設(shè)有向網(wǎng)絡(luò)n（v，），在發(fā)點(diǎn)vs 有一批貨，要通過網(wǎng)絡(luò)上的弧運(yùn)輸?shù)绞拯c(diǎn)vt 去，受運(yùn)輸條件限制，每條弧ij在單位時(shí)間內(nèi)通過的車輛數(shù)不能超過cij 輛，分析：如何組織運(yùn)輸才能使從vs到vt 在單位時(shí)間內(nèi)通過的車輛達(dá)到最多？ 上面描述的這類問題，稱為最大流問題。 最大流問題廣泛地應(yīng)用在交通運(yùn)輸、供水、油管供油、郵電通訊，也可以用在生產(chǎn)安排，管理優(yōu)化等實(shí)際問題上。例：如圖1中，有一批物資需要用汽車盡快從發(fā)點(diǎn)運(yùn)到

23、收點(diǎn)，?。╥，j）上所標(biāo)的數(shù)字表示該條道路在單位時(shí)間內(nèi)最多能通過的車輛數(shù)（單位：百輛），問如何調(diào)運(yùn)，才能使單位時(shí)間里有最多的車輛從調(diào)到。425136756385577113223圖1 點(diǎn)出發(fā)的車輛數(shù)應(yīng)該與點(diǎn)到達(dá)的車輛數(shù)相同，除和以外的各中間點(diǎn)，進(jìn)的車輛數(shù)應(yīng)該與離去的車輛數(shù)應(yīng)該相同。fxxxxx67571413126765564636575665352546341436353432231325233212xxxxxxxxxxxxxxxxxxxxxxxxij 是通過弧(i，j)的車輛數(shù)。（1）（4）（5）（6）（2）（3） 對(duì)所有?。╥，j），應(yīng)滿足約束 滿足（1）（7）的解稱為從到的一個(gè)可行流，

24、 我們的目的：在所有可行流中求出一個(gè)方案，使得這個(gè)可行流得到的 f 最大。 若從收點(diǎn)到發(fā)點(diǎn)連接一條假想弧(7，1)，設(shè)它的容量c71=，那么 對(duì)點(diǎn)： 對(duì)點(diǎn)： 最大流問題的目標(biāo)為 ijijcx 0（7）14131271xxxx716757xxx（8）（9）（10）max71x所以，對(duì)于發(fā)點(diǎn)為vs，收點(diǎn)為vt的網(wǎng)絡(luò)n（v，u），當(dāng)增加一條約束為cts=的假想弧（t，s）后，最大流問題就成為： 容量約束： 平衡條件： 目標(biāo)函數(shù)： ijijcx 0ujjijuijjixx),(),(maxstx（11）（12）（13）（二）求最大流的方法：弧標(biāo)號(hào)法 盡管最大流問題可以用線性規(guī)劃模型描述，但是我們一般并

25、不用求解線性規(guī)劃的方法求最大流，而是用一種更為簡便明了的圖上作業(yè)法弧標(biāo)號(hào)法，求解上述最大流問題。 為了便于弧標(biāo)號(hào)法的計(jì)算，首先需要將最大流問題（譬如圖1）重新改畫成為圖2的形式。 2416357st650230081023730071000055圖2 在圖在圖2 2中，每條弧中，每條弧 上標(biāo)有兩個(gè)數(shù)字，其中，上標(biāo)有兩個(gè)數(shù)字，其中，靠近點(diǎn)靠近點(diǎn) i 的是的是 ，靠近點(diǎn)，靠近點(diǎn) j j 的是的是 。如。如 表示從表示從到到的最大通過量是的最大通過量是5 5（百輛），從（百輛），從到到的最大通過量是的最大通過量是0 0； 表示從表示從到到和從和從到到都可以通過都可以通過2 2（百輛）；等等。（百輛）

26、；等等。 ijcjic05222416357st650230081023730071000055ijv圖2 求最大流的基本步驟： 弧標(biāo)號(hào)法求最大流的過程，就是對(duì)圖2反復(fù)地進(jìn)行修改的過程，其計(jì)算步驟如下： 步驟1. 從發(fā)點(diǎn)s到收點(diǎn)t選定一條路，使這條路通過的所有弧vij的前面約束量cij都大于0，如果找不到這樣的路，說明已經(jīng)求得最大流，轉(zhuǎn)步驟4。 步驟2. 在選定的路上，找到最小的容許量cij定為p。 步驟3. 對(duì)選定的路上每條弧的容量作以下修改，對(duì)于與路同向的弧，將cij修改為cij-p，對(duì)于與路反向的弧，將cij修改為cij+p。修改完畢后再轉(zhuǎn)入步驟1。步驟4.用原圖中各條弧上起點(diǎn)與終點(diǎn)數(shù)值

27、減去修改后的圖中對(duì)應(yīng)點(diǎn)的數(shù)值，得到正負(fù)號(hào)相反的兩個(gè)數(shù)，并將從正到負(fù)的方向用箭頭表示。這樣，就得到一個(gè)最大流量圖。 下面，我們用弧標(biāo)號(hào)法求解圖2中的最大流。 第一次修改第一次修改：（1）從發(fā)點(diǎn)）從發(fā)點(diǎn)s到收點(diǎn)到收點(diǎn)t找一條路，使得這條路上的找一條路，使得這條路上的所有弧前面的約束量所有弧前面的約束量 。從圖。從圖2 2中可以看出，中可以看出，顯然，顯然，就是滿足這樣的條件的一就是滿足這樣的條件的一條路。條路。 （2）在路中, , , ,所以取 。 0ijc613c736c767c613 cp（3）在路中，修改每一條弧的容量： 066613-pc660031pc660063pc16-7767pc1

28、6-7736pc660076pc通過第1次修改，得到圖3。 2416357st05023008162 3130611600055圖3返回步驟（1），進(jìn)行第2次修改。 第二次修改：選定，在這條路中，由于 ，所以，將 改為2 ， 改為0， 改為5， 、 、 改為3。修改后的圖變?yōu)閳D4。 325 cp12c25c57c21c52c75c2416357st023203051623133611600055返回步驟（1），繼續(xù)做第3次修改。 圖4第三次修改：取，在這條，由于 ，所以將 改為0， 改為5， 改為0， 改為4， 改為1， 改為2， 改為3， 改為5。修改后的圖變?yōu)閳D5。 12c21c23c32

29、c35c53c57c75c2cp122416357st005003231641135611600055圖5返回步驟（1），繼續(xù)做第4次修改。 第四次修改：選定，在這條路中，由于 p =c67 =1，所以將c14改為4,c41改為1,c46改為4,c64改為1,c67改為0，c76 改為7。修改后的圖為變?yōu)閳D6 。 2416357st00500323164 1135701611044圖6返回步驟（1），繼續(xù)做第5次修改。 第五次修改：選定,在這條路中，由于 p = c65 = 1，所以將c14和c46均改為3，c65改為0，c57改為2，c41、c64、c56均改為2，c75改為6。修改后的圖變

30、為圖7。 2416357st005003222641136500622033圖7 需要注意的是，由圖7中可以看出，弧 本來在圖2中是無容量可通過的，但經(jīng)過幾次修改，由 變成 ，即此時(shí)從到還可通過1（百輛），而從到，可以通過6（百輛）的容量，這說明，修改過程實(shí)際上是把計(jì)劃中從到的通過車輛數(shù)減少了。0761(6,3)取，在這條路中，由于p=c35=1，所以將 c14和 c46均改為2，c63改為5, c35改為0，c57改為1，c41、c64、c53均改為3，c36改為2，c75改為7。修改后的圖變?yōu)閳D8。 2416357st005003312640237500533022圖8 在圖8中，從發(fā)點(diǎn)到

31、收點(diǎn)，再也不存在連通的起點(diǎn)容量都大于零的弧了，所以圖8為最大流圖。 轉(zhuǎn)入步驟（4），用原圖中各條弧上起點(diǎn)與終點(diǎn)數(shù)值減去修改后的圖上各點(diǎn)的數(shù)值，將得到正負(fù)號(hào)相反的兩個(gè)數(shù)，將這個(gè)數(shù)標(biāo)在弧上，并將從正到負(fù)的方向用箭頭表示,這樣就得到最大流量圖。例如原來弧 是 ，現(xiàn)在是 ，相減為5，那邊為正，我們就記作 。這樣，就得到圖9，即最大流量。依這樣的調(diào)度方式，可以從發(fā)點(diǎn)s調(diào)運(yùn)14（百輛）汽車到收點(diǎn)t。 07525(3,6)6373371035542513672圖9 最大流量圖 圖10最大流fmx的大小是確定的，但最大流的路線可以不唯一。在上例中，如果從不同的路開始來修改圖，也可能得到另外一個(gè)最大流圖（圖10）。 2416357563233177235注意驗(yàn)證：p104 例2應(yīng)用舉例 一制造商需要把兩個(gè)車間d1,d2生產(chǎn)的同類商品通過運(yùn)輸網(wǎng)絡(luò)送到三個(gè)銷售點(diǎn)m1,m2,m3去，如圖所示。設(shè)各銷售點(diǎn)計(jì)劃銷售量分別為10,8,8，問網(wǎng)絡(luò)的運(yùn)輸能力能否滿足這一要求？兩個(gè)車間生產(chǎn)數(shù)量多少最為恰當(dāng)？三、 最小費(fèi)用