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

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

2、最短路。例3（運(yùn)輸問(wè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（指派問(wèn)題）一家公司經(jīng)理準(zhǔn)備安排n名員工去完成n項(xiàng)任務(wù)，每人一項(xiàng)。由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的收益不同，如何分配工作方案使總回報(bào)最大？例5（中國(guó)郵遞員問(wèn)題）一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他設(shè)計(jì)一條最短的投遞路線？即從郵局出發(fā)，經(jīng)過(guò)投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局。例6（旅行商問(wèn)題）一名推銷(xiāo)員準(zhǔn)備前往若干城市推銷(xiāo)產(chǎn)品。如何為他設(shè)

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

4、1、 關(guān)聯(lián)矩陣2、 鄰接矩陣三、 最 小 生 成 樹(shù)定義有序二元組g=(v,e )稱(chēng)為一個(gè)圖.1 是有窮非空集，稱(chēng)為頂點(diǎn)集 其中的元素叫圖g的頂點(diǎn)。2 e稱(chēng)為邊集，其中的元素稱(chēng)為圖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，稱(chēng)為圖的有有向向邊邊（或弧） ，而與 v 中頂點(diǎn)的無(wú)序偶 vivj相對(duì)應(yīng)的邊 e，稱(chēng)為圖的無(wú)無(wú)向向邊邊.每一條邊都是無(wú)向邊的圖，叫無(wú)無(wú)向向圖圖；每一條邊都是有向邊的圖，稱(chēng)為有有向向圖圖；既有無(wú)向邊又有有向邊的圖稱(chēng)為混混合合圖圖.定

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

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

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

8、點(diǎn)，以下算法產(chǎn)生的是最小生成樹(shù)個(gè)結(jié)點(diǎn)，以下算法產(chǎn)生的是最小生成樹(shù)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中無(wú)回路且中無(wú)回路且ei+1是滿(mǎn)足此條件的最小邊；是滿(mǎn)足此條件的最小邊；4） ii1,轉(zhuǎn)入轉(zhuǎn)入2）。）。注意：最小生成樹(shù)不唯一，但不同的最小生成樹(shù)的邊權(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最短路問(wèn)題及其算法一、基本概念二、固定起點(diǎn)的最短路三、每對(duì)頂點(diǎn)之間的最短路基 本 概 念通路44112544141vevevevevwvv道路4332264521141vevevevevevtvv路徑4521141vevevpvv定義定義（）任意兩點(diǎn)均有路徑的圖稱(chēng)為連通圖連通圖（）起點(diǎn)與終點(diǎn)重合

10、的路徑稱(chēng)為圈圈（）連通而無(wú)圈的圖稱(chēng)為樹(shù)樹(shù)定定義義（）設(shè) p(u,v)是賦權(quán)圖 g 中從 u 到 v的路徑， 則稱(chēng))()()(peeewpw為路徑 p 的權(quán)權(quán)(2) 在賦權(quán)圖 g 中，從頂點(diǎn) u 到頂點(diǎn) v的具有最小權(quán)的路 ),(*vup，稱(chēng)為 u 到 v的最最短短路路固定起點(diǎn)的最短路最短路是一條路徑 假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u(píng)0為根的樹(shù) 因此, 可采用樹(shù)生長(zhǎng)的過(guò)程來(lái)求指定頂點(diǎn)到其余頂點(diǎn)的最短路dijkstra 算法算法：求 g 中從頂點(diǎn) u0到其余頂點(diǎn)的最短路設(shè) g 為賦權(quán)有向圖或無(wú)向圖，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)，用以確定最短路的路線算法的過(guò)程就是在每一步改進(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)的最短路先寫(xiě)出帶權(quán)鄰接矩陣： 03064093021509701608120w因 g 是無(wú)向圖，故 w是對(duì)稱(chēng)陣 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、徑中最短路的長(zhǎng)度（2）d(2)= )()2(ijd，其中) 1 (2) 1 ()2(,miniijijddd)1 (2 jd )2(ijd是從 vi到 vj的只允許以 v1 、 v2作為中間點(diǎn)的路徑中最短路的長(zhǎng)度（）d()=)()(ijd，其中)1()1()(,miniijijddd)1( jd)(ijd是從 vi到 vj的只允許以 v1、v2、v作為中間點(diǎn)的路徑中最短路的長(zhǎng)度即是從 vi到 vj中間可插入任何頂點(diǎn)的路徑中最短路的長(zhǎng)，因此d()即是距離矩陣算法原理 求路徑矩陣的方法r=)(ijr, rij的含義是從 vi到 vj的最短路要經(jīng)過(guò)點(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í)求得 ，可由 來(lái)查找任何點(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)之間的最短路徑的長(zhǎng)度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.可化為最短路問(wèn)題的多階段決策問(wèn)題最短路的應(yīng)用（2）弧集 e=(,)v vij，i=1,2,3,4,5; ij6,弧(,)v vij表第 i 年初購(gòu)進(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 選址問(wèn)題-中心問(wèn)題例例 2某城市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如圖所示問(wèn)應(yīng)設(shè)在那個(gè)區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短（1）用 floyd 算法求出距離矩陣 d=)(ijd（3）求出頂點(diǎn)kv，使)(min)(1iikvsvs則kv就是要求的建立消防站的地點(diǎn)此點(diǎn)稱(chēng)為圖的中心點(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èn)題網(wǎng)絡(luò)流問(wèn)題 1、 網(wǎng)絡(luò)流圖2 、最大流問(wèn)題及其解法3 、最小費(fèi)用問(wèn)題及其解法問(wèn)題1：7種設(shè)備要用5架飛機(jī)運(yùn)往目的地，每種設(shè)備各有4臺(tái)，這5架飛機(jī)的容量分別為8，8，5，4，4臺(tái)，問(wèn)能否有一種裝載法，使同一種類(lèi)型的設(shè)備不會(huì)有兩臺(tái)在同一架飛機(jī)上。問(wèn)

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

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

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

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

24、 我們的目的：在所有可行流中求出一個(gè)方案，使得這個(gè)可行流得到的 f 最大。 若從收點(diǎn)到發(fā)點(diǎn)連接一條假想弧(7，1)，設(shè)它的容量c71=，那么 對(duì)點(diǎn)： 對(duì)點(diǎn)： 最大流問(wè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）后，最大流問(wèn)題就成為： 容量約束： 平衡條件： 目標(biāo)函數(shù)： ijijcx 0ujjijuijjixx),(),(maxstx（11）（12）（13）（二）求最大流的方法：弧標(biāo)號(hào)法 盡管最大流問(wèn)題可以用線性規(guī)劃模型描述，但是我們一般并

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

26、；等等。 ijcjic05222416357st650230081023730071000055ijv圖2 求最大流的基本步驟： 弧標(biāo)號(hào)法求最大流的過(guò)程，就是對(duì)圖2反復(fù)地進(jìn)行修改的過(guò)程，其計(jì)算步驟如下： 步驟1. 從發(fā)點(diǎn)s到收點(diǎn)t選定一條路，使這條路通過(guò)的所有弧vij的前面約束量cij都大于0，如果找不到這樣的路，說(shuō)明已經(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中可以看出，中可以看出，顯然，顯然，就是滿(mǎn)足這樣的條件的一就是滿(mǎn)足這樣的條件的一條路。條路。 （2）在路中, , , ,所以取 。 0ijc613c736c767c613 cp（3）在路中，修改每一條弧的容量： 066613-pc660031pc660063pc16-7767pc1

28、6-7736pc660076pc通過(guò)第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中可以看出，弧 本來(lái)在圖2中是無(wú)容量可通過(guò)的，但經(jīng)過(guò)幾次修改，由 變成 ，即此時(shí)從到還可通過(guò)1（百輛），而從到，可以通過(guò)6（百輛）的容量，這說(shuō)明，修改過(guò)程實(shí)際上是把計(jì)劃中從到的通過(guò)車(chē)輛數(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ù)的方向用箭頭表示,這樣就得到最大流量圖。例如原來(lái)弧 是 ，現(xiàn)在是 ，相減為5，那邊為正，我們就記作 。這樣，就得到圖9，即最大流量。依這樣的調(diào)度方式，可以從發(fā)點(diǎn)s調(diào)運(yùn)14（百輛）汽車(chē)到收點(diǎn)t。 07525(3,6)6373371035542513672圖9 最大流量圖 圖10最大流fmx的大小是確定的，但最大流的路線可以不唯一。在上例中，如果從不同的路開(kāi)始來(lái)修改圖，也可能得到另外一個(gè)最大流圖（圖10）。 2416357563233177235注意驗(yàn)證：p104 例2應(yīng)用舉例 一制造商需要把兩個(gè)車(chē)間d1,d2生產(chǎn)的同類(lèi)商品通過(guò)運(yùn)輸網(wǎng)絡(luò)送到三個(gè)銷(xiāo)售點(diǎn)m1,m2,m3去，如圖所示。設(shè)各銷(xiāo)售點(diǎn)計(jì)劃銷(xiāo)售量分別為10,8,8，問(wèn)網(wǎng)絡(luò)的運(yùn)輸能力能否滿(mǎn)足這一要求？?jī)蓚€(gè)車(chē)間生產(chǎn)數(shù)量多少最為恰當(dāng)？三、 最小費(fèi)用