第7章線性規(guī)劃問題與網(wǎng)絡流

1、1學習要點學習要點理解線性規(guī)劃算法模型掌握解線性規(guī)劃問題的單純形算法 理解網(wǎng)絡與網(wǎng)絡流的基本概念掌握網(wǎng)絡最大流的增廣路算法掌握網(wǎng)絡最小費用流的消圈算法第7章 線性規(guī)劃與網(wǎng)絡流2線性規(guī)劃問題和單純形算法線性規(guī)劃問題和單純形算法線性規(guī)劃問題及其表示線性規(guī)劃問題及其表示一般線性規(guī)劃問題可表示為如下形式：一般線性規(guī)劃問題可表示為如下形式： s.t.) 1 . 8(max1njjjxc)5 . 8(, 2 , 10)4 . 8(, 1) 3 . 8(, 1)2 . 8(, 2 , 1321211211111ntxmmmmmkbxammmjbxamibxatntktktntjtjtntitit3變量滿足約

2、束條件變量滿足約束條件(7.2)-(7.5)式的一組值稱為線性規(guī)劃問題的一個式的一組值稱為線性規(guī)劃問題的一個可可行解行解。所有可行解構(gòu)成的集合稱為線性規(guī)劃問題的所有可行解構(gòu)成的集合稱為線性規(guī)劃問題的可行區(qū)域可行區(qū)域。使目標函數(shù)取得極值的可行解稱為使目標函數(shù)取得極值的可行解稱為最優(yōu)解最優(yōu)解。在最優(yōu)解處目標函數(shù)的值稱為在最優(yōu)解處目標函數(shù)的值稱為最優(yōu)值最優(yōu)值。有些情況下可能不存在最優(yōu)解。有些情況下可能不存在最優(yōu)解。根本沒有可行解，可行區(qū)域為空集；根本沒有可行解，可行區(qū)域為空集；目標函數(shù)沒有極值，目標函數(shù)值無界。目標函數(shù)沒有極值，目標函數(shù)值無界。4標準線性規(guī)劃問題描述標準線性規(guī)劃問題描述), 2 ,

3、1(0max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczjmnmnmmnnnnnn約束條件：目標函數(shù)：5將一般線性規(guī)劃問題轉(zhuǎn)化為標準型規(guī)劃問題的方法將一般線性規(guī)劃問題轉(zhuǎn)化為標準型規(guī)劃問題的方法 (1)一般線性規(guī)劃形式中目標函數(shù)如果是求極小值的，即一般線性規(guī)劃形式中目標函數(shù)如果是求極小值的，即 那么，令那么，令 ，則，則， (2)右端常數(shù)項如果小于零，則不等式兩邊同乘以（右端常數(shù)項如果小于零，則不等式兩邊同乘以（-1），將其變成大于），將其變成大于零；同時改變不等號的方向，保證恒等變形。如零；同時改變不等號的方向，保證恒等變形。如

4、2x1+x26，2x1x26。(3)約束條件為大于等于約束時，則在不等式左邊減去一個新的非負變量約束條件為大于等于約束時，則在不等式左邊減去一個新的非負變量將不等式約束改為等式約束。如將不等式約束改為等式約束。如3x12x212，3x12x2x312，x30；(4)約束條件為小于等于約束時，則在左邊加上一個新的非負變量將不等約束條件為小于等于約束時，則在左邊加上一個新的非負變量將不等式約束改為等式約束。如式約束改為等式約束。如x12x28，x12x2x38，x30；(5)無約束的決策變量無約束的決策變量x，即可正可負的變量，則引入兩個新的非負變量，即可正可負的變量，則引入兩個新的非負變量x和和

5、x”，令，令x=-x-x”，其中，其中x0，x”0，將，將x代入線性規(guī)劃模型。代入線性規(guī)劃模型。(6)決策變量決策變量x小于等于小于等于0時，令時，令xx，顯然，顯然x0，將，將x代入線性規(guī)劃代入線性規(guī)劃模型。模型。在在(3)(6)中引入的新的非負變量稱為中引入的新的非負變量稱為松弛變量松弛變量。njjjxcz1minzznjjjxcz1maxmaxminzz6標準型線性規(guī)劃問題的單純形算法標準型線性規(guī)劃問題的單純形算法 單純形法單純形法是指是指1947年數(shù)學家年數(shù)學家George Dantzing(喬治喬治丹捷格丹捷格)發(fā)明發(fā)明的一種求解線性規(guī)劃模型的一般性方法。的一種求解線性規(guī)劃模型的一般

6、性方法。約束標準型線性規(guī)劃問題約束標準型線性規(guī)劃問題為了便于討論，先考察一類特殊的標準形式的線性規(guī)劃為了便于討論，先考察一類特殊的標準形式的線性規(guī)劃問題。在這類問題中，問題。在這類問題中，每個等式約束條件中均至少含有每個等式約束條件中均至少含有一個正系數(shù)的變量，且這個變量只出現(xiàn)在一個約束條件一個正系數(shù)的變量，且這個變量只出現(xiàn)在一個約束條件中。中。將每個約束條件中這樣的變量作為非將每個約束條件中這樣的變量作為非0變量來求解該變量來求解該約束方程。這類特殊的標準形式線性規(guī)劃問題稱為約束約束方程。這類特殊的標準形式線性規(guī)劃問題稱為約束標準型線性規(guī)劃問題。標準型線性規(guī)劃問題。 7基本概念：基本概念：基

7、本變量（基本變量（ m個）：每個約束條件中的系數(shù)為正個）：每個約束條件中的系數(shù)為正且只出現(xiàn)在一個約束條件中的變量。且只出現(xiàn)在一個約束條件中的變量。非基本變量非基本變量(n-m)：除基本變量外的變量全部為：除基本變量外的變量全部為非基本變量。非基本變量?；究尚薪猓簼M足標準形式約束條件的可行解稱基本可行解：滿足標準形式約束條件的可行解稱為基本可行解。由此可知，如果令為基本可行解。由此可知，如果令n-m個非基本個非基本變量等于變量等于0，那么根據(jù)約束條件求出，那么根據(jù)約束條件求出m個基本變個基本變量的值，它們組成的一組可行解為一個基本可行量的值，它們組成的一組可行解為一個基本可行解。解。8線性規(guī)劃

8、基本定理線性規(guī)劃基本定理定理定理1（最優(yōu)解判別定理）若目標函數(shù)中關(guān)于非（最優(yōu)解判別定理）若目標函數(shù)中關(guān)于非基本變量的所有系數(shù)（以下稱檢驗數(shù)）小于等于基本變量的所有系數(shù)（以下稱檢驗數(shù)）小于等于0，則當前基本可行解就是最優(yōu)解。，則當前基本可行解就是最優(yōu)解。定理定理2（無窮多最優(yōu)解判別定理）若目標函數(shù)中（無窮多最優(yōu)解判別定理）若目標函數(shù)中關(guān)于非基本變量的所有檢驗數(shù)小于等于關(guān)于非基本變量的所有檢驗數(shù)小于等于0，同時，同時存在某個非基本變量的檢驗數(shù)等于存在某個非基本變量的檢驗數(shù)等于0，則線性規(guī)，則線性規(guī)劃問題有無窮多個最優(yōu)解。劃問題有無窮多個最優(yōu)解。定理定理3（無界解定理）如果某個檢驗數(shù)（無界解定理）如

9、果某個檢驗數(shù)cj大于大于0，而而xj對應的列向量中所有基本變量的系數(shù)對應的列向量中所有基本變量的系數(shù)a1j,a2j,amj都小于等于都小于等于0，則該線性規(guī)劃問題有，則該線性規(guī)劃問題有無界解。無界解。9約束標準型線性規(guī)劃問題的單純形算法約束標準型線性規(guī)劃問題的單純形算法步驟步驟1：找出基本變量和非基本變量，將目標函數(shù)由：找出基本變量和非基本變量，將目標函數(shù)由非基本變量表示，建立初始單純形表如表非基本變量表示，建立初始單純形表如表7-1所示。所示。表表7-1 初始單純形表初始單純形表110步驟步驟2；判別、檢查目標函數(shù)的所有系數(shù)，即檢驗；判別、檢查目標函數(shù)的所有系數(shù)，即檢驗數(shù)數(shù)cj(j=1,2,

10、n)。（1）如果所有的）如果所有的cj0，則已獲得最優(yōu)解，算法結(jié)，則已獲得最優(yōu)解，算法結(jié)束。束。（2）若在檢驗數(shù)）若在檢驗數(shù)cj中，有些為正數(shù)，但其中某一正中，有些為正數(shù)，但其中某一正的檢驗數(shù)所對應的列向量的各分量均小于等于的檢驗數(shù)所對應的列向量的各分量均小于等于0，則線性規(guī)劃問題無界，算法結(jié)束。則線性規(guī)劃問題無界，算法結(jié)束。（3）若在檢驗數(shù)）若在檢驗數(shù)cj中，有些為正數(shù)且它們所對應的中，有些為正數(shù)且它們所對應的列向量中有正的分量，則轉(zhuǎn)步驟列向量中有正的分量，則轉(zhuǎn)步驟3。步驟步驟3：選入基變量。在所有：選入基變量。在所有cj0的檢驗數(shù)中選取的檢驗數(shù)中選取值最大的一個，記為值最大的一個，記為ce

11、，其對應的非基變量為，其對應的非基變量為xe，對應的列向量為對應的列向量為a1e,a2e,ameT，稱為入基列。，稱為入基列。11步驟步驟4：選離基變量。選?。哼x離基變量。選取“常數(shù)列元素常數(shù)列元素/入基列元入基列元素素”正比值的最小者所對應的基本變量為離基變量，正比值的最小者所對應的基本變量為離基變量，即即 ，選取基本變量，選取基本變量xk為離基變量。為離基變量。步驟步驟5：換基變換（轉(zhuǎn)軸變換）。在單純形表上將：換基變換（轉(zhuǎn)軸變換）。在單純形表上將入基變量和離基變量互換位置，并按照式如下公式入基變量和離基變量互換位置，并按照式如下公式進行各元素的變換后得到一張新的單純形表。轉(zhuǎn)步進行各元素的變

12、換后得到一張新的單純形表。轉(zhuǎn)步驟驟2。kekieiaababiemin012對應入基列位置元素對應入基列位置元素=-原入基列元素原入基列元素/交叉位置元素交叉位置元素（不包括交叉位置）。（不包括交叉位置）。對應離基行位置元素對應離基行位置元素=原離基行元素原離基行元素/交叉位置元素交叉位置元素（不包括交叉位置）。（不包括交叉位置）。交叉位置元素交叉位置元素=原交叉位置元素的倒數(shù)。原交叉位置元素的倒數(shù)。目標函數(shù)的值目標函數(shù)的值=原目標函數(shù)的值原目標函數(shù)的值+同行畫線位置元素同行畫線位置元素同列畫線位置元素同列畫線位置元素/交叉位置的元素。交叉位置的元素。其它位置的元素其它位置的元素=原對應位置的

13、元素原對應位置的元素-同行畫線位置同行畫線位置元素元素同列畫線位置元素同列畫線位置元素/交叉位置的元素交叉位置的元素13例題例題1)1,2,3,40(ix-108x 3x4x12 4x2x-7 2x x-3xx2x3x-xzmin i432 324321432zz)61,2,3,4,5,0(ix10 x8x 3x4x-12 x4x2x-7 2x x-3xx2x3xxzmin i64325 324321432解：將線性規(guī)劃問題轉(zhuǎn)化為約束標準型如下：解：將線性規(guī)劃問題轉(zhuǎn)化為約束標準型如下： 令令14由約束標準形式可知：由約束標準形式可知：x1,x5,x6是基本變量，是基本變量，x2,x3,x4是非

14、基本是非基本變量，建立初始單純形表如表變量，建立初始單純形表如表7-2所示。由此可得，基本可行解所示。由此可得，基本可行解為為X(0)=（7,0,0,0,12,10），），z=0。由表由表7-2可知：可知：x3為入基變量，為入基變量，x5為離基變量，根據(jù)迭代公式得為離基變量，根據(jù)迭代公式得出如表出如表7-3所示的單純形表所示的單純形表3。由。由此可得，基本可行解為此可得，基本可行解為X(1)=（10,0,3,0,0,1）, z=915由表由表7-3可知：可知：x2為入基變量，為入基變量，x1為離基變量，根據(jù)迭代公式迭為離基變量，根據(jù)迭代公式迭代得如表代得如表7-4所示的單純形表所示的單純形表4

15、。由此可得，基本可行解為由此可得，基本可行解為X(2)=（0,4,5,0,0,11）, z=11。同時，。同時，由表由表7-4可知，所有檢驗數(shù)均小可知，所有檢驗數(shù)均小于等于于等于0，故，故X(2)= （0,4,5,0,0,11）為該線性）為該線性規(guī)劃問題的唯一最優(yōu)解，其最優(yōu)規(guī)劃問題的唯一最優(yōu)解，其最優(yōu)值值z=-11。練習：練習：00348242max21212121xxxxxxxxz0042222max2121212121xxxxxxxxxxz16兩階段單純形算法兩階段單純形算法一般線性規(guī)劃問題轉(zhuǎn)化為標準形式的線性規(guī)劃問題后，每個一般線性規(guī)劃問題轉(zhuǎn)化為標準形式的線性規(guī)劃問題后，每個約束條件中不

16、一定都含有基本變量。在這種情況下，可在每約束條件中不一定都含有基本變量。在這種情況下，可在每個約束條件表達式的左端添加一個非負變量個約束條件表達式的左端添加一個非負變量zi(i=1,2,m)，將其轉(zhuǎn)化為約束標準型的線性規(guī)劃問題。添加的非負變量將其轉(zhuǎn)化為約束標準型的線性規(guī)劃問題。添加的非負變量zi稱為人工變量。形式如下：稱為人工變量。形式如下：), 2 , 1(0), 2 , 1(0max221122222121211212111112211miznjxbxaxaxazbxaxaxazbxaxaxazxcxcxcxczijmnmnmmmnnnnniiinn17第一階段：用輔助目標函數(shù)代替原來的目

17、標函數(shù)。第一階段：用輔助目標函數(shù)代替原來的目標函數(shù)。輔助目標函數(shù)：輔助目標函數(shù)： 。選擇人工變量作為基本變量，其它變量作為非基本變量，構(gòu)選擇人工變量作為基本變量，其它變量作為非基本變量，構(gòu)造初始單純形表。然后，運行該算法，當所有人工變量均變造初始單純形表。然后，運行該算法，當所有人工變量均變成非基本變量時，輔助目標函數(shù)達到最大值，第一階段算法成非基本變量時，輔助目標函數(shù)達到最大值，第一階段算法結(jié)束；如果所有人工變量無法全部變成非基本變量，則原線結(jié)束；如果所有人工變量無法全部變成非基本變量，則原線性規(guī)劃問題無解。性規(guī)劃問題無解。第二階段：將第一階段得到的最后一張單純形表中第二階段：將第一階段得到

18、的最后一張單純形表中的所有人工變量所在的列全部劃掉，剩下的就只含的所有人工變量所在的列全部劃掉，剩下的就只含有有xi的約束標準型線性規(guī)劃問題，此時的目標函數(shù)的約束標準型線性規(guī)劃問題，此時的目標函數(shù)由輔助目標函數(shù)改為原來的目標函數(shù)，用剩下的單由輔助目標函數(shù)改為原來的目標函數(shù)，用剩下的單純形表作為第二階段的初始單純形表，再次運行約純形表作為第二階段的初始單純形表，再次運行約束標準型單純形算法，即得線性規(guī)劃問題的解。束標準型單純形算法，即得線性規(guī)劃問題的解。mzzzz21187.2 最大網(wǎng)絡流問題最大網(wǎng)絡流問題1 基本概念和術(shù)語基本概念和術(shù)語 （1） 網(wǎng)絡網(wǎng)絡G是一個簡單有向圖，是一個簡單有向圖，G

19、=(V,E)，V=1，2，n。在。在V中中指定一個頂點指定一個頂點s，稱為，稱為源源和另一個頂點和另一個頂點t，稱為，稱為匯匯。有向圖。有向圖G的每一條邊的每一條邊(v,w)E，對應有一個值，對應有一個值cap(v,w)0，稱為邊的，稱為邊的容量容量。這樣的有向圖。這樣的有向圖G稱作一個稱作一個網(wǎng)絡網(wǎng)絡。（2） 網(wǎng)絡流網(wǎng)絡流網(wǎng)絡上的網(wǎng)絡上的流流是定義在網(wǎng)絡的邊集合是定義在網(wǎng)絡的邊集合E上的一個上的一個非負函數(shù)非負函數(shù)flow=flow(v,w)，并稱，并稱flow(v,w)為邊為邊(v,w)上的上的流量流量。19（3） 可行流可行流滿足下述條件的流flow稱為可行流可行流：容量約束：容量約束：

20、對每一條邊(v,w)E，0flow(v,w)cap(v,w)。平衡約束：平衡約束：對于中間頂點：流出量=流入量。即對每個vV(vs,t)有：頂點v的流出量頂點v的流入量=0，即對于源s：s的流出量s的流入量=源的凈輸出量f，即對于匯t：t的流入量t的流出量的=匯的凈輸入量f，即式中f 稱為這個可行流的流量，即源的凈輸出量(或匯的凈輸入量)。0),(),(),(),(EvwEwvvwflowwvflowfsvflowvsflowEsvEvs),(),(),(),(fvtflowtvflowEvtEtv),(),(),(),(20（4） 邊流邊流對于網(wǎng)絡G的一個給定的可行流flow，將網(wǎng)絡中滿足f

21、low(v,w)=cap(v,w)的邊稱為飽和邊飽和邊；flow(v,w)0的邊稱為非零流邊非零流邊。當邊(v,w)既不是一條零流邊也不是一條飽和邊時，稱為弱流邊弱流邊。（5） 最大流最大流最大流問題即求網(wǎng)絡G的一個可行流flow，使其流量f達到最大。即flow滿足：0flow(v,w)cap(v,w)，(v,w)E；且tvftsvsvfvwflowwvflow,0),(),(21（6） 流的費用流的費用網(wǎng)絡的每一條邊(v,w)除了給定容量cap(v,w)外，還定義了一個單位流量費用cost(v,w)。對于網(wǎng)絡中一個給定的流flow，其費用定義為：Ewvwvflowwvtflowt),(),(

22、),(cos)(cos22（7） 殘余網(wǎng)絡殘余網(wǎng)絡對于給定的一個流網(wǎng)絡G及其上的一個流flow，網(wǎng)絡G關(guān)于流flow的殘余網(wǎng)絡G*與G有相同的頂點集V，而網(wǎng)絡G中的每一條邊對應于G*中的1條邊或2條邊。設(shè)(v,w)是G的一條邊。當原網(wǎng)絡G中的邊(v,w)是一條零流邊時，殘流網(wǎng)絡G*中有唯一的一條邊(v,w)與之對應，且該邊的容量為cap(v,w)。當原網(wǎng)絡G中的邊(v,w)是一條飽和邊時，殘流網(wǎng)絡G*中有唯一的一條邊(w,v)與之對應，且該邊的容量為cap(v,w)。當原網(wǎng)絡G中的邊(v,w)是一條弱流邊時，殘流網(wǎng)絡G*中有2條邊(v,w)和(w,v)與之對應，這2條邊的容量分別為cap(v,

23、w) -flow(v,w)和flow(v,w)。23（8）向前邊和向后邊）向前邊和向后邊設(shè)P是網(wǎng)絡G中連結(jié)源s和匯t的一條路。定義路的方向是從s到t。將路P上的邊分成2類：一類邊的方向與路的方向一致，稱為向前邊向前邊。向前邊的全體記為P+。另一類邊的方向與路的方向相反，稱為向后邊向后邊。向后邊的全體記為P-。24（9）增廣路設(shè)flow是一個可行流，P是從s到t的一條路，若P滿足下列條件：在P的所有向前邊(v,w)上，flow(v,w)0，即P-中的每一條邊都是非零流。則稱P為關(guān)于可行流flow的一條可增廣路。25增廣路定理：增廣路定理：設(shè)flow是網(wǎng)絡G的一個可行流，如果不存在從s到t關(guān)于fl

24、ow的可增廣路P，則flow是G的一個最大流。增廣路算法增廣路算法（1）初始化為0流（2）找關(guān)于當前可行流的可增廣路，若找到，轉(zhuǎn)（3）；否則，當前可行流為網(wǎng)絡的最大流。（3）沿增廣路增流。因此，增廣路算法主要包括兩個過程：找增廣路和沿增廣路增流。26可采用標號法找可增廣路。對網(wǎng)絡中的每個節(jié)點j，其標號包括兩部分信息（pred(j)，maxl(j)），其中pred(j)表示節(jié)點j在可能的增廣路中的前一個節(jié)點，maxl(j)表示沿該可能的增廣路到節(jié)點j為止可以增加的最大流量。具體步驟為：步驟1：源點s的標號為（0，+）。步驟2：從已標號而未檢查的點v出發(fā)，對于邊，如果flow(v，w)cap(v，

25、w)，則w的標號為(v，maxl(w)，maxl(w)=minmaxl(v),cap(v，w)-flow(v，w)；對于邊，flow(w，v)0，則w的標號為(-v，maxl(w)，maxl(w)=minmaxl(v)，flow(w，v)。步驟3：不斷重復步驟2，直到已經(jīng)不存在已標號未檢查的點或標到了匯點結(jié)束。如果不存在已標號未檢查的點，則說明不存在關(guān)于當前可行流的可增廣路，當前流就是最大流。如果標到了匯點，則找到了一條可增廣路，需要沿著該可增廣路進行增流，轉(zhuǎn)過程（2）。沿增廣路增流具體方法 PwvwvflowPwvdwvflowPwvdwvflowwvflow),(),(),(),(),()

26、,(),(27例題用增廣路算法找出如下圖所示的網(wǎng)絡及可行流的最大流，其中，頂點1為源點，頂點6為匯點，邊上的權(quán)為（cap，flow）。28標號法找增廣路 沿著增廣路增流 29標號法找增廣路 沿著增廣路增流 30標號法找增廣路 沿著增廣路增流 31標號法找增廣路，當前流為最大流 32最大網(wǎng)絡流的變換與應用最大網(wǎng)絡流的變換與應用 1.多源多匯的網(wǎng)絡流問題多源多匯的網(wǎng)絡流問題多源多匯的最大流問題可以轉(zhuǎn)化為單源單匯的最大流問多源多匯的最大流問題可以轉(zhuǎn)化為單源單匯的最大流問題。題。方法：方法：在原網(wǎng)絡的基礎(chǔ)上，增加一個虛源在原網(wǎng)絡的基礎(chǔ)上，增加一個虛源s和一個虛匯和一個虛匯t。從從s向原網(wǎng)絡中的源點分別

27、引一條有向邊，每一條有向原網(wǎng)絡中的源點分別引一條有向邊，每一條有向邊的流量等于與其相連的源點（非虛源）的流出量，向邊的流量等于與其相連的源點（非虛源）的流出量，容量為無窮大；容量為無窮大；從原網(wǎng)絡中的匯點分別向虛匯引一條有向邊，每一條從原網(wǎng)絡中的匯點分別向虛匯引一條有向邊，每一條有向邊的流量等于與其相連的匯點的流入量，容量為有向邊的流量等于與其相連的匯點的流入量，容量為無窮大。無窮大。33示例示例 ：342.網(wǎng)絡的頂點容量約束網(wǎng)絡的頂點容量約束流經(jīng)某頂點的流量不能超過該頂點給定的約束值流經(jīng)某頂點的流量不能超過該頂點給定的約束值 變換方法：變換方法：只要將有頂點容量約束的頂點只要將有頂點容量約束

28、的頂點x用一條邊用一條邊來替換來替換原來頂點原來頂點x的入邊仍為頂點的入邊仍為頂點x的入邊，原來頂點的入邊，原來頂點x的出的出邊改為頂點邊改為頂點y的出邊。的出邊。連接頂點連接頂點x和頂點和頂點y只有一條邊只有一條邊，其邊容量為原，其邊容量為原頂點頂點x的頂點容量。的頂點容量。35最大網(wǎng)絡流的變換與應用最大網(wǎng)絡流的變換與應用3.二分圖的最大匹配問題二分圖的最大匹配問題二分圖的概念二分圖的概念設(shè)設(shè)G(V,E)是一個無向圖。如果是一個無向圖。如果頂點集合頂點集合V可分割為兩個可分割為兩個互不相互不相交的交的子集子集X和和Y，并且圖中每條邊，并且圖中每條邊(v,w)所關(guān)聯(lián)的兩個頂點所關(guān)聯(lián)的兩個頂點v

29、和和w分屬分屬于這兩個不同的頂點集，則稱圖于這兩個不同的頂點集，則稱圖G為一個二分圖。為一個二分圖。二分圖的匹配二分圖的匹配設(shè)設(shè)G(V,E)是一個二分圖。如果是一個二分圖。如果M E，且，且M中任何兩條邊都不與中任何兩條邊都不與同一個頂點相關(guān)聯(lián)，則稱同一個頂點相關(guān)聯(lián)，則稱M是是G的的一個匹配。一個匹配。二分圖的最大匹配。二分圖的最大匹配。36最大網(wǎng)絡流的變換與應用最大網(wǎng)絡流的變換與應用將二分圖的最大匹配問題將二分圖的最大匹配問題轉(zhuǎn)換為網(wǎng)絡的最大流問題轉(zhuǎn)換為網(wǎng)絡的最大流問題（1）增加一個源）增加一個源s利利個匯個匯t。（2）從）從s向向X的每一個頂點的每一個頂點都增加一條有向邊；從都增加一條有向

30、邊；從Y的每的每一個頂點都增加一條到一個頂點都增加一條到t的有的有向邊。向邊。（3）原圖）原圖G中的每中的每條都改條都改為相應的由為相應的由X指向指向Y的有向邊；的有向邊；（4）置所有邊的容量為）置所有邊的容量為1。37最大網(wǎng)絡流的變換與應用最大網(wǎng)絡流的變換與應用4.帶下界約束的最大流帶下界約束的最大流在給定網(wǎng)絡中，對于邊在給定網(wǎng)絡中，對于邊(x,y)，不僅僅有邊流量的上界約，不僅僅有邊流量的上界約束，即容量約束束，即容量約束cap(x,y)，還有邊流量的下界約束，還有邊流量的下界約束caplow(x.y)。在這種情況下，對可行流。在這種情況下，對可行流flow的容量約束的容量約束相應地改變?yōu)?/p>

31、相應地改變?yōu)? ),(),(),(yxcapyxflowyxcaplow兩個階段求解兩個階段求解第第1階段先找滿足約束條件的可行流階段先找滿足約束條件的可行流第第2階段將找到的可行流擴展成最大流。階段將找到的可行流擴展成最大流。 38最大網(wǎng)絡流的變換與應用最大網(wǎng)絡流的變換與應用第第1階段先找滿足約束條件階段先找滿足約束條件的可行流的可行流一個等價的循環(huán)可行流一個等價的循環(huán)可行流問題問題 變換方法變換方法在原網(wǎng)絡中增加一條容量在原網(wǎng)絡中增加一條容量充分大的邊從匯點指向源充分大的邊從匯點指向源點，這條邊將從源點流到點，這條邊將從源點流到匯點的流量再送回到源點匯點的流量再送回到源點構(gòu)成一個循環(huán)流。原

32、網(wǎng)絡構(gòu)成一個循環(huán)流。原網(wǎng)絡有可行流當且僅當新網(wǎng)絡有可行流當且僅當新網(wǎng)絡有循環(huán)可行流。有循環(huán)可行流。 39最大網(wǎng)絡流的變換與應用最大網(wǎng)絡流的變換與應用設(shè)設(shè)flow是新網(wǎng)絡的一個循環(huán)可行流，則是新網(wǎng)絡的一個循環(huán)可行流，則(1)對于對于 有有:頂點頂點x的流出量的流出量-頂點頂點x的流入量的流入量=0 (2)對于對于 ，有，有將其轉(zhuǎn)化為一般網(wǎng)絡的最大流問題。將其轉(zhuǎn)化為一般網(wǎng)絡的最大流問題。轉(zhuǎn)化方法轉(zhuǎn)化方法對對 且邊且邊(x,y)既有邊容量上界約束，也有既有邊容量上界約束，也有邊容量下界約束，在循環(huán)網(wǎng)絡中添加相應的源邊容量下界約束，在循環(huán)網(wǎng)絡中添加相應的源點點s和匯點和匯點t，添加兩條有向邊，添加兩條

33、有向邊(x,t)、(s,y)，邊，邊上的容量均為上的容量均為caplow(x,y)。 VxEyx),(),(),(),(yxcapyxflowyxcaplowEyx),(40將其轉(zhuǎn)化為單源單匯的將其轉(zhuǎn)化為單源單匯的最大流問題最大流問題4142437.3 最小費用流問題最小費用流問題1 網(wǎng)絡流的費用網(wǎng)絡流的費用網(wǎng)絡的每一條邊網(wǎng)絡的每一條邊(v,w)除了給定容量除了給定容量cap(v,w)外，還定義了一個單位流量外，還定義了一個單位流量費用費用cost(v,w)。對于網(wǎng)絡中一個給定的流對于網(wǎng)絡中一個給定的流flow，其費用定義為：其費用定義為：2涉及流的費用的殘余網(wǎng)絡涉及流的費用的殘余網(wǎng)絡對于對于

34、G中的任一條邊中的任一條邊：對應于：對應于G*中的中的，則設(shè)置，則設(shè)置G*中中的單位流量費用為的單位流量費用為cost(x,y)；對應于；對應于G*中的中的，則設(shè)置，則設(shè)置G*中中的單位流量費用為的單位流量費用為-cost(x,y)。Ewvwvflowwvtflowt),(),(),(cos)(cos443最小費用最大流問題最小費用最大流問題給定網(wǎng)絡給定網(wǎng)絡G，要求要求G的一個最大流的一個最大流flow，使流的總費用最使流的總費用最小。小。4負費用圈負費用圈對于一個給定的網(wǎng)絡對于一個給定的網(wǎng)絡G、其上的可行流、其上的可行流flow及流的費用，及流的費用，殘余網(wǎng)絡中的負費用圈是指所有邊的單位流量

35、費用之和殘余網(wǎng)絡中的負費用圈是指所有邊的單位流量費用之和為負的圈為負的圈 最小費用最大流問題的最優(yōu)性定理最小費用最大流問題的最優(yōu)性定理網(wǎng)絡網(wǎng)絡G的最大流的最大流flow是是G的一個最小費用最大流的充分必的一個最小費用最大流的充分必要條件是要條件是flow所對應的殘余網(wǎng)絡中沒有負費用圈所對應的殘余網(wǎng)絡中沒有負費用圈 45最小費用流的消圈算法最小費用流的消圈算法 步驟步驟0：用最大流算法構(gòu)造最大流：用最大流算法構(gòu)造最大流flow。步驟步驟1：如果殘余網(wǎng)絡中不存在負費用圈，則計算結(jié)束，已經(jīng)找到最小費用流；：如果殘余網(wǎng)絡中不存在負費用圈，則計算結(jié)束，已經(jīng)找到最小費用流；否則轉(zhuǎn)步驟否則轉(zhuǎn)步驟2。步驟步驟

36、2：沿找到的負費用圈增流，并轉(zhuǎn)步驟：沿找到的負費用圈增流，并轉(zhuǎn)步驟1。w算法主要包括兩個過程算法主要包括兩個過程w找負費用圈找負費用圈w沿負費用圈增流沿負費用圈增流46找負費用圈的方法找負費用圈的方法步驟步驟1：初始化數(shù)組：初始化數(shù)組st中的元素全為中的元素全為0；數(shù)組；數(shù)組wts=0，其它均為無窮大；，其它均為無窮大；隊列隊列Q為空；為空；N=0。步驟步驟2：節(jié)點：節(jié)點s入隊，令入隊，令m=頂點個數(shù)頂點個數(shù)+1，m也入隊；也入隊；步驟步驟3：檢查隊列是否為空，如果為空，則殘余網(wǎng)絡中沒有負費用圈，算：檢查隊列是否為空，如果為空，則殘余網(wǎng)絡中沒有負費用圈，算法結(jié)束；如果不空，則轉(zhuǎn)步驟法結(jié)束；如果

37、不空，則轉(zhuǎn)步驟4；步驟步驟4：取出隊首元素：取出隊首元素v；步驟步驟5：如果：如果v=m，判斷，判斷N是否大于是否大于m，如果，如果N大于大于m，則殘余網(wǎng)絡中沒有，則殘余網(wǎng)絡中沒有負費用圈，算法結(jié)束；否則，負費用圈，算法結(jié)束；否則，N+，將，將m入隊，轉(zhuǎn)步驟入隊，轉(zhuǎn)步驟4；如果；如果vm，轉(zhuǎn)步，轉(zhuǎn)步驟驟6；步驟步驟6：殘余網(wǎng)絡中如果不存在以：殘余網(wǎng)絡中如果不存在以v為弧尾且未檢查的弧，轉(zhuǎn)步驟為弧尾且未檢查的弧，轉(zhuǎn)步驟3；否則；否則對其中一條以對其中一條以v為弧尾且未檢查的弧，轉(zhuǎn)步驟為弧尾且未檢查的弧，轉(zhuǎn)步驟7；步驟步驟7：取出弧的弧頭：取出弧的弧頭w；步驟步驟8；計算；計算wtv+cost(v

38、,w)，記其值為，記其值為p;步驟步驟9：如果：如果p大于等于大于等于wtw，轉(zhuǎn)步驟，轉(zhuǎn)步驟6；否則；否則wtw=p，stw=v；步驟步驟10：利用：利用st找出包含節(jié)點找出包含節(jié)點w的負費用圈，如果找到返回的負費用圈，如果找到返回w，算法結(jié)束；，算法結(jié)束；反之將反之將w入隊；轉(zhuǎn)步驟入隊；轉(zhuǎn)步驟6。47沿負費用圈增流的方法沿負費用圈增流的方法如果找到負費用圈，則沿負費用圈增流，設(shè)如果找到負費用圈，則沿負費用圈增流，設(shè)增量為增量為d。增流方法增流方法沿負費用圈方向的邊容量減去沿負費用圈方向的邊容量減去d，如果邊的容量，如果邊的容量等于等于0，則取消該方向的邊；逆負費用圈方向的，則取消該方向的邊；

39、逆負費用圈方向的邊容量加上邊容量加上d。48例題：在下圖中找負費用圈49步驟1：初始化。初始化數(shù)組st中的元素均為0；wt1=0，其它均為；隊列為空；N=0；m=6+1=7;步驟2：讓節(jié)點1和m入隊；數(shù)組st、wt及隊列Q的數(shù)據(jù)如下圖所示。50步驟3：取出隊首元素1。檢查以1為弧尾的所有弧。對于弧，記w=2。計算p=wt1+cost12=0+1=1。由于pwt2，所以wt2=1，st2=1；然后找以2為始點和終點的圈，結(jié)果未找到，將節(jié)點2入隊。對于弧，記w=3。計算p=wt1+cost13=0+7=7。由于pwt3，所以wt3=7，st3=1；然后找以3為始點和終點的圈，結(jié)果未找到，將節(jié)點3入隊。數(shù)組st、wt及隊列Q的數(shù)據(jù)如圖所示。51步驟5：取出隊首元素，即m