運(yùn)籌學(xué)第7章 最大流問題(精簡).ppt

1、最大流問題,給定一個(gè)有向圖G(V,E)，其中僅有一個(gè)點(diǎn)的入次為零稱為發(fā)點(diǎn)（源），記為vs，僅有一個(gè)點(diǎn)的出次為零稱為收點(diǎn)（匯），記為vt，其余點(diǎn)稱為中間點(diǎn)。,基本概念,3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,對于G中的每一條邊(vi,vj)，相應(yīng)地給一個(gè)數(shù)cij（cij0），稱為邊(vi,vj)的容量。我們把這樣的網(wǎng)絡(luò) G稱為容量網(wǎng)絡(luò) ，記為G(V,E,C)。,網(wǎng)絡(luò)上的流，是指定義在邊集E上的函數(shù)ff(vi,vj)，并稱f(vi,vj)為邊(vi,vj)上的流量，簡記為fij。,3,1,5,2,1,0,1,0,4,1,2,2,3,1,5,2,2,1,vs,v2,v

2、1,v3,v4,vt,標(biāo)示方式：每條邊上標(biāo)示兩個(gè)數(shù)字，第一個(gè)是容量，第二是流量,可行流、可行流的流量、最大流。,可行流是指滿足如下條件的流：,（1）容量限制條件：對G中每條邊(vi,vj), 有,（2）平衡條件：,對中間點(diǎn)，有：,（即中間點(diǎn)vi的物資輸入量等于輸出量）,對收點(diǎn)vt與發(fā)點(diǎn)vs，有：,（即vs發(fā)出的物資總量等于vt接收的物資總量），W是網(wǎng)絡(luò)的總流量。,可行流總是存在的，例如f=0就是一個(gè)流量為0的可行流。 所謂最大流問題就是在容量網(wǎng)絡(luò)中尋找流量最大的可行流。 一個(gè)流f=fij，當(dāng)fij=cij，則稱f對邊(vi, vj)是飽和的，否則稱f對邊(vi, vj)不飽和。對于不飽和的，其

3、間隙為ij=cij-fij 最大流問題實(shí)際上是一個(gè)線性規(guī)劃問題。 但利用它與圖的密切關(guān)系，可以利用圖直觀簡便地求解。,給定容量網(wǎng)絡(luò)G(V,E,C)，若點(diǎn)集V被剖分為兩個(gè)非空集合V1和V2，使 vsV1 ，vtV2，則把邊集(V1,V2)稱為（分離vs和vt的）割集。,顯然，若把某一割集的邊從網(wǎng)絡(luò)中去掉，則從vs到vt便不存在路。所以，直觀上說，割集是從vs到vt的必經(jīng)之路。,3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,vs,v1,v4,v3,vt,v2,邊集（vs,v1），（v1,v3），（v2,v3），（v3,vt），（v4,vt）是G的割集。其頂點(diǎn)分別屬于兩個(gè)互

4、補(bǔ)不相交的點(diǎn)集。去掉這五條邊，則圖不連通，去掉這五條邊中的任意1-4條，圖仍然連通。,割集的容量(簡稱割量) 最小割集,割集(V1, V2)中所有起點(diǎn)在V1，終點(diǎn)在V2的邊的容量的和稱為割集容量。例如下圖中所示割集的容量為5,3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,在容量網(wǎng)絡(luò)的所有割集中，割集容量最小的割集稱為最小割集（最小割）。,對于可行流ffij，我們把網(wǎng)絡(luò)中使fijcij的邊稱為飽和邊，使fij0的邊稱為非零流邊。,設(shè)f是一個(gè)可行流，是從vs到vt的一條鏈，若滿足前向邊都是非飽和邊,后向邊都是都是非零流邊,則稱是（可行流f的）一條可增廣鏈。,3,1,5,2

5、,1,0,1,0,4,1,2,2,3,1,5,2,2,1,vs,v2,v1,v3,v4,vt,若是聯(lián)結(jié)發(fā)點(diǎn)vs和收點(diǎn)vt的一條鏈，我們規(guī)定鏈的方向是從vs到vt，則鏈上的邊被分成兩類：前向邊、后向邊。,對最大流問題有下列定理： 定理1 容量網(wǎng)絡(luò)中任一可行流的流量不超過其任一割集的容量。 定理2（最大流-最小割定理）任一容量網(wǎng)絡(luò)中，最大流的流量等于最小割集的割量。 推論1 可行流f*fij*是最大流，當(dāng)且僅當(dāng)G中不存在關(guān)于f*的增廣鏈。,求最大流的標(biāo)號法,標(biāo)號法思想是：先找一個(gè)可行流。對于一個(gè)可行流，經(jīng)過標(biāo)號過程得到從發(fā)點(diǎn)vs到收點(diǎn)vt的增廣鏈；經(jīng)過調(diào)整過程沿增廣鏈增加可行流的流量，得新的可行流

6、。重復(fù)這一過程，直到可行流無增廣鏈，得到最大流。,標(biāo)號過程: (1)給vs標(biāo)號(,+)，vs成為已標(biāo)號未檢查的點(diǎn)，其余都是未標(biāo)號點(diǎn)。 (2)取一個(gè)已標(biāo)號未檢查的點(diǎn)vi，對一切未標(biāo)號點(diǎn)vj：若有非飽和邊(vi,vj)，則vj標(biāo)號(vi,l(vj)，其中l(wèi)(vj)minl(vi),cij fij，vj成為已標(biāo)號未檢查的點(diǎn)；若有非零邊(vj,vi)，則vj標(biāo)號(-vi,l(vj)，其中l(wèi)(vj)minl(vi), fji，vj成為已標(biāo)號未檢查的點(diǎn)。vi成為已標(biāo)號已檢查的點(diǎn)。 (3)重復(fù)步驟(2)，直到vt成為標(biāo)號點(diǎn)或所有標(biāo)號點(diǎn)都檢查過。若vt成為標(biāo)號點(diǎn)，表明得到一條vs到vt的增廣鏈，轉(zhuǎn)入調(diào)整過程；

7、若所有標(biāo)號點(diǎn)都檢查過，表明這時(shí)的可行流就是最大流，算法結(jié)束。 調(diào)整過程：在增廣鏈上，前向邊流量增加l(vt)，后向邊流量減少l(vt)。,下面用實(shí)例說明具體的操作方法：例,(3,3),(5,1),(1,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),vs,v2,v1,v3,v4,vt,(3,3),(5,1),(1,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),vs,v2,v1,v3,v4,vt,在圖中給出的可行流的基礎(chǔ)上，求vs到vt的最大流。,(,+),(vs,4),(-v1,1),(-v2,1),(v2,1),(v3,1),(3

8、,3),(5,2),(1,0),(1,0),(4,3),(2,2),(3,0),(5,3),(2,2),vs,v2,v1,v3,v4,vt,(vs,3),(,+),得增廣鏈，標(biāo)號結(jié)束，進(jìn)入調(diào)整過程,無增廣鏈，標(biāo)號結(jié)束，得最大流。同時(shí)得最小割。,下圖中已經(jīng)標(biāo)示出了一個(gè)可行流，求最大流, ,vs, 3,vs, 4,v2, 4,-v4, 2,v4, 3,如圖已經(jīng)得到增廣鏈，然后進(jìn)行調(diào)整。,調(diào)整后的可行流如下圖：, ,vs, 3,vs, 1,v2, 1,-v4, 1,v3, 1,v5, 1,如圖已經(jīng)得到增廣鏈，然后進(jìn)行調(diào)整。,調(diào)整后的可行流如下圖：,-, ,vs, 3,如圖所示最小割集的容量（即當(dāng)前可

9、行流的流量），就是最大流的流量。注：用該方法可以同時(shí)得到最小割集，即圖中連結(jié)已標(biāo)號的點(diǎn)與未標(biāo)號的點(diǎn)的邊集。,具有實(shí)際背景的例子,國慶大假期間旅游非?；鸨?，機(jī)票早已訂購一空。成都一家旅行社由于信譽(yù)好、服務(wù)好，所策劃的國慶首都游的行情看好，要求參加的游客眾多，游客甚至不惜多花機(jī)票錢輾轉(zhuǎn)取道它地也愿參加此游。旅行社只好緊急電傳他在全國各地的辦事處要求協(xié)助解決此問題。很快，各辦事處將其已訂購機(jī)票的情況傳到了總社。根據(jù)此資料，總社要作出計(jì)劃，最多能將多少游客從成都送往北京以及如何取道轉(zhuǎn)機(jī)。下面是各辦事處已訂購機(jī)票的詳細(xì)情況表：,用圖來描述就是,發(fā)點(diǎn)vs =成都，收點(diǎn)vt =北京。前面已訂購機(jī)票情況表中的數(shù)字即是各邊上的容量（允許通過的最大旅客量），當(dāng)各邊上的實(shí)際客流量為零時(shí)略去不寫，以零流作為初始可行流。,利用標(biāo)號法（經(jīng)5次迭代）可以得到從成都發(fā)送旅客到北京的最大流量如圖所示,重,武,昆,上,廣,西,鄭,沈,京