計算機算法設(shè)計與實現(xiàn) 王曉東主編第三版 PPT第8章 線性規(guī)劃與網(wǎng)絡(luò)流

1、1 學(xué)習(xí)要點學(xué)習(xí)要點 理解線性規(guī)劃算法模型 掌握解線性規(guī)劃問題的單純形算法 理解網(wǎng)絡(luò)與網(wǎng)絡(luò)流的基本概念 掌握網(wǎng)絡(luò)最大流的增廣路算法 掌握網(wǎng)絡(luò)最大流的預(yù)流推進算法 掌握網(wǎng)絡(luò)最小費用流的消圈算法 掌握網(wǎng)絡(luò)最小費用流的最小費用路算法 掌握網(wǎng)絡(luò)最小費用流的網(wǎng)絡(luò)單純形算法 第8章 線性規(guī)劃與網(wǎng)絡(luò)流 2 8.1 線性規(guī)劃問題和單純形算法線性規(guī)劃問題和單純形算法 線性規(guī)劃問題及其表示線性規(guī)劃問題及其表示 線性規(guī)劃問題可表示為如下形式： s.t. ) 1 . 8(max 1 n j jjx c )5 . 8(, 2 , 10 )4 . 8(, 1 ) 3 . 8(, 1 )2 . 8(, 2 , 1 3212

2、1 1 211 1 1 1 ntx mmmmmkbxa mmmjbxa mibxa t n t ktkt n t jtjt n t itit 3 變量滿足約束條件(8.2)-(8.5)式的一組值稱為線性規(guī)劃問題的一個可行解可行解。 所有可行解構(gòu)成的集合稱為線性規(guī)劃問題的可行區(qū)域可行區(qū)域。 使目標(biāo)函數(shù)取得極值的可行解稱為最優(yōu)解最優(yōu)解。 在最優(yōu)解處目標(biāo)函數(shù)的值稱為最優(yōu)值最優(yōu)值。 有些情況下可能不存在最優(yōu)解。 通常有兩種情況： (1)根本沒有可行解，即給定的約束條件之間是相互排斥的，可行區(qū)域為空集； (2)目標(biāo)函數(shù)沒有極值，也就是說在n 維空間中的某個方向上，目標(biāo)函數(shù)值可以無限增 大，而仍滿足約束條

3、件，此時目標(biāo)函數(shù)值無界。 4 這個問題的解為 (x1,x2,x3,x4) = (0,3.5,4.5,1)；最優(yōu)值為16。 4321 3maxxxxxz 12 9 072 182 432 4321 42 31 xxx xxxx xx xx 4 , 3 , 2, 10ixi 5 線性規(guī)劃基本定理線性規(guī)劃基本定理 約束條件(8.2)-(8.5)中n個約束以等號滿足的可行解稱為線性規(guī)劃問題的基本可行解基本可行解。 若nm，則基本可行解中至少有n-m個分量為0，也就是說，基本可行解中最多有m個 分量非零。 線性規(guī)劃基本定理：線性規(guī)劃基本定理：如果線性規(guī)劃問題有最優(yōu)解，則必有一基本可行最優(yōu)解。 上述定理的

4、重要意義在于，它把一個最優(yōu)化問題轉(zhuǎn)化為一個組合問題，即在(8.2) -(8.5) 式的m+n個約束條件中，確定最優(yōu)解應(yīng)滿足其中哪n個約束條件的問題。 由此可知，只要對各種不同的組合進行測試，并比較每種情況下的目標(biāo)函數(shù)值，直到 找到最優(yōu)解。 Dantzig于1948年提出了線性規(guī)劃問題的單純形算法。 單純形算法的特點是： （1）只對約束條件的若干組合進行測試，測試的每一步都使目標(biāo)函數(shù)的值增加； （2）一般經(jīng)過不大于m或n次迭代就可求得最優(yōu)解。 6 約束標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形算法約束標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形算法 當(dāng)線性規(guī)劃問題中沒有不等式約束(8.2)和(8.4)式，而只有等式約束(8.3)

5、和變量非負(fù)約 束(8.5)時，稱該線性規(guī)劃問題具有標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式。 為便于討論，不妨先考察一類更特殊的標(biāo)準(zhǔn)形式線性規(guī)劃問題。這一類線性規(guī)劃問題 中，每一個等式約束中，至少有一個變量的系數(shù)為正，且這個變量只在該約束中出現(xiàn)。 在每一約束方程中選擇一個這樣的變量，并以它作為變量求解該約束方程。這樣選出 來的變量稱為左端變量或基本變量基本變量，其總數(shù)為m個。剩下的n-m個變量稱為右端變量或 非基本變量非基本變量。 這一類特殊的標(biāo)準(zhǔn)形式線性規(guī)劃問題稱為約束標(biāo)準(zhǔn)型線性規(guī)劃問題約束標(biāo)準(zhǔn)型線性規(guī)劃問題。 雖然約束標(biāo)準(zhǔn)型線性規(guī)劃問題非常特殊，但是對于理解線性規(guī)劃問題的單純形算法是 非常重要的。 稍后將看到，任

6、意一個線性規(guī)劃問題可以轉(zhuǎn)換為約束標(biāo)準(zhǔn)型線性規(guī)劃問題。 7 532 23maxxxxz 10834 1242 723 5326 324 5321 xxxx xxx xxxx 6 , 5 , 4 , 3 , 2, 10ixi x2x3x5 z0-13-2 x173-12 x412-240 x610-438 8 任何約束標(biāo)準(zhǔn)型線性規(guī)劃問題，只要將所有非基本變量都置為0，從約束方程式中解出滿 足約束的基本變量的值，可求得一個基本可行解。 單純形算法的基本思想就是從一個基本可行解出發(fā)，進行一系列的基本可行解的變換。 每次變換將一個非基本變量與一個基本變量互調(diào)位置，且保持當(dāng)前的線性規(guī)劃問題是一個 與原問題

7、完全等價的標(biāo)準(zhǔn)線性規(guī)劃問題。 基本可行解x=(7,0,0,12,0,10)。 單純形算法的第單純形算法的第1步：步：選出使目標(biāo)函數(shù)增加的非基本變量作為入基變量入基變量。 查看單純形表的第1行（也稱之為z行）中標(biāo)有非基本變量的各列中的值。 選出使目標(biāo)函數(shù)增加的非基本變量作為入基變量。 z行中的正系數(shù)非基本變量都滿足要求。 在上面單純形表的z行中只有1列為正，即非基本變量相應(yīng)的列，其值為3。 選取非基本變量x3作為入基變量。 單純形算法的第單純形算法的第2步：步：選取離基變量離基變量。 在單純形表中考察由第1步選出的入基變量所相應(yīng)的列。 在一個基本變量變?yōu)樨?fù)值之前，入基變量可以增到多大。 9 如果

8、入基變量所在的列與基本變量所在行交叉處的表元素為負(fù)數(shù)，那么該元素將不受任何 限制，相應(yīng)的基本變量只會越變越大。 如果入基變量所在列的所有元素都是負(fù)值，則目標(biāo)函數(shù)無界，已經(jīng)得到了問題的無界解。 如果選出的列中有一個或多個元素為正數(shù)，要弄清是哪個數(shù)限制了入基變量值的增加。 受限的增加量可以用入基變量所在列的元素（稱為主元素）來除主元素所在行的“常數(shù)列” （最左邊的列）中元素而得到。所得到數(shù)值越小說明受到限制越多。 應(yīng)該選取受到限制最多的基本變量作為離基變量，才能保證將入基變量與離基變量互調(diào)位 置后，仍滿足約束條件。 上例中，惟一的一個值為正的z行元素是3，它所在列中有2個正元素，即4和3。 min

9、12/4,10/3=4，應(yīng)該選取x4為離基變量； 入基變量x3取值為3。 單純形算法的第單純形算法的第3步：轉(zhuǎn)軸變換步：轉(zhuǎn)軸變換。 轉(zhuǎn)軸變換的目的是將入基變量與離基變量互調(diào)位置。 給入基變量一個增值，使之成為基本變量； 修改離基變量，讓入基變量所在列中，離基變量所在行的元素值減為零，而使之成為非基 本變量。 10 解離基變量所相應(yīng)的方程，將入基變量x3用離基變量x4表示為 再將其代入其他基本變量和所在的行中消去x3 ， 代入目標(biāo)函數(shù)得到 形成新單純形表 3 4 1 2 1 423 xxx 18 4 3 2 5 102 4 1 2 5 5426 5421 xxxx xxxx 542 2 4 3

10、2 1 9xxxz x2x4x5 z91/2 -3/4 -2 x1105/21/22 x33-1/21/40 x61-5/2-3/48 11 單純形算法的第單純形算法的第4步：步：轉(zhuǎn)回并重復(fù)第1步，進一步改進目標(biāo)函數(shù)值。 不斷重復(fù)上述過程，直到z行的所有非基本變量系數(shù)都變成負(fù)值為止。這表明目標(biāo)函數(shù)不 可能再增加了。 在上面的單純形表中，惟一的值為正的z行元素是非基本變量x2相應(yīng)的列，其值為1/2。 因此，選取非基本變量x2作為入基變量。 它所在列中有惟一的正元素5/2，即基本變量x1相應(yīng)行的元素。 因此，選取x1為離基變量。 再經(jīng)步驟3的轉(zhuǎn)軸變換得到新單純形表。 新單純形表z行的所有非基本變量

11、系數(shù)都變成負(fù)值，求解過程結(jié)束。 整個問題的解可以從最后一張單純形表的常數(shù)列中讀出。 目標(biāo)函數(shù)的最大值為11； 最優(yōu)解為：x*=(0,4,5,0,0,11)。 x1x4x5 z11-1/5 -4/5 - 12/5 x245/21/104/5 x351/53/102/5 x6111-1/210 12 單純形算法計算步驟單純形算法計算步驟 單純形算法的計算過程可以用單純形表的形式歸納為一系列基本矩陣運算。 主要運算為轉(zhuǎn)軸變換，該變換類似解線性方程組的高斯消去法中的消元變換。 單純形表：單純形表： 為基本變量， 為非基本變量。 基本變量下標(biāo)集為B=1,2,m； 非基本變量下標(biāo)集為N=m+1,m+2,n

12、； 當(dāng)前基本可行解為（ ）。 xm+1xm+2xn zc0cm+1cm+2cn x1b1a1m+1a1m+2a1n x2b2a2m+1a2m+2a2n xmbmamm+1amm+2amn m xxx, 21 nmm xxx, 21 0 , 0 , 21 m bbb 13 單純形算法計算步驟單純形算法計算步驟如下： 步驟步驟1：選入基變量選入基變量。 如果所有cj0，則當(dāng)前基本可行解為最優(yōu)解，計算結(jié)束。 否則取ce0相應(yīng)的非基本變量xe為入基變量。 步驟步驟2：選離基變量選離基變量。 對于步驟1選出的入基變量xe ，如果所有aie0 ，則最優(yōu)解無界，計算結(jié)束。 否則計算 選取基本變量xk為離基變

13、量。 新的基本變量下標(biāo)集為 新的非基本變量下標(biāo)集為 步驟步驟3：作轉(zhuǎn)軸變換作轉(zhuǎn)軸變換。 新單純形表中各元素變換如下。 ke k ie i a a b a b ie 0 min keBB ekNN 14 （8.10） （8.11） （8.12） （8.13） 步驟步驟4：轉(zhuǎn)步驟1。 ke k e ke k iei i a b b Bi a b abb ke ie ik ke kj ieij ij a a a NjBi a a aaa, ke ek ke kj ej a a Nj a a a 1 ke e k ke ki ei i a c c Ni a a ccc 15 將一般問題轉(zhuǎn)化為約束標(biāo)準(zhǔn)型

14、將一般問題轉(zhuǎn)化為約束標(biāo)準(zhǔn)型 有幾種巧妙的辦法可以將一般的線性規(guī)劃問題轉(zhuǎn)換為約束標(biāo)準(zhǔn)型線性規(guī)劃問題。 首先，需要把(8.2)或(8.4)形式的不等式約束轉(zhuǎn)換為等式約束。 具體做法是，引入松弛變量松弛變量，利用松弛變量的非負(fù)性，將不等式轉(zhuǎn)化為等式。 松馳變量記為yi，共有m1+m3個。 在求解過程中，應(yīng)當(dāng)將松弛變量與原來變量同樣對待。求解結(jié)束后，拋棄松弛變量。 注意松弛變量前的符號由相應(yīng)的原不等式的方向所確定。 12 9 072 182 432 4321 42 31 xxx xxxx xx xx 12 9 072 182 3432 4321 242 131 yxxx xxxx yxx yxx 16

15、 為了進一步構(gòu)造標(biāo)準(zhǔn)型約束，還需要引入m個人工變量人工變量，記為zi。 至此，原問題已經(jīng)變換為等價的約束標(biāo)準(zhǔn)型線性規(guī)劃問題。 對極小化線性規(guī)劃問題，只要將目標(biāo)函數(shù)乘以-1即可化為等價的極大化線性規(guī)劃問題。 12 9 072 182 34324 43213 2422 1311 yxxxz xxxxz yxxz yxxz 17 一般線性規(guī)劃問題的一般線性規(guī)劃問題的2階段單純形算法階段單純形算法 引入人工變量后的線性規(guī)劃問題與原問題并不等價，除非所有zi都是0 。 為了解決這個問題，在求解時必須分2個階段進行。 第一階段用一個輔助目標(biāo)函數(shù) 替代原來的目標(biāo)函數(shù)。 這個線性規(guī)劃問題稱為原線性規(guī)劃問題所相

16、應(yīng)的輔助線性規(guī)劃問題。 對輔助線性規(guī)劃問題用單純形算法求解。 如果原線性規(guī)劃問題有可行解，則輔助線性規(guī)劃問題就有最優(yōu)解，且其最優(yōu)值為0，即所 有zi都為0。 在輔助線性規(guī)劃問題最后的單純形表中，所有zi均為非基本變量。 劃掉所有zi相應(yīng)的列，剩下的就是只含xi和yi的約束標(biāo)準(zhǔn)型線性規(guī)劃問題了。 單純形算法第一階段的任務(wù)就是構(gòu)造一個初始基本可行解。 單純形算法第二階段的目標(biāo)是求解由第一階段導(dǎo)出的問題。 此時要用原來的目標(biāo)函數(shù)進行求解。 如果在輔助線性規(guī)劃問題最后的單純形表中， zi不全為0，則原線性規(guī)劃問題沒有可行解， 從而原線性規(guī)劃問題無解。 m i i zz 1 18 退化情形的處理退化情形

17、的處理 用單純形算法解一般的線性規(guī)劃問題時，可能會遇到退化的情形，即在迭代計算的某一步 中，常數(shù)列中的某個元素的值變成0，使得相應(yīng)的基本變量取值為0。 如果選取退化的基本變量為離基變量，則作轉(zhuǎn)軸變換前后的目標(biāo)函數(shù)值不變。在這種情況 下，算法不能保證目標(biāo)函數(shù)值嚴(yán)格遞增，因此，可能出現(xiàn)無限循環(huán)。 考察下面的由Beale在1955年提出的退化問題的例子。 按照2階段單純形算法求解該問題將出現(xiàn)無限循環(huán)。 4321 6 2 1 20 4 3 maxxxxxz 1 03 2 1 12 2 1 098 4 1 3 4321 4321 x xxxx xxxx 4 , 3 , 2, 10ixi 19 Bland

18、提出避免循環(huán)的一個簡單易行的方法。 Bland提出在單純形算法迭代中，按照下面的2個簡單規(guī)則就可以避免循環(huán)。 規(guī)則1：設(shè) ，取xe為入基變量。 規(guī)則2：設(shè) 取xk為離基變量。 算法leave(col)已經(jīng)按照規(guī)則2選取離基變量。 選取入基變量的算法enter(objrow) 中只要加一個break語句即可。 0|min j cje ie i a le l a b a b lk ie 0 min|min 20 倉庫租賃問題倉庫租賃問題 某企業(yè)計劃為流通的貨物租賃一批倉庫。必須保證在時間段i=1,2,n，有bi的倉庫容量可 用?，F(xiàn)有若干倉庫源可供選擇。設(shè)cij是從時間段i到時間段j租用1個單位倉庫

19、容量的價格， 1ijn。應(yīng)如何安排倉庫租賃計劃才能滿足各時間段的倉庫需求，且使租賃費用最少。 設(shè)租用時間段i到時間段j的倉庫容量為yij，1ijn。則租用倉庫的總費用為： 在時間段k可用的倉庫容量為： 倉庫租賃問題可表述為下面的線性規(guī)劃問題： ij n i n ij ijy c 1 k i n kj ij y 1 ij n i n ij ijy c 1 min k i k n kj ij by 1 0 ij y 21 設(shè) m=n(n+1)/2； （ ）=（ ）； （ ）=（ ）； 上述線性規(guī)劃問題可表述為n個約束和m個變量的標(biāo)準(zhǔn)線性規(guī)劃問題如下。 nnnn yyyyyyy, 223221121

20、1 m xxx, 21 nnnn ccccccc, 2232211211 m ddd, 21 xd T min bAx 0 x 1001001000 0000 1101100 01111110 0000001111 A 22 8.2 最大網(wǎng)絡(luò)流問題最大網(wǎng)絡(luò)流問題 1 基本概念和術(shù)語基本概念和術(shù)語 （1） 網(wǎng)絡(luò)網(wǎng)絡(luò) G是一個簡單有向圖，G=(V,E)，V=1，2，n。 在V中指定一個頂點s，稱為源源和另一個頂點t，稱為匯匯。 有向圖G的每一條邊(v,w)E，對應(yīng)有一個值cap(v,w)0，稱為邊的容量容量。 這樣的有向圖G稱作一個網(wǎng)絡(luò)網(wǎng)絡(luò)。 （2） 網(wǎng)絡(luò)流網(wǎng)絡(luò)流 網(wǎng)絡(luò)上的流流是定義在網(wǎng)絡(luò)的邊集合

21、E上的一個非負(fù)函數(shù)flow=flow(v,w)，并稱flow(v,w)為 邊(v,w)上的流量流量。 23 （3） 可行流可行流 滿足下述條件的流flow稱為可行流可行流： (3.1)容量約束：容量約束：對每一條邊(v,w)E，0flow(v,w)cap(v,w)。 (3.2)平衡約束：平衡約束： 對于中間頂點：流出量=流入量。 即對每個vV(vs,t)有：頂點v的流出量頂點v的流入量=0，即 對于源s：s的流出量s的流入量=源的凈輸出量f，即 對于匯t：t的流入量t的流出量的=匯的凈輸入量f，即 式中f 稱為這個可行流的流量，即源的凈輸出量(或匯的凈輸入量)。 可行流總是存在的。 例如，讓所

22、有邊的流量flow(v,w)=0，就得到一個其流量f=0的可行流(稱為0流)。 0),(),( ),(),( EvwEwv vwflowwvflow fsvflowvsflow EsvEvs ),(),( ),(),( fvtflowtvflow EvtEtv ),(),( ),(),( 24 （4） 邊流邊流 對于網(wǎng)絡(luò)G的一個給定的可行流flow，將網(wǎng)絡(luò)中滿足flow(v,w)=cap(v,w)的邊稱為飽和邊飽和邊； flow(v,w)0的邊稱為 非零流邊非零流邊。當(dāng)邊(v,w)既不是一條零流邊也不是一條飽和邊時，稱為弱流邊弱流邊。 （5） 最大流最大流 最大流問題即求網(wǎng)絡(luò)G的一個可行流fl

23、ow，使其流量f達到最大。即flow滿足： 0flow(v,w)cap(v,w)，(v,w)E；且 （6） 流的費用流的費用 在實際應(yīng)用中，與網(wǎng)絡(luò)流有關(guān)的問題，不僅涉及流量，而且還有費用的因素。此時網(wǎng)絡(luò)的 每一條邊(v,w)除了給定容量cap(v,w)外，還定義了一個單位流量費用cost(v,w)。對于網(wǎng)絡(luò) 中一個給定的流flow，其費用定義為： tvf tsv svf vwflowwvflow,0),(),( Ewv wvflowwvtflowt ),( ),(),(cos)(cos 25 （7） 殘流網(wǎng)絡(luò)殘流網(wǎng)絡(luò) 對于給定的一個流網(wǎng)絡(luò)G及其上的一個流flow，網(wǎng)絡(luò)G關(guān)于流flow的殘流網(wǎng)絡(luò)

24、G*與G有相同 的頂點集V，而網(wǎng)絡(luò)G中的每一條邊對應(yīng)于G*中的1條邊或2條邊。 設(shè)(v,w)是G的一條邊。 當(dāng)flow(v,w)0時，（w,v）是G*中的一條邊，該邊的容量為cap*(w,v)=flow(v,w)； 當(dāng)flow(v,w)cap(v,w)時，(v,w)是G*中的一條邊，該邊的容量為 cap*(v,w)=cap(v,w)-flow(v,w)。 按照殘流網(wǎng)絡(luò)的定義，當(dāng)原網(wǎng)絡(luò)G中的邊(v,w)是一條零流邊時，殘流網(wǎng)絡(luò)G*中有唯一的一 條邊(v,w)與之對應(yīng)，且該邊的容量為cap(v,w)。 當(dāng)原網(wǎng)絡(luò)G中的邊(v,w)是一條飽和邊時，殘流網(wǎng)絡(luò)G*中有唯一的一條邊(w,v)與之對應(yīng)，且 該

25、邊的容量為cap(v,w)。 當(dāng)原網(wǎng)絡(luò)G中的邊(v,w)是一條弱流邊時，殘流網(wǎng)絡(luò)G*中有2條邊(v,w)和(w,v)與之對應(yīng)，這2 條邊的容量分別為cap(v,w) -flow(v,w)和flow(v,w)。 殘流網(wǎng)絡(luò)是設(shè)計與網(wǎng)絡(luò)流有關(guān)算法的重要工具。 26 增廣路算法增廣路算法 1 算法基本思想算法基本思想 設(shè)P是網(wǎng)絡(luò)G中聯(lián)結(jié)源s和匯t的一條路。定義路的方向是從s到t。 將路P上的邊分成2類： 一類邊的方向與路的方向一致，稱為向前邊向前邊。向前邊的全體記為P+。 另一類邊的方向與路的方向相反，稱為向后邊向后邊。向后邊的全體記為P-。 設(shè)flow是一個可行流，P是從s到t的一條路，若P滿足下列

26、條件： （1）在P的所有向前邊(v,w)上，flow(v,w)0，即P-中的每一條邊都是非零流邊。 則稱P為關(guān)于可行流flow的一條可增廣路。 可增廣路是殘流網(wǎng)絡(luò)中一條容量大于0的路。 將具有上述特征的路P稱為可增廣路是因為可以通過修正路P上所有邊流量flow(v,w)將當(dāng)前 可行流改進成一個流值更大的可行流。 27 增流的具體做法是： （1）不屬于可增廣路P的邊(v,w)上的流量保持不變； （2）可增廣路P上的所有邊(v,w)上的流量按下述規(guī)則變化： 在向前邊(v,w)上，flow(v,w)+d； 在向后邊(v,w)上，flow(v,w)-d。 按下面的公式修改當(dāng)前的流。 其中d稱為可增廣量

27、，可按下述原則確定：d取得盡量大，又要使變化后的流仍為可行流。 按照這個原則，d既不能超過每條向前邊(v,w)的cap(v,w)-flow(v,w)，也不能超過每條向后 邊(v,w)的flow(v,w)。 因此d應(yīng)該等于向前邊上的cap(v,w)-flow(v,w)與向后邊上的flow(v,w)的最小值。也就是殘流 網(wǎng)絡(luò)中P的最大容量。 增廣路定理：增廣路定理：設(shè)flow是網(wǎng)絡(luò)G的一個可行流，如果不存在從s到t關(guān)于flow的可增廣路P，則 flow是G的一個最大流。 Pwvwvflow Pwvdwvflow Pwvdwvflow wvflow ),(),( ),(),( ),(),( ),(

28、28 2 算法描述算法描述 最大流的增廣路算法如下。該算法也常稱作Ford Fulkerson算法。 template class MAXFLOW const Graph int s, t,maxf; vector wt; vector st; int ST(int v) const return stv-other(v); void augment(int s, int t) int d = stt-capRto(t); for (int v = ST(t); v != s; v = ST(v) if (stv-capRto(v) capRto(v); stt-addflowRto(t, d

29、); maxf+=d; for ( v = ST(t); v != s; v = ST(v) stv-addflowRto(v, d); bool pfs(); public: MAXFLOW(const Graph maxflow+=maxf; ; 29 3 算法的計算復(fù)雜性算法的計算復(fù)雜性 增廣路算法的效率由下面2個因素所確定。 （1）整個算法找增廣路的次數(shù)； （2）每次找增廣路所需的時間。 給定的網(wǎng)絡(luò)中有n個頂點和m條邊，且每條邊的容量不超過M。 可以證明，在一般情況下，增廣路算法中找增廣路的次數(shù)不超過nM次。 最短增廣路算法在最壞情況下找增廣路的次數(shù)不超過nm/2次。 找1次增廣路最多

30、需要O(m)計算時間。 因此，在最壞情況下最短增廣路算法所需的計算時間為O(nm2) 。 當(dāng)給定的網(wǎng)絡(luò)是稀疏網(wǎng)絡(luò)，即m=O(n)時，最短增廣路算法所需的計算時間為O(n3)。 最大容量增廣路算法在最壞情況下找增廣路的次數(shù)不超過2mlogM次。 由于使用堆來存儲優(yōu)先隊列，找1次增廣路最多需要O(nlogn)計算時間。 因此，在最壞情況下最大容量增廣路算法所需的計算時間為 當(dāng)給定的網(wǎng)絡(luò)是稀疏網(wǎng)絡(luò)時，最大容量增廣路算法所需的計算時間為 )loglog(MnmnO )loglog( 2 MnnO 30 預(yù)流推進算法預(yù)流推進算法 1 算法基本思想算法基本思想 增廣路算法的特點是找到增廣路后，立即沿增廣路

31、對網(wǎng)絡(luò)流進行增廣。 每一次增廣可能需要對最多n-1條邊進行操作。 最壞情況下，每一次增廣需要O(n)計算時間。 有些情況下，這個代價是很高的。下面是一個極端的例子。 31 無論用哪種增廣路算法，都會找到10條增廣路，每條路長為10，容量為1。 共需要10次增廣，每次增廣需要對10條邊進行操作，每條邊增廣1個單位流量。 10條增廣路中的前9個頂點（前8條邊）是完全一樣的。 如果直接將前8條邊的流量增廣10個單位，而只對后面長為2的不同的有向路單獨操作， 就可以節(jié)省許多計算時間。 這就是預(yù)流推進（preflow push )算法的基本思想。 預(yù)流推進算法注重對每一條邊的增流，而不必每次一定對一條增

32、廣路增流。 通常將沿一條邊增流的運算稱為一次推進（push）。 在算法的推進過程中，網(wǎng)絡(luò)流滿足容量約束，但一般不滿足流量平衡約束。 從每個頂點（除s和t外）流出的流量之和總是小于等于流入該頂點的流量之和。 這種流稱為預(yù)流（preflow）。這也是這類算法被稱為預(yù)流推進算法的原因。 下面先給出預(yù)流的嚴(yán)格定義。 給定網(wǎng)絡(luò)G=(V,E)一個預(yù)流預(yù)流是定義在G的邊集E上的一個正邊流函數(shù)。 該函數(shù)滿足容量約束，即對G的每一條邊(v,w)E，滿足0flow(v,w)cap(v,w)。 32 G的每一中間頂點滿足流出量小于或等于流入量。 即對每個vV(vs,t)有 滿足條件 的中間頂點v稱為活頂點活頂點。

33、量 稱為頂點v的存流。 按此定義，源s和匯t不可能成為活頂點。 對網(wǎng)絡(luò)G上的一個預(yù)流，如果存在活頂點，則說明該預(yù)流不是可行流。 預(yù)流推進算法就是要選擇活頂點，并通過把一定的流量推進到它的鄰點，盡可能地將 當(dāng)前活頂點處正的存流減少為0，直至網(wǎng)絡(luò)中不再有活頂點，從而使預(yù)流成為可行流。 如果當(dāng)前活頂點有多個鄰點，那么首先推進到哪個鄰點呢? 由于算法最后的目的是盡可能將流推進到匯點t，因此算法應(yīng)尋求把流量推進到它的鄰 點中距頂點t最近的頂點。 預(yù)流推進算法中用到一個高度函數(shù)h來確定推流邊。 對于給定網(wǎng)絡(luò)G=(V,E)的一個流，其高度函數(shù)h是定義在G的頂點集V上的一個非負(fù)函數(shù)。 該函數(shù)滿足： （1）對于

34、G的殘流網(wǎng)絡(luò)中的每一條邊(u,v)有，h(u) h(v)+1； （2）h(t)=0。 G的殘流網(wǎng)絡(luò)中滿足h(u) = h(v)+1的邊(u,v)稱為G的可推流邊可推流邊。 EvwEwv vwflowwvflow ),(),( ),(),( EvwEwv vwflowwvflow ),(),( ),(),( EwvEvw wvflowvwflow ),(),( ),(),( 33 一般的預(yù)流推進算法一般的預(yù)流推進算法 一般的預(yù)流推進算法的每次迭代是一次推進運算或者一次高度重新標(biāo)號運算。 如果推進的流量等于推流邊上的殘留容量，則稱為飽和推進，否則稱為非飽和推進。 算法終止時，網(wǎng)絡(luò)中不含有活頂點。此

35、時只有頂點s和t的存流非零。此時的預(yù)流實際上 已經(jīng)是一個可行流。 算法預(yù)處理階段已經(jīng)令h(s)=n，而高度函數(shù)在計算過程中不會減少，因此算法在計算過 程中可以保證網(wǎng)絡(luò)中不存在增廣路。 根據(jù)增廣路定理，算法終止時的可行流是一個最大流。 步驟步驟0：構(gòu)造初始預(yù)流flow： 對源頂點s的每條出邊(s,v)令flow(s,v)=cap(s,v)； 對其余邊(u,v)令flow(u,v)=0。構(gòu)造一有效的高度函數(shù)h。 步驟步驟1：如果殘量網(wǎng)絡(luò)中不存在活頂點，則計算結(jié)束，已經(jīng)得到最大流； 否則轉(zhuǎn)步驟2。 步驟步驟2：在網(wǎng)絡(luò)中選取活頂點v。 如果存在頂點v的出邊為可推流邊，則選取一條這樣的可推流邊，并沿此邊

36、推流。 否則令h(v) = minh(w)+1 | (v,w)是當(dāng)前殘流網(wǎng)絡(luò)中的邊，并轉(zhuǎn)步驟1。 34 一般的預(yù)流推進算法并未給出如何選擇活頂點和可推流邊。 不同的選擇策略導(dǎo)致不同的預(yù)流推進算法。 在基于頂點的預(yù)流推進算法中，選定一個活頂點后，算法沿該活頂點的所有推流邊進 行推流運算，直至無可推流邊或該頂點的存變成0時為止。 3 算法的計算復(fù)雜性算法的計算復(fù)雜性 基于頂點的預(yù)流推進算法用一個廣義隊列g(shù)Q存儲當(dāng)前活頂點集合。 廣義隊列可以是通常的FIFO隊列，LIFO棧，隨機化隊列，隨機化棧，或按各種優(yōu)先級 定義的優(yōu)先隊列。 算法的效率與廣義優(yōu)先隊列的選擇密切相關(guān)。 如果選用通常的FIFO隊列，

37、則在最壞情況下，預(yù)流推進算法求最大流所需的計算時間 為O(mn2)，其中m和n分別為圖G的邊數(shù)和頂點數(shù)。 如果以頂點高度值為優(yōu)先級，選用優(yōu)先隊列實現(xiàn)預(yù)流推進算法，則在最壞情況下，求 最大流所需的計算時間為 這個算法也稱為最高頂點標(biāo)號預(yù)流推進算法。 近來已提出許多其它預(yù)流推進算法的實現(xiàn)策略，在最壞情況下算法所需的計算時間已 接近O(mn)。 )( 2 nmO 35 8.3 最小費用流問題最小費用流問題 1 網(wǎng)絡(luò)流的費用網(wǎng)絡(luò)流的費用 在實際應(yīng)用中，與網(wǎng)絡(luò)流有關(guān)的問題，不僅涉及流量，而且還有費用的因素。 網(wǎng)絡(luò)的每一條邊(v,w)除了給定容量cap(v,w)外，還定義了一個單位流量費用cost(v,w

38、)。 對于網(wǎng)絡(luò)中一個給定的流flow，其費用定義為： 2 最小費用流問題最小費用流問題 給定網(wǎng)絡(luò)G，要求G的一個最大用流flow，使流的總費用最小。 3 最小費用可行流問題最小費用可行流問題 給定多源多匯網(wǎng)絡(luò)G，要求G的一個可行流flow，使可行流的總費用最小。 可行流問題等價于最大流問題。最小費用可行流問題也等價于最小費用流問題。 Ewv wvflowwvtflowt ),( ),(),(cos)(cos 36 消圈算法消圈算法 1 算法基本思想算法基本思想 最小費用流問題有關(guān)的算法中，仍然沿用殘流網(wǎng)絡(luò)的概念。 此時，殘流網(wǎng)絡(luò)中邊的費用定義為： int costRto(int v) retu

39、rn from(v) ? -pcost : pcost; 當(dāng)殘流網(wǎng)絡(luò)中的邊是向前邊時，其費用不變。 當(dāng)殘流網(wǎng)絡(luò)中的邊是向后邊時，其費用為原費用的負(fù)值。 由于殘流網(wǎng)絡(luò)中存在負(fù)費用邊，因此殘流網(wǎng)絡(luò)中就不可避免地會產(chǎn)生負(fù)費用圈。 在與最小費用流問題有關(guān)的算法中，負(fù)費用圈是一個重要概念。 最小費用流問題的最優(yōu)性條件最小費用流問題的最優(yōu)性條件 網(wǎng)絡(luò)G的最大流flow是G的一個最小費用流的充分且必要條件是flow所相應(yīng)的殘流網(wǎng)絡(luò) 中沒有負(fù)費用圈。 37 最小費用流的消圈算法最小費用流的消圈算法 步驟步驟0：用最大流算法構(gòu)造最大流flow。 步驟步驟1：如果殘量網(wǎng)絡(luò)中不存在負(fù)費用圈，則計算結(jié)束，已經(jīng)找到最小

40、費用流； 否則轉(zhuǎn)步驟2。 步驟步驟2：沿找到的負(fù)費用圈增流，并轉(zhuǎn)步驟1。 38 3 算法的計算復(fù)雜性算法的計算復(fù)雜性 給定網(wǎng)絡(luò)中有n個頂點和m條邊，且每條邊的容量不超過M，每條邊的費用不超過C。 最大流的費用不超過mCM，而每次消去負(fù)費用圈至少使得費用下降1個單位，因此最 多執(zhí)行mCM次找負(fù)費用圈和增流運算。 用Bellman-Ford算法找1次負(fù)費用圈需要O(mn)計算時間。 最小費用流的消圈算法在最壞情況下需要計算時間)( 2nCM mO 39 最小費用路算法最小費用路算法 1 算法基本思想算法基本思想 消圈算法首先找到網(wǎng)絡(luò)中的一個最大流，然后通過消去負(fù)費用圈使費用降低。 最小費用路算法不

41、用先找最大流，而是用類似于求最大流的增廣路算法的思想，不斷 在殘流網(wǎng)絡(luò)中尋找從源s到匯t的最小費用路，然后沿最小費用路增流，直至找到最小費 用流。 殘流網(wǎng)絡(luò)中從源s到匯t的最小費用路是殘流網(wǎng)絡(luò)中從s到t的以費用為權(quán)的最短路。 殘流網(wǎng)絡(luò)中邊的費用定義為： 當(dāng)殘流網(wǎng)絡(luò)中邊(v,w)是向前邊時，其費用為cost(v,w)； 當(dāng)(v,w)是向后邊時，其費用為-cost(w,v)。 Pwvvwt Pwvwvt wvwt ),(),(cos ),(),(cos ),( 40 最小費用流的最小費用路算法最小費用流的最小費用路算法 步驟步驟0：初始可行0流。 步驟步驟1：如果不存在最小費用路，則計算結(jié)束，已經(jīng)找到最小費用流； 否則用最短路算法在殘流網(wǎng)絡(luò)中找從s到t的最小費用可增廣路，轉(zhuǎn)步驟2。 步驟步驟2：沿找到的最小費用可增廣路增流，并轉(zhuǎn)步驟1。 41 3 算法的計算復(fù)雜性算法的計算復(fù)雜性 算法的主要計算量在于連續(xù)尋找最小費用路并增流。 給定網(wǎng)絡(luò)中有n個頂點和m條邊，且每條邊的容量不超過M，每條邊的費用不超過C。 每次增流至少使得流值增加1個單位，因此最多執(zhí)行M次找最小費用路算法。 如果找1次最小費用路需要s(m,n,C)計算時間，則求最小費用流的最小費用路算法需要 O(Ms(m,n,C)計算時間。 42 網(wǎng)絡(luò)單純形算法網(wǎng)絡(luò)單純形算法 1 算法基本思想算法基本思想