1、第九章 網(wǎng)絡(luò)優(yōu)化第一節(jié) 圖與網(wǎng)絡(luò)第二節(jié) 樹(shù)和最小樹(shù)問(wèn)題第三節(jié) 最短路問(wèn)題第四節(jié) 最大流問(wèn)題第五節(jié) 最小費(fèi)用流問(wèn)題第六節(jié) 用Excel求解網(wǎng)絡(luò)優(yōu)化問(wèn)題第一節(jié) 圖與網(wǎng)絡(luò)一、 圖的概念二、 網(wǎng)絡(luò) 在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點(diǎn)和線來(lái)畫(huà)出各式各樣的示意圖。例如城市之間的鐵路交通圖，這里用點(diǎn)表示城市，用點(diǎn)與點(diǎn)之間的線表示城市之間的鐵路線。諸如此類(lèi)還有城市中的市政管道圖，民用航空線圖等等。圖論的起源：哥尼斯堡七橋問(wèn)題：世紀(jì)歐洲的哥尼斯堡城有一條流經(jīng)全城的普雷格爾河，河的兩岸與河中的兩個(gè)小島之間有七座橋彼此相通。從陸地A、B、C、D中的任一地方開(kāi)始能否通過(guò)每座橋一次且僅通過(guò)

2、一次，就返回原出發(fā)地？CD河AB1736年瑞士數(shù)學(xué)家歐拉（E.Euler）將此問(wèn)題抽象為一個(gè)具有個(gè)點(diǎn)，條邊的圖，如下。上述問(wèn)題變成從圖中任一點(diǎn)出發(fā)，能否一筆畫(huà)出圖形？（邊不能重復(fù)）DBAC歐拉證明不能！圖的若干示例大阪新加坡紐約上海悉尼倫敦巴黎例1航線分布問(wèn)題補(bǔ)例、有八種化學(xué)藥品A、B、C、D、P、R、S、T要放進(jìn)貯藏室保管。出于安全原因，下列各種藥品不能貯藏在同一室內(nèi)：AR，AC，AT，RP，PS，ST，TB，TD，BD，DC，RS，RB，PD，SC，SD，問(wèn)貯存這八種藥品至少需要多少間貯藏室？如圖，將八種藥品表示為個(gè)點(diǎn)，不能放在同一室的兩種藥品用一條邊相連。兩種藥品沒(méi)有邊相連說(shuō)明可以放在一

3、起。ACDPRST從上圖中邊最多的點(diǎn)出發(fā)開(kāi)始分析！A、B、S，R、D，P、T、C三間D-R或AS-A與BT-C與P或RB補(bǔ)例、有甲、乙、丙、丁、戊、己六名運(yùn)動(dòng)員報(bào)名參加A、B、C、D、E、F六個(gè)項(xiàng)目的比賽。如下表，打的是各運(yùn)動(dòng)員報(bào)名參加的比賽項(xiàng)目。要求合理安排六個(gè)項(xiàng)目的比賽順序，使得每個(gè)運(yùn)動(dòng)員都不連續(xù)地參加兩項(xiàng)比賽。ABCDEF甲乙丙丁戊己把六個(gè)比賽項(xiàng)目表示為六個(gè)點(diǎn)，如果兩個(gè)項(xiàng)目有同一名運(yùn)動(dòng)員參加，就在這兩個(gè)項(xiàng)目的點(diǎn)之間連一條邊，如下圖：從相鄰邊最多的點(diǎn)開(kāi)始，找出一個(gè)點(diǎn)的序列，使依次排列的兩個(gè)點(diǎn)不相鄰（沒(méi)有邊相連），即達(dá)到要求。ABCDEFA、C、B、F、E、D就是一種比賽安排，還有其它的安排

4、方式！（從邊最多的點(diǎn)開(kāi)始安排）補(bǔ)例3、農(nóng)夫m、狼w、羊s、草g過(guò)河問(wèn)題。有位農(nóng)夫，要帶一匹狼、一只羊、一擔(dān)草過(guò)河，農(nóng)夫在，相安無(wú)事。河邊只有一條小船，一次擺渡農(nóng)夫只能帶一樣?xùn)|西（狼、羊或草）。農(nóng)夫不在場(chǎng)，狼要吃羊，羊要吃草。農(nóng)夫怎樣才能把這三樣?xùn)|西擺渡到對(duì)岸？至少要擺渡幾次？解：首先要考慮這四個(gè)對(duì)象的組合問(wèn)題。 全部組合如下：(1)m,w,s,g,(2)m,w,s,g(3)m,s,w,g(4)m,g,w,s(5)m,w,s,g(6)m,w,g,s(7)w,s,g,m(8)m,s,g,w顯然，上面的2，4，7組合是不允許的！去掉這三個(gè)組合，還剩下10個(gè)狀態(tài)。現(xiàn)在用一個(gè)頂點(diǎn)代表一種狀態(tài)，按照狀態(tài)中

5、是否有人m存在，分成上下兩組，如下圖：12345678910m,w,s,g m,s m,w,s m,w,g m,s,g w,g g s w找出從頂點(diǎn)1到頂點(diǎn)6的一條路！(1-7-4-10-3-9-2-6,1-7-4-8-5-9-2-6)補(bǔ)例4、分油問(wèn)題。 現(xiàn)在有一個(gè)8升的瓶子裝滿(mǎn)了油，想利用一個(gè)3升和一個(gè)5升的瓶子將油分成兩個(gè)4升，如何分?至少要分幾次?8,0,03,5,06,0,24,4,07,0,15,0,35,3,02,3,32,5,17,1,04,1,33,2,36,2,01,5,21,4,3將8、5、3升瓶子中的油數(shù)列成一個(gè)三數(shù)組，表示一個(gè)狀態(tài)，作為圖的一個(gè)頂點(diǎn)，狀態(tài)之間的轉(zhuǎn)化用箭頭

6、線相連，如下圖。 從上面的例子可以得知： 在自然界和人類(lèi)社會(huì)中，大量的事物以及事物間的關(guān)系都可以用圖來(lái)加以描述。一般來(lái)講，圖論中的圖是由點(diǎn)以及點(diǎn)與點(diǎn)之間的連線所構(gòu)成的，通常用點(diǎn)代表所研究的對(duì)象，用線代表兩個(gè)對(duì)象之間的關(guān)系，至于圖中點(diǎn)的相對(duì)位置如何，點(diǎn)與點(diǎn)之間的連線是長(zhǎng)還是短、是曲線還是直線，對(duì)于反映對(duì)象之間的關(guān)系，并不十分重要。因此，圖論中的圖與幾何中的圖形不是等價(jià)的！已知甲、乙、丙、丁、戊共5名乒乓球參賽選手，其中： 甲和其他各選手都賽過(guò)一次 乙和甲、丙賽過(guò) 丙和甲、乙、丁賽過(guò) 丁和甲、丙、戊賽過(guò) 戊和甲、丁賽過(guò)為反映這個(gè)情況，可用一個(gè)抽象圖表示： 甲戊丁丙乙v1v2v3v4v5e1e2e5

7、e7e3e4e6邊點(diǎn)v1，v2 ,v3 ,v4 ,v5分別代表這5名選手邊 ei 表示對(duì)應(yīng)的兩名選手賽過(guò)一次。如果進(jìn)一步反映參賽選手間的勝負(fù)關(guān)系，可用一條帶箭頭的連線表示：甲戊丁丙乙v1v2v3v4v5a1a2a5a7a3a4a6弧ai 表示對(duì)應(yīng)的兩名選手賽過(guò)一次，其箭頭方向進(jìn)一步表示這次比賽的勝負(fù)關(guān)系。如甲勝乙、乙勝丙等。 通常用點(diǎn)表示研究對(duì)象,用點(diǎn)與點(diǎn)之間的線表示研究對(duì)象之間的特定關(guān)系。由于在一般情況下，圖中的相對(duì)位置如何，點(diǎn)與點(diǎn)之間線的長(zhǎng)短曲直，對(duì)于反映研究對(duì)象之間的關(guān)系，顯得并不重要。因此，圖論中的圖與幾何圖及工程圖等本質(zhì)上是不同的。為以后研究的方便，我們首先給出有關(guān)圖的一些基本概念。

8、 一、圖的概念圖是由作為研究對(duì)象的有限個(gè)頂點(diǎn)的集合和表達(dá)這些頂點(diǎn)之間關(guān)系的m條線的集合組成的。記頂點(diǎn)集合為 ，線集合為 。線又分為弧（Arc）和邊（Edge）。則圖記為G=（V，L）。頂點(diǎn)有時(shí)也稱(chēng)為節(jié)點(diǎn)（node）。弧是由一對(duì)有序的頂點(diǎn)組成，表示了兩個(gè)頂點(diǎn)之間可能運(yùn)動(dòng)的方向。如 表示從頂點(diǎn) 指向頂點(diǎn) 的弧， 是起點(diǎn)， 是終點(diǎn)。取消弧的方向就變成了邊。邊是只要任兩點(diǎn)之間有連線，兩個(gè)方向均可使用。弧可看作是城市道路中的單行道，而邊則是雙行道。由頂點(diǎn)集和弧組成的圖稱(chēng)為有向圖，如圖（a）。由頂點(diǎn)集和邊組成的圖稱(chēng)為無(wú)向圖，如圖（b） (a)(b)鏈：有一序列弧 ，如果每一個(gè)弧 與前一個(gè)弧 恰有一個(gè)公共頂

9、點(diǎn)，則稱(chēng)這一序列弧為一個(gè)鏈。道路：如果鏈中每一個(gè)弧的終點(diǎn)是下面一個(gè)弧的起點(diǎn)，則這個(gè)鏈稱(chēng)為一個(gè)道路。環(huán)（圈）：連接 與 的一條鏈，如果 與 是同一個(gè)點(diǎn)時(shí)，稱(chēng)此鏈為環(huán)。次（或度）：以 為頂點(diǎn)的邊的條數(shù)稱(chēng)為頂點(diǎn) 的次（或度），記作 。次為零的點(diǎn)稱(chēng)為弧立點(diǎn)，次為1的點(diǎn)稱(chēng)為懸掛點(diǎn)。懸掛點(diǎn)的邊稱(chēng)為懸掛邊。次為奇數(shù)的點(diǎn)稱(chēng)為奇點(diǎn)，次為偶數(shù)的點(diǎn)稱(chēng)為偶點(diǎn)。子圖：設(shè)有兩個(gè)圖G1=V1，E1, G2=V2，E2，如果V2V1，E2E1，稱(chēng)G2是G1的子圖；如果V2 V1，E2E1，稱(chēng)G2是G1的真子圖；如果V2 =V1，E2E1，稱(chēng)G2是G1的生成子圖（或稱(chēng)支撐子圖）。連通圖：一個(gè)圖中任意兩點(diǎn)間至少有一個(gè)鏈相連，則稱(chēng)

10、此圖為連通圖。否則稱(chēng)為不連通圖。任何一個(gè)不連通圖都可以分為若干個(gè)連通子圖。v1v5v4v2v3e1e8e7e6e5e4e3e2v1v5v4v2e1e5e3子圖v1v5v4v2v3e8e6e5e2生成子圖二、網(wǎng)絡(luò) 點(diǎn)或邊帶有某種數(shù)量指標(biāo)的圖叫網(wǎng)絡(luò)圖，簡(jiǎn)稱(chēng)網(wǎng)絡(luò)。 與點(diǎn)或邊有關(guān)的某些數(shù)量指標(biāo)，我們經(jīng)常稱(chēng)之為權(quán)，權(quán)可以代表如距離、費(fèi)用、容量等。 左圖可以看作： 從發(fā)電廠（節(jié)點(diǎn)1）向某城市（節(jié)點(diǎn)6）輸送電力，必須通過(guò)中轉(zhuǎn)站（節(jié)點(diǎn)2，3，4，5）轉(zhuǎn)送，邊上數(shù)字代表兩節(jié)點(diǎn)間的距離。電力公司希望選擇合適的中轉(zhuǎn)站，使從電廠到城市的傳輸路線最短。 一個(gè)輸油管道網(wǎng)。節(jié)點(diǎn)1表示管道的起點(diǎn)，節(jié)點(diǎn)6表示管道的終點(diǎn)，節(jié)點(diǎn)2

11、到5表示中轉(zhuǎn)站，旁邊的數(shù)字表示該段管道能通過(guò)的最大輸送量。應(yīng)怎樣安排輸油線路，使從節(jié)點(diǎn)1到節(jié)點(diǎn)6的總輸送量最大？ 一張城市分布圖。現(xiàn)在要在各城市之間架設(shè)電話(huà)線，應(yīng)如何架設(shè)，使各城市之間既能通話(huà)，又使總的架設(shè)路線最短？ 第二節(jié) 樹(shù)和最小樹(shù)問(wèn)題一、 樹(shù)的概念及性質(zhì)二、 圖的子樹(shù)三、 最小生成樹(shù)四、 最小生成樹(shù)算法一、樹(shù)的概念及性質(zhì)連通且不含環(huán)的無(wú)向圖稱(chēng)為樹(shù)。 樹(shù)具有下面的性質(zhì)：性質(zhì)9.1：在樹(shù)中，任意兩頂點(diǎn)之間必有一條且僅有一條鏈。性質(zhì)9.2：在樹(shù)中去掉任一條邊，則樹(shù)成為不連通圖。性質(zhì)9.3：在樹(shù)中不相鄰的兩個(gè)頂點(diǎn)間添上一條邊，恰好得到一個(gè)環(huán)。樹(shù)：連通且不含圈的無(wú)向圖 樹(shù)的性質(zhì)： 任意兩頂點(diǎn)之間必

12、有一條且僅有一條鏈。 去掉任一條邊，則樹(shù)成為不連通圖。 不相鄰的兩個(gè)頂點(diǎn)間添上一條邊，恰好得到一個(gè)環(huán)（圈）。樹(shù)與古代美女一樣，是恰到好處的，“減一分則瘦，加一分則肥”二、 圖的子樹(shù)子樹(shù)：如果圖G=（V，L）的子圖是樹(shù)，則稱(chēng)T為G的一個(gè)子樹(shù)。如下圖中的兩個(gè)圖，(b)是(a)的一個(gè)部分樹(shù)。顯然，如果圖G有子樹(shù)，則G必定是連通圖。反之，如果圖G是連通圖，則G必有子樹(shù)。三、 最小生成樹(shù)最小生成樹(shù)：設(shè)有一連通圖G=（V，L），對(duì)于每一條邊 ，有一個(gè)權(quán) 。一棵生成樹(shù)所有樹(shù)枝上權(quán)的總和，稱(chēng)為這個(gè)生成樹(shù)的權(quán)，具有最小權(quán)的生成樹(shù)稱(chēng)為最小生成樹(shù)簡(jiǎn)稱(chēng)最小樹(shù)。最小樹(shù)定理：如果T是圖G的一顆樹(shù)，則它是最小樹(shù)，當(dāng)且僅當(dāng)對(duì)

13、T外的每條邊 有： 其中， 是樹(shù)T內(nèi)連接點(diǎn) 和 的唯一的鏈。由于圖中不同弧的權(quán)可能相等，所以最小生成樹(shù)并不一定唯一。四、 最小生成樹(shù)算法1求最小生成樹(shù)的破圈法第1步：先任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊，若在同一圈中有幾條都是權(quán)最大邊，則任選其中的一條邊去掉。第2步：在余下的子圈中，重復(fù)上述步驟，直至沒(méi)有圈為止。2求最小生成樹(shù)的避圈法第1步：選一點(diǎn)v1 ，在所有與v1相關(guān)聯(lián)的邊中選取最小權(quán)邊 (vi, vj) ，標(biāo)記為“已選”。第2步：把所有點(diǎn)分為兩部分V1和V2 ，其中：V1表示與標(biāo)記為“已選”邊相關(guān)聯(lián)的點(diǎn)集；V2 是剩下的點(diǎn)構(gòu)成的集合。第3步：選取最小權(quán)邊：如果V2 ，則從邊集 (vi,

14、 vj)|viV1, vjV2選取最小權(quán)邊，標(biāo)記為“已選”后，返回第2步；否則，算法結(jié)束。例9.1用破圈法和避圈法分別求最小生成樹(shù)。23164515008575805090851004065破圈法避圈法生成樹(shù)：6個(gè)點(diǎn)，只有5條邊，最小邊長(zhǎng)310補(bǔ)例、用破圈法求圖的最小支撐樹(shù)BASDTCE27254143515下圖中頂點(diǎn)AT代表村鎮(zhèn)，邊代表道路，邊上的數(shù)字為道路長(zhǎng)度，現(xiàn)在想沿著道路架設(shè)電線，使得所有村鎮(zhèn)通電，如何架設(shè)總線路最短？（即求圖的最小支撐樹(shù)）7第三節(jié) 最短路問(wèn)題一、 最短路問(wèn)題二、 最短路問(wèn)題算法一、 最短路問(wèn)題設(shè)一個(gè)連通的賦權(quán)有向圖G =(V, A)，對(duì)于每一個(gè)弧e = (vi,vj)

15、，相應(yīng)地有一個(gè)權(quán)l(xiāng)ij。vs和vt是G中的兩個(gè)頂點(diǎn)，是G中從vs到vt的任意一條路，定義路的權(quán)是中所有弧的權(quán)之和，記作L()。最短路問(wèn)題就是要在所有從vs到vt的路中，尋找一個(gè)權(quán)最小的路*，亦即L(*) = min L()。*稱(chēng)為從vs到vt的最短路。*的權(quán)L(*)稱(chēng)為從vs到vt的距離。二、最短路問(wèn)題算法Dijkstra基本步驟是：假設(shè)每個(gè)弧的權(quán)是非負(fù)的，給每個(gè)頂點(diǎn)vi記一個(gè)數(shù)（稱(chēng)為標(biāo)號(hào)），標(biāo)號(hào)分臨時(shí)性標(biāo)號(hào)T和永久性標(biāo)號(hào)P，永久性標(biāo)號(hào)表示從到該點(diǎn)的最短路權(quán)，得到永久性標(biāo)號(hào)的不再改變標(biāo)號(hào)；臨時(shí)性標(biāo)號(hào)表示從開(kāi)始點(diǎn)v1到該點(diǎn)vi的最短路權(quán)的上界。算法的每一步都把某一點(diǎn)的T標(biāo)號(hào)改為P標(biāo)號(hào)。開(kāi)始時(shí)給初

16、始點(diǎn)v1的標(biāo)號(hào)記為0，即P(v1)=0，其它點(diǎn)（記為臨時(shí)性標(biāo)號(hào)）的標(biāo)號(hào)記為，即T(vi)= (i= 2 , ,n)。然后，若vi點(diǎn)是剛得到P標(biāo)號(hào)的點(diǎn)，考慮L中與vi點(diǎn)相連的弧（vi,vj）且vj是T標(biāo)號(hào)。對(duì)的標(biāo)號(hào)進(jìn)行如下更改： T(vj)=minT(vj),P(vi)+wij 比較所有具有T標(biāo)號(hào)的點(diǎn)，把最小者改為P標(biāo)號(hào)。當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)。直到全部點(diǎn)均為P標(biāo)號(hào)為止。 1325464332322 第0步：P(1)=0,T(i)=+； 第1步：與1相連的標(biāo)號(hào)為2,3，均是T標(biāo)號(hào)，修改2,3的標(biāo)號(hào)，T(2)=minT(2),P(1)+w12=4,T(3)=3；在所有的T標(biāo)號(hào)中，

17、3的標(biāo)號(hào)最小，改3的標(biāo)號(hào)為P(3)=3； 第2步：修改與3相連的T標(biāo)號(hào)；在所有剩下的T標(biāo)號(hào)中，2的標(biāo)號(hào)最小，改為P(2)=4； 第3步：修改與2相連的T標(biāo)號(hào)；在所有剩下的T標(biāo)號(hào)中，5的標(biāo)號(hào)最小，改為P(5)=6； 第4步：修改與5相連的T標(biāo)號(hào)；在所有剩下的T標(biāo)號(hào)中，4的標(biāo)號(hào)最小，改為P(4)=7； 第5步：修改與4相連的T標(biāo)號(hào)；只剩下節(jié)點(diǎn)6是T標(biāo)號(hào)，修改6的標(biāo)號(hào)，P(6)=8。 從節(jié)點(diǎn)6開(kāi)始回退，得到最短路。P(1)=0T(3)=+T(2)=+T(3)=3T(5)=+P(3)=3T(5)=6T(2)=4T(4)=+T(6)=+P(2)=4T(4)=7P(5)=6T(6)=8P(4)=7P(6)

18、=8P(6)=8P(5)=6P(3)=3P(1)=0最短路問(wèn)題 車(chē)齡每年的維護(hù)費(fèi)用交易費(fèi)用01234520004000500090001200070006000200010000從一特殊的節(jié)點(diǎn)出發(fā)，找出從該節(jié)點(diǎn)到網(wǎng)絡(luò)中任何其它節(jié)點(diǎn)的最短路徑問(wèn)題某人買(mǎi)了一輛價(jià)值12000美元的新車(chē)，一輛車(chē)每年的維護(hù)費(fèi)用依賴(lài)于年初時(shí)的車(chē)齡，具體費(fèi)用見(jiàn)下表。為了避免舊車(chē)的高維護(hù)費(fèi)用，他決定賣(mài)掉舊車(chē)買(mǎi)新車(chē)。舊車(chē)的價(jià)格依賴(lài)于交易時(shí)的車(chē)齡，見(jiàn)下表。為計(jì)算簡(jiǎn)單起見(jiàn)，假設(shè)任何時(shí)間新車(chē)的價(jià)格不變均為12000美元。他希望在今后5年內(nèi)的凈費(fèi)用最小（即：凈費(fèi)用=購(gòu)買(mǎi)價(jià)+維護(hù)價(jià)-售出價(jià)）。 123456217777712121221

19、31314412211-02-73-124-195-246-31第四節(jié) 最大流問(wèn)題一、基本概念二、求最大流的標(biāo)號(hào)算法在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著與流量有關(guān)的問(wèn)題。如鐵路運(yùn)輸系統(tǒng)中的車(chē)輛流，城市給排水系統(tǒng)的水流問(wèn)題等等。研究物質(zhì)從一點(diǎn)流到另一點(diǎn)的最大流量問(wèn)題，稱(chēng)為最大流問(wèn)題。最大流問(wèn)題是圖與網(wǎng)絡(luò)理論中十分重要的優(yōu)化問(wèn)題，他的應(yīng)用非常廣泛，如交通運(yùn)輸網(wǎng)絡(luò)中人流、車(chē)流、貨流，通訊網(wǎng)絡(luò)中的信息流以及金融領(lǐng)域的資金流等等。本節(jié)主要介紹最大流問(wèn)題的基本概念和算法。一、 基本概念網(wǎng)絡(luò)與流研究網(wǎng)絡(luò)流問(wèn)題時(shí)，必須給出各弧的通過(guò)能力，它們表示弧的容量，如下圖中各弧的權(quán)，通常記為 。在有向圖中指定一點(diǎn)稱(chēng)為發(fā)點(diǎn)，另

20、一點(diǎn)稱(chēng)為收點(diǎn)，其余的點(diǎn)稱(chēng)為中間點(diǎn)。流過(guò)網(wǎng)絡(luò)各邊的流量具有一定的方向性，圖上各邊箭頭所指方向，即為流量流動(dòng)的方向。我們把標(biāo)有弧容量 的網(wǎng)絡(luò)稱(chēng)為容量網(wǎng)絡(luò)，把容量網(wǎng)絡(luò)中實(shí)際通過(guò)的流量集 稱(chēng)為網(wǎng)絡(luò)流。 可行流與最大流在實(shí)際問(wèn)題中，網(wǎng)絡(luò)流必須滿(mǎn)足兩個(gè)條件，一是每個(gè)弧的流量不能超過(guò)該弧的最大通過(guò)能力，即容量；二是中間支點(diǎn)的流量為零。對(duì)每個(gè)支點(diǎn)，流入和流出該點(diǎn)的物資總量之差，是該點(diǎn)的凈輸出量，簡(jiǎn)稱(chēng)為該點(diǎn)的流量，由于中間支點(diǎn)只起中轉(zhuǎn)的作用，所以中間點(diǎn)的流量為零。而發(fā)點(diǎn)和收點(diǎn)的流量必須相等。設(shè)圖G=（V，L），其中支點(diǎn)集 ，這樣就得到如下兩個(gè)約束。（1）容量限制條件：對(duì)每個(gè)弧 ，有（2）平衡條件：對(duì)于中間點(diǎn)：流

21、入量=流出量，即對(duì)每個(gè) 有對(duì)于發(fā)點(diǎn) ：對(duì)于收點(diǎn) ：式中 稱(chēng)為發(fā)點(diǎn)（或收點(diǎn)）的流量。我們對(duì)滿(mǎn)足以上兩個(gè)條件的網(wǎng)絡(luò)流稱(chēng)為可行流。網(wǎng)絡(luò)系統(tǒng)上可行流具有如下特點(diǎn)：（1）發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必相等；（2）每一個(gè)中間點(diǎn)的流入量與流出量的必相等；（3）每一個(gè)弧上的流量不能超過(guò)它的最大通過(guò)能力（即容量）。增廣鏈在網(wǎng)絡(luò)中，如果 ，則稱(chēng)此弧為飽和弧；如果 則稱(chēng)此弧為非飽和弧；如果 ，則稱(chēng)此弧為零弧。設(shè)C是網(wǎng)絡(luò)中從發(fā)點(diǎn) 到收點(diǎn) 的一條鏈，鏈的方向是從 到 。對(duì)于鏈上的弧，如果弧的方向與鏈的方向一致，稱(chēng)此弧為前向弧。前向弧的全體記為 。如果弧的方向與鏈的方向相反，則稱(chēng)此弧為后向弧。后向弧全體記為 。增廣鏈：

22、設(shè) 是一個(gè)可行流，C是從發(fā)點(diǎn) 到收點(diǎn) 的一條鏈，若C滿(mǎn)足以下條件，則稱(chēng)C為一條增廣鏈：(1) 在弧上 ， ，即 中每一條弧是非飽和弧。(2) 在弧上 ， ，即 中每一條弧是非零流弧。割集：設(shè)容量網(wǎng)絡(luò)G=(V,E,C)，如果點(diǎn)集V被剖分為兩個(gè)非空集合S1和S2，發(fā)點(diǎn)vsS1，收點(diǎn)vtS2，那么將弧集(S1, S2) = (vi, vj) | viS1, vjS2稱(chēng)為G的一個(gè)割集。容量最小的割集稱(chēng)為最小割集。最大流-最小割定理：1）設(shè)f為容量網(wǎng)絡(luò)G=(V, E, C)的任一可行流，流量為W( f )， (S1, S2)為G的任一割集，容量為C(S1, S2)。則有W( f ) C(S1, S2)。

23、2）在任一容量網(wǎng)絡(luò)G=(V, E, C)中，最大流的流量等于最小割的容量。二、求最大流的標(biāo)號(hào)算法標(biāo)號(hào)算法的基本思想是從網(wǎng)絡(luò)圖的一個(gè)可行流出發(fā)，用給頂點(diǎn)標(biāo)號(hào)的方法找增廣鏈。如果找到增廣鏈，說(shuō)明當(dāng)前流不是最大，則增大可行流；然后繼續(xù)在增大了流量的新可行流中找增廣鏈，直到在某個(gè)新可行流中找不到增廣鏈為止，這個(gè)新可行流就是最大流，同時(shí)也得到了最小割集。具體的算法過(guò)程：從一個(gè)可行流 出發(fā)（若網(wǎng)絡(luò)中沒(méi)有給定 ，則可以設(shè) 是零流），需要經(jīng)過(guò)標(biāo)號(hào)過(guò)程與調(diào)整過(guò)程。1標(biāo)號(hào)過(guò)程在這個(gè)過(guò)程中，網(wǎng)絡(luò)中的點(diǎn)或是標(biāo)號(hào)點(diǎn)或是未標(biāo)號(hào)點(diǎn)。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：第一標(biāo)號(hào)表示它的標(biāo)號(hào)是從哪一點(diǎn)得到的，以便找出增廣鏈；第二個(gè)標(biāo)號(hào)

24、是為確定增廣鏈的調(diào)整量 用的。標(biāo)號(hào)過(guò)程開(kāi)始時(shí)，總是先給發(fā)點(diǎn) 標(biāo)上 。其余各點(diǎn)標(biāo)號(hào)的規(guī)則是：設(shè) 是已標(biāo)號(hào)的點(diǎn)，檢查與 點(diǎn)關(guān)聯(lián)的另一頂點(diǎn)未標(biāo)號(hào)的弧：（1）如果在弧 上（即前向弧）， ，則給 標(biāo)號(hào) ，其中 。如果 ，則 不標(biāo)號(hào)。（1）如果在弧 上（即后向弧）， ，則給 標(biāo)號(hào) ，其中 。負(fù)號(hào)說(shuō)明經(jīng)后向弧到 。如果 ，則 不標(biāo)號(hào)。重復(fù)上述步驟，直到 被標(biāo)上號(hào)，表明得到一條從 到 的增廣鏈C，轉(zhuǎn)入調(diào)整過(guò)程。2調(diào)整過(guò)程由收點(diǎn) 標(biāo)號(hào)算出的 作為調(diào)整量（即 ）。對(duì)增廣鏈各弧的調(diào)整如下：增廣鏈以外各弧流量不變。去掉所有標(biāo)號(hào)，對(duì)新的可行流 ，重新進(jìn)入標(biāo)號(hào)過(guò)程。直到標(biāo)號(hào)過(guò)程中斷。當(dāng)前流就是最大流。例9.5. 用標(biāo)號(hào)法

25、求圖9-14所示網(wǎng)絡(luò)的最大流。弧旁的數(shù)為 。 解：1. 標(biāo)號(hào)過(guò)程首先給初始點(diǎn)vs標(biāo)上 。（1）檢查vs，在弧(vs,v1)上， ，不滿(mǎn)足標(biāo)號(hào)條件。在弧(vs,v2)上， ，則v2的標(biāo)號(hào)為 ，其中 （2）檢查v2，在弧(v2,vt)上， ，不滿(mǎn)足標(biāo)號(hào)條件。在弧(v1,v2)上， ，則v1的標(biāo)號(hào)為 ，其中（3）檢查v1，在弧(v1,v3)上， ，則v3的標(biāo)號(hào)為 ，其中（4）檢查v3，在弧(v3,vt)上， ，則vt的標(biāo)號(hào)為 ，其中因vt有了標(biāo)號(hào)，所以轉(zhuǎn)入調(diào)整過(guò)程。第五節(jié) 最小費(fèi)用流問(wèn)題 在研究實(shí)際問(wèn)題時(shí)，我們不僅考慮流量，還經(jīng)常要考慮費(fèi)用的問(wèn)題。如運(yùn)輸系統(tǒng)的貨物流，即要考慮貨運(yùn)量最大，又要考慮總費(fèi)

26、用最小。對(duì)于這類(lèi)問(wèn)題就可用下面的最小費(fèi)用最大流問(wèn)題來(lái)解決。最小費(fèi)用流問(wèn)題就是：對(duì)于網(wǎng)絡(luò)圖G中的弧，除標(biāo)明弧的容量 外，還要標(biāo)明流過(guò)該弧單位流量的費(fèi)用 ，求G的一個(gè)可行流 ，使得流的總運(yùn)輸費(fèi)用達(dá)到最小 特別，如果可行流 是最大流時(shí)，此問(wèn)題就是最小費(fèi)用最大流問(wèn)題。 求最小費(fèi)用最大流的基本思路是：從一個(gè)費(fèi)用最小的可行流 出發(fā)（這樣的可行流一定存在，因?yàn)橘M(fèi)用 ，所以 就是一個(gè)流量為0的最小費(fèi)用流），找出這個(gè)可行流 的費(fèi)用最小的一條增廣鏈C，沿C調(diào)整 ，直到找不到費(fèi)用最小的增廣鏈，就得到了最小費(fèi)用最大流。 因此，求費(fèi)用最小增廣鏈?zhǔn)窃搯?wèn)題的關(guān)鍵。 例9.6求下圖（a）所示網(wǎng)絡(luò)的最小費(fèi)用最大流，弧旁權(quán)數(shù)為 。 第六節(jié) 用Excel求解