最大流與最小費(fèi)用流

1、1第四節(jié) 最大流問題 最大流問題是一類應(yīng)用極為廣泛的問題，例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流，供水網(wǎng)絡(luò)中有水流，金融系統(tǒng)中有現(xiàn)金流，通訊系統(tǒng)中有信息流，等等。50年代福特（Ford）、富克遜（Fulkerson）建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。 一、最大流有關(guān)概念 如果我們把圖5-41年做輸油管道網(wǎng)， 為起點(diǎn)， 為終點(diǎn)， 為中轉(zhuǎn)站，邊上的數(shù)表示該管道的最大輸油能力，問應(yīng)該如何安排各管道輸油量，才能使從 到 的總輸油量最大？ 管道網(wǎng)絡(luò)中每邊的最大通過能力即容量是有限的，實(shí)際流量也不一定等于容量，上述問題就是要討論如何充分利用裝置的能力，以取得最好效果（流量最大），這類問題通

2、常稱為最大流問題。tusu1234,u u u utusu2 定義20 設(shè)有向連通圖 的每條邊上有非負(fù)數(shù)稱 為邊容量，僅有一個(gè)人次為0的點(diǎn) 稱為發(fā)點(diǎn)（源），一個(gè)出次為0的點(diǎn) 稱為收點(diǎn) （匯），其余點(diǎn)為中間點(diǎn)，這樣的網(wǎng)絡(luò)G稱為容量網(wǎng)絡(luò)，常記做 。 對(duì)任一G中的邊 有流量，稱集合 為G的一個(gè)流。稱滿足下列條件的流 為可行流： （1）容量限制條件：對(duì)G中每條邊， 有 （2）平衡條件：對(duì)中間點(diǎn) ，有 （即中間點(diǎn) 的物資的輸入量與輸出量相等） 對(duì)收、發(fā)點(diǎn) 有 （即從 點(diǎn)發(fā)出的物資總量等于 點(diǎn)輸入量）W為網(wǎng)絡(luò)流的總流量。tususijtijffW,tsu uivijkijkffiv0ijijfc ijff

3、ijf,ijv v,GV E Ctvsvijc,ijv v,GV EG3 可行流總是純?cè)诘?，例?就是一個(gè)流量為0的可行流。所謂最大流問題就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。 一個(gè)流 ，當(dāng) 則稱流 對(duì)邊 是飽和的，否則稱 對(duì) 不飽和。最大流問題實(shí)際是個(gè)線性規(guī)劃問題，但是利用它與圖的緊密關(guān)系，能更為直觀簡(jiǎn)便地求解。 定義21 容量網(wǎng)絡(luò) 為發(fā)、收點(diǎn)，若有邊集 為E的子集，將G分為兩個(gè)子圖 其頂點(diǎn)集合分別記 分屬 ，滿足： 不連通； 為 的真子集，而 仍連通，則稱 為G的割集，記 。,ES S E,G V EEEE,G V EE,S S,stv v, ,S S SS SS 12,G GE, ,s

4、tGV E Cv v,ijv vf,ijv vf,ijijfc ijff 0f 4 割集 中所有始點(diǎn)在S，終點(diǎn)在 的邊的容量之和，稱為 的割集容量，記為 。如圖5-41中，邊集 和邊集 都是G的割集，它們割集容量分別為9和11。容量網(wǎng)絡(luò)G的割集有多個(gè)，其中割集容量最小者稱為網(wǎng)絡(luò)G的最小割集容量（簡(jiǎn)稱最小割）。 二、最大流-最小割 定理 由割集的定義不難看出，在容量網(wǎng)絡(luò)中割集是由 到 的必經(jīng)之路，無(wú)論拿掉哪個(gè)割集， 到 便不再相通，所以任何一個(gè)可行流的流量不會(huì)超過任一割集的容量，也即網(wǎng)絡(luò)的最大流與最小割容量（最小割）滿足下面定理。tvsvtvsv 134,sssv vv vv v 1132334

5、,sttv vv vv vv vv v,C S S,S SS,S S5 定理10 設(shè)f為網(wǎng)絡(luò)G=(V,E,C)的任一可行流，流量為 是分離 的任一割集，則有 由此可知，若能找到一個(gè)可行流 一個(gè)割集 ，使得 的流量 ，則 一定是最大流，而 就是所有割集中容量最小的一個(gè)。下面證明最大流-最小割定理，定理的證明實(shí)際上就是給出了尋找最大流的方法。 定理11（最大流-最小割定理）任一網(wǎng)絡(luò)G中，從 到 的最大流的流量等于分高 的最小割的容量。,stv vtvsv,SSf,WC SSf,SS,f,WC S S,stv v,WS S6 證明 設(shè) 是一個(gè)最大流，流量為W，用下面的方法定義點(diǎn)集 令 若點(diǎn) 且 則令

6、 若點(diǎn) 且 則令 在這種定義下， 一定不屬于 ，若否， ,則得到一條從 到 的鏈 ，規(guī)定 到 為鏈 的方向，鏈上與 方向一致的邊叫前向邊，與 方向相反的邊稱為后向邊，即 如圖5-42中 為前向邊 為后向邊。 根據(jù) 的定義， 中的前向邊 上必有 ，后向邊上必有0ijfijijfc,ijv vS32,v v12,v vtvsvtvsvtvSStvjvS0,jif,ivSjvS,ijijfc,ivS;svSSf7 令 當(dāng) 為前向邊 當(dāng) 為后向邊 取 ，顯然 。 我們把 修改為 ： 為 上前向邊 為 后向邊 其余 不難驗(yàn)證 仍為可行流（即滿足容量限制條件與平衡條件），但是 的總流量等于 的流加 ，這與

7、 為最大流矛盾，所以 不屬于 。Stvff1f1f,ijv v,ijv v1ijijijffff1ff0 minij,ijv v,ijv vijijijijcff8 令 ，則 。 于是得到一個(gè)割集 ，對(duì)割集中的邊 顯然有 但流量W又滿足 所以最大流的流量等于最小割的容量，定理得到證明。 定義22 容量網(wǎng)絡(luò)G，若 為網(wǎng)絡(luò)中從 到 的一條鏈，給 定向?yàn)閺?到 , 上的邊凡與 同向稱為前向邊，凡與 反向稱為后向邊，其集合分別用和 表示，f是一個(gè)可行流，如果滿足tvSvtvSv,ijijijJiijvSvSvSvSWffc,0,ijijijjicvSvSfvSvS,ijv v,SStvSVSS9 則稱

8、 為從 到 的（關(guān)于f的）可增廣鏈。 推論 可行流f是最大流的充要條件是不存在從 到 的（關(guān)于f的）可增廣鏈。 可增廣鏈的實(shí)際意義是：沿著這條鏈從 到 輸送流，還有潛力可挖，只需按照定理證明中的調(diào)整方法，就可以把流量提高，調(diào)整后的流，在各點(diǎn)仍滿足平衡條件及容量限制條件，即仍為可行流。這樣就得到了一個(gè)尋求最大流的方法：從一個(gè)可行流開始，尋求關(guān)于這個(gè)可行流的可增廣鏈，若存在，則可以經(jīng)過調(diào)整，得到一個(gè)新的可行流，其流量比原來(lái)的可行流要大，重復(fù)這個(gè)過程，直到不存在關(guān)于該流的可增廣鏈時(shí)就得到了最大流。tvSvtvSvtvSv0,0,ijijijijijijfcv vcfv v10 三、求最大流的標(biāo)號(hào)算法

9、 設(shè)已有一個(gè)可行流f，標(biāo)號(hào)的方法可分為兩步：第 1步是標(biāo)號(hào)過程，通過標(biāo)號(hào)來(lái)尋找可增廣鏈；第2 步是調(diào)整過程，沿可增廣鏈調(diào)整f以增加流量。 1.標(biāo)號(hào)過程 （1）給發(fā)點(diǎn)以標(biāo)號(hào) （2）選擇一個(gè)已標(biāo)號(hào)的頂點(diǎn) ，對(duì)于 的所有 未標(biāo)號(hào)的鄰接點(diǎn) 按下列規(guī)則處理： a) 若邊 ，且 則令 ， 并給以標(biāo)號(hào) 。 b) 若邊 ，且 時(shí)，令 并給以標(biāo)號(hào), ,ijvjvmin,jijjiicfijijfc,ijv vE,iivmin,jjiif0,jif,ijv vEjviviv11 （3）重復(fù)（2）直到收點(diǎn) 被標(biāo)號(hào)或不再有頂點(diǎn)可標(biāo)號(hào)時(shí)為止。 如若 得到標(biāo)號(hào)，說明存在一條可增廣鏈，轉(zhuǎn)（第2步）調(diào)整過程。若 未獲得標(biāo)號(hào)，

10、標(biāo)號(hào)過程已無(wú)法進(jìn)行時(shí)，說明f已是最大流。 2. 調(diào)整過程 若 是可增廣鏈上的前向邊 （1）令 若 是可增廣鏈上的后向邊 若 不存在可增廣鏈上 （2）去掉所有標(biāo)號(hào)，回到第1步，對(duì)可行流 重新標(biāo)號(hào)。f ,ijv v,ijv v,ijv vjiijjijifffftvtvtv12 例5.17 圖5-43表明一個(gè)網(wǎng)絡(luò)及初始可行流，每條邊上的有序數(shù)表示 ，求這個(gè)網(wǎng)絡(luò)的最大流。 先給 標(biāo)以 。 檢查 的鄰接點(diǎn) 發(fā)現(xiàn)點(diǎn) 滿足 且 令 ，給 以標(biāo)號(hào) 。同理給 點(diǎn)以標(biāo)號(hào) 。 檢查 點(diǎn)的尚未標(biāo)號(hào)的鄰接點(diǎn) 發(fā)現(xiàn) 滿足 且 令 給 以標(biāo)號(hào) 。2,2v5v5min 3,22,v252503,fc25,v vE5v56,

11、v v2v,1sv3v2v2min 2,2v 2224,ssfc2,sv vE2v123,v v vsv, sv,ijijcf,1sv13 檢查與 點(diǎn)鄰接的未標(biāo)號(hào)點(diǎn)有 ，發(fā)現(xiàn) 點(diǎn)滿足 且 ，令 則給 點(diǎn)以標(biāo)號(hào) 。 點(diǎn)未標(biāo)號(hào)，與 鄰接，邊 且 所以令 給 以標(biāo) 號(hào) 。 類似前面的步驟，可由 得到標(biāo)號(hào) 。 由于 已得到標(biāo)號(hào)，說明存在增廣鏈，所以標(biāo)號(hào)過程結(jié)束，見圖5-44。tv4,2v4vtv1,2v4v4min 3,22,v141425,fc14,v vE1v4v5,2v1v1min 3,22,v1530f15,v vE1v1,tv v5v14 轉(zhuǎn)入調(diào)整過程，令 為調(diào)整量，從 點(diǎn)開始，由逆增廣鏈方

12、向按標(biāo)號(hào) 找到點(diǎn)，令 。 再由 點(diǎn)標(biāo)號(hào) 找到前一個(gè)點(diǎn) ，并令 。按 點(diǎn)標(biāo)號(hào)找到點(diǎn) 。 由于標(biāo)號(hào)為 為反向邊，令 由 點(diǎn)的標(biāo)號(hào)在找到 ，令 。 由 點(diǎn)找到 ，令 調(diào)整過程結(jié)束，調(diào)整中的可增廣鏈見圖5-44，調(diào)整后的可行流見圖5-45。222ssff sv2v25252ff 2v5v15152ff 551,vv v5v1v14142ff 1v1,2v4v442ttff 4v4,2vtv2vt15 重新開始標(biāo)號(hào)過程，尋找可增廣鏈，當(dāng)標(biāo)到 點(diǎn)為 以后，與 點(diǎn)鄰接的 點(diǎn)都不滿足標(biāo)號(hào)條件，所以標(biāo)號(hào)無(wú)法再繼續(xù)，而 點(diǎn)并為得到標(biāo)號(hào)，如圖5-45。 這時(shí) ，即為最大流的流量，算法結(jié)束。 用標(biāo)號(hào)法在得到最大流的同

13、時(shí)，可得到一個(gè)最小割。即圖5-45中虛線所示。 標(biāo)號(hào)點(diǎn)集合為s，即 未標(biāo)號(hào)點(diǎn)集合為 此時(shí)割集 1236,ssS Sv vv vv v12456,tSv v v v v v3,SSv v12345611ssstttWfffffftv126,v v v3,sv v,1sv3v16 割集容量 ，與最大流的流量相等。 由此也可以體會(huì)到最小割的意義，網(wǎng)絡(luò)從發(fā)點(diǎn)到收點(diǎn)的各 通路中，由容量決定其通過能力，最小割則是這此路中的 咽喉部分，或者叫瓶口，其容易最小，它決定了整個(gè)網(wǎng)絡(luò) 的最大通過能力。要提高整個(gè)網(wǎng)絡(luò)的運(yùn)輸能力，必須首先 改造這個(gè)咽喉部份的通過能力。 求最大流的標(biāo)號(hào)算法還可用于解決多發(fā)點(diǎn)多收點(diǎn)網(wǎng)絡(luò)的最

14、 大劉問題，設(shè)容量網(wǎng)絡(luò)G有若干發(fā)點(diǎn) ；若干個(gè) 收點(diǎn) 可以添加兩個(gè)新點(diǎn) ，用容量為 的有 向邊分別連結(jié) 得到新的網(wǎng) 絡(luò) ， 為只有一個(gè)發(fā)點(diǎn) 一個(gè)收點(diǎn) 的網(wǎng)絡(luò)，求解 的 最大流問題即可得到G的解，如圖5-46。1236,11ssC S ScccGtv,svGG1212,smntvx xxy yyv與與,stv v12,ny yy12,mx xx17 四、最大匹配問題四、最大匹配問題 考慮工作分配問題。有n個(gè)工人，m件工作，每個(gè)工人能 力不同，各能勝任其中某幾項(xiàng)工作。假設(shè)每件工作只需要 一人坐，每人只做一件工作，怎樣分配才能盡量的工作有 人做，更多的人有工作？ 這個(gè)問題可以用土的語(yǔ)言描述，如圖5-4

15、7。其中 表示工作，邊 個(gè)人能勝任第 項(xiàng)工作，這樣就得到了一個(gè)二部圖 G，用點(diǎn)集X表示 ，點(diǎn)集Y表示 ， 二部圖 。上述的工作分配問題就是要在途G 中找一個(gè)邊集E的子集，使得集中任何兩條邊沒有公共端 點(diǎn)，最好的方案就是要使此邊集的邊數(shù)盡可能多，這就是 匹配問題。(, ,)GX Y E12 ,my yy12 ,nx xxjy( ,)ijix yx表示第1212,nmx xxy yy表示工人18 定義定義2323 二部圖 ，M是邊集E的子集，若M中的任意兩條邊都沒有公共端點(diǎn)，則稱M為圖G的一個(gè)匹配（也稱對(duì)集）。 M中任意條邊的端點(diǎn)v稱為（關(guān)于M的）飽和點(diǎn)，G中其他定點(diǎn)稱為非飽和點(diǎn)。 若不存在另一條

16、匹配 ，則稱M為最大匹配。 例如圖5-48種用粗線標(biāo)出的各邊組成圖G的一個(gè)匹配 ，且為最大匹配。圖5-48還有另一最大匹配由邊 組成，即一個(gè)土的最大匹配中所含邊數(shù)是確定的，但匹配方案可以不同。11253443( ,),(,),(,),(,)x yxyxyxy11253243( ,),(,),(,),(,)Mx yxyxyxy1MM1使得 M(, ,)GX Y E19 二部圖中最大匹配問題，可以化為最大流問題。在二部圖中增加兩個(gè)新點(diǎn) 分別作為發(fā)點(diǎn)、收點(diǎn)，并擁有向邊把他們與原二部圖中頂點(diǎn)相連，另全部邊上的容量均為1。那么當(dāng)這個(gè)網(wǎng)絡(luò)的流達(dá)到最大時(shí)，如果 上的流量為1，就讓 工作，這樣的方案就是最大匹

17、配的方案。 例5.18 設(shè)有5位待業(yè)者，5項(xiàng)工作，他們各自能勝任工作情況如圖5-49所示，要求設(shè)計(jì)一個(gè)新業(yè)方案，使盡量多的人能就業(yè)。 解 按前述方法增加虛擬的發(fā)、收點(diǎn) ，用求最大流的標(biāo)號(hào)法求解得到圖5-49，在圖中略去容量，只標(biāo)出流量。邊 上的流量都是1，所以讓 工作可得最大就業(yè)方案，即最多可以安排四個(gè)人就業(yè)。12352154,x x x xyy yy分別干12213554( ,),(,),(,),(,)x yxyx yxy,stv vijxy作( ,)iix y1,vvs20 例5.19 有5批貨物，要用船只從 地。規(guī)定每批貨物出發(fā)日期如表5-4所示，又知船只航行所需時(shí)間（天）如表5-5所示

18、。每批貨物只需一條船裝運(yùn)，船只在空載和重載時(shí)航行時(shí)間相同，要求制定一個(gè)計(jì)劃，以最小的船只完成這5項(xiàng)運(yùn)輸任務(wù)。 設(shè) 分別為每項(xiàng)運(yùn)輸任務(wù)的出發(fā)日期 完成日期。則由表5-4和表5-5知：111222232315721013312134135810iiiabxyxyxyxyxy任務(wù)(1,2,3,4,5 )ix,iia b12123,x xy yy地分別運(yùn)往21 還可以求出第i項(xiàng)運(yùn)輸任務(wù)到j(luò)項(xiàng)運(yùn)輸任務(wù)所需的轉(zhuǎn)移時(shí)間，用 表示。如第一項(xiàng)任務(wù)是從 地，第二項(xiàng)任務(wù)是由 地，其轉(zhuǎn)移時(shí)間就是船只要由 地所需的時(shí)間，由表5-5知需2天，即 。類似可求出；1314152123242531323435414243455

19、15253541113111331122222222ttttttttttttttttttt122t11yx地返回12xy地運(yùn)貨到11xy地運(yùn)貨到(1,2,3,4,5;1,2,3,4,5)ijtij22 做一個(gè)二部圖，點(diǎn)集X與Y都表示1，2，3，4，5五項(xiàng)任務(wù)，點(diǎn)i，j間有邊的條件是第i件任務(wù)完成后可以轉(zhuǎn)去作第j鍵，即滿足 者，如圖5-50。如X集中點(diǎn)1到Y(jié)集中點(diǎn)2有邊是因?yàn)?10，滿足7+210，也即一條船于5日出發(fā)完成第一項(xiàng)運(yùn)貨任務(wù)，7日到達(dá)目的地 ，空船2天返回 地還來(lái)得及于10日再去作第二次運(yùn)輸任務(wù)。求出上述二部圖的一個(gè)最大匹配 。如 ：（1，2），（4，5），（5，3），說明一條船可以

20、完成任務(wù)1后接著完成任務(wù)2，另一條船則可以連續(xù)完成任務(wù)4、任務(wù)5、任務(wù)3，即所需最少船只數(shù)為 。2|5 MMM1x1y11227,2,bta而iijjbta23第五節(jié) 最小費(fèi)用流問題 上一節(jié)討論的尋求網(wǎng)絡(luò)最大流問題，只考慮了流的數(shù)量， 沒有考慮流的費(fèi)用。實(shí)際上許多問題要考慮流的費(fèi)用最小 問題。 最小費(fèi)用流問題的一般提法：已知容量網(wǎng)絡(luò)G=(V,E,C), 每條邊 除了已給的容量 外還，給出了單位流量的 費(fèi)用 ，記G=(V,E,C,d)。求G的一個(gè)可行流 使得流量 ，且總費(fèi)用 最小 特別地，當(dāng)要求 為最大流量時(shí)，此問題即為最小費(fèi)用最 大流問題。 最小費(fèi)用流問題的常用算法有兩種：（1）原始算法，（2

21、）對(duì)偶算法。下面只介紹第二種算法，本算法是由性交算法。fEvvijijjifdfd),()(vfW)(ijff )0(ijdijcjivv ,24 定義 24 已知網(wǎng)絡(luò)G=(V,E,C ,d)， 是G上的一 份可行流， 為從 到 的（關(guān)于 的）可增廣 鏈， 稱為鏈 的費(fèi)用。 如圖5-51所示的可增廣鏈 中， 邊上權(quán)為費(fèi)用 ，則鏈 的費(fèi)用 =（3+4+1+6）-（5+7）=2。 若 是從 到 所有可增廣鏈中費(fèi)用最小的鏈， 則稱 為最小費(fèi)用可增廣鏈。*tvsv*)(dijd),(),(:4512vvvv),(),(),(),(:543321tsvvvvvvvvijijddd)(ftvsvf25 對(duì)

22、偶算法的基本思路： 限制奧一個(gè)流量為 的最小費(fèi)用流 ，后然尋找從 到 可廣增鏈 ，用最大流方法將 調(diào)整到 ，使 流量為 ，并保證 是在 流量下的最小費(fèi)用流，不斷進(jìn)行到 為止。 定理 12 若 是流量為 的最小費(fèi)用流， 是關(guān)于 的從 到 的一條最小費(fèi)用可增廣鏈，則 經(jīng)過 調(diào)整流量 得到新可流量 ，一定是流量為 的可行流中的最小費(fèi)用。 由于 就是流量為0的最小費(fèi)用流，所以初始最小費(fèi)用流可以取 ，余下的問題是如何尋找關(guān)于f的最小費(fèi)用可增廣鏈。為了計(jì)算方便：我們構(gòu)造長(zhǎng)度網(wǎng)絡(luò)。0)0(f0, 0fdij)( fW)(fffftvsvf)( fWfvfWk)()()(0fW)1 (f)(0fW)1 (f)

23、1(f)0(ftvsv)0(f0)(0fW26 定義25 對(duì)網(wǎng)絡(luò)G=（V，E，C，d），有可行流 f，保持原網(wǎng)絡(luò)各點(diǎn)，每條邊用兩條方向相反的有 向邊代替，各邊的權(quán) 按如下規(guī)則： （1）當(dāng)邊 ，令 （其中 的意義是：這條邊已飽和，不能增大流量，否則要花費(fèi)很高的代價(jià)，實(shí)際無(wú)法實(shí)現(xiàn)，因此權(quán)為 的邊可從網(wǎng)絡(luò)中去掉。） （2）當(dāng)邊 為原來(lái)G中邊 的反向邊，令 （這里 的意義是此邊流量已減少到0，不能再減少，權(quán)為 的邊也可以去掉。）00ijijijjiffdl當(dāng)當(dāng)),(jivv),(ijvvijijijijijijcfcfdl當(dāng)當(dāng)Evvji),(ijl27 這樣得到的網(wǎng)絡(luò) 稱為長(zhǎng)度網(wǎng)絡(luò)（將費(fèi)用看成長(zhǎng)度）。 顯然在G中求關(guān)于f的最小費(fèi)用可增廣鏈等價(jià)于在長(zhǎng)度網(wǎng)絡(luò) 中求從 到 的最短路。 對(duì)偶算法的基本步驟如下