最小費用流問題課件

最小費用流問題例、最小費用流問題目標：從發(fā)點到收點的總的流量費用最小約束：1）容量約束，各邊流量不大于容量

2）流量平衡約束，各點進出流量總和相等

3）從發(fā)點到收點的總流量為括號內(nèi)第一個數(shù)字是容量，第二個是單位流量費用最小費用流問題的一般提法容量網(wǎng)絡(luò)的每邊另外賦值非負的單位流量費用，記為，給定從到的總流量，要求一個總流量等于的可行流使得總費用達到最小，特別是，如果給定總流量等于最大流，所求問題稱為最小費用最大流問題下例中可行流要滿足的流量平衡約束中間節(jié)點：發(fā)點：收點：定義：從發(fā)出的所有邊的終節(jié)點指標集合

:進入的所有邊的始節(jié)點的指標集合如下圖：再用表示的凈發(fā)出流量，即流量平衡約束可統(tǒng)一寫成網(wǎng)絡(luò)的最小費用流問題是一種特殊的線性規(guī)劃問題最小費用流問題的對偶目標函數(shù)對偶目標函數(shù)其中是的分量，表示容量約束最小費用流問題的松弛條件和滿足松弛條件滿足容量約束最小費用流問題的松弛定理：則是原問題最優(yōu)解，是對偶問題最優(yōu)解如果可行流和對偶變量滿足松弛條件由弱對偶定理可知結(jié)論成立證明：滿足松弛條件可行流利用松弛定理解決最小費用流問題的途徑1）產(chǎn)生一對滿足松弛條件和所有中間節(jié)點的流量平衡條件的，的總流量不大于，例如，2）如果也滿足收點和發(fā)點的流量平衡條件（總流量為），已是原問題的最優(yōu)解3）如果不滿足發(fā)點和收點的平衡條件，那么在滿足1）的條件的前提下改進，使其流量增加如何完成3）的任務？如何增加流量？已知條件：（滿足所有中間節(jié)點的流量平衡條件和容量約束）

是最大流的充要條件（增廣鏈定理）：不存在關(guān)于的可增廣鏈可以采用的方法：是最大流問題的一個可行流尋找關(guān)于的可增廣鏈，如果找不到，已經(jīng)是最大流，原問題不可行，否則增加流量如果沿該增廣鏈增加流量，由容量約束知由于增加后的總流量為，應滿足所以最終選用的流量增加值應該為假設(shè)是從到關(guān)于的可增廣鏈，用表示其前向邊的集合，表示后向邊的集合，用表示當前的總流量流量調(diào)整前后原目標函數(shù)的改變?yōu)槭茄卦黾訂挝涣髁康馁M用，稱為的費用，顯然應該選擇費用最小的可增廣鏈增加總流量記沿對進行調(diào)整獲得新的流量，則根據(jù)前面的討論可形成下面的最小費用流算法：1）令2）如果，停止，否則求出費用最小的可增廣鏈（如果沒有可增廣鏈，停止）3）令

4）用替換，替換，回到2）對前面的最小費用流算法要解決的問題1）實現(xiàn)問題如何方便地求出費用最小的可增廣鏈？2）理論問題算法停止于時所產(chǎn)生的是否是最小費用流問題的解？對第一個問題的解決方法情況1）如果出現(xiàn)在某個可增廣鏈中，一定屬于該鏈的前向邊，此時如果把轉(zhuǎn)換成從到的下述道路任取，其只會是以下三種情況之一1），2），3）那么構(gòu)成路長的一部分，就象構(gòu)成的一部分一樣情況2）如果出現(xiàn)在某個可增廣鏈中，一定屬于該鏈的后向邊，此時如果把轉(zhuǎn)換成從到的下述道路那么構(gòu)成路長的一部分，就象構(gòu)成的一部分一樣情況3）此時既可能屬于前向邊，也可能屬于后向邊，所以上述兩種可能的等價轉(zhuǎn)化方式都應該保留總結(jié)前面討論，可以把容量網(wǎng)絡(luò)的每條邊按以下規(guī)則等價轉(zhuǎn)換成長度網(wǎng)絡(luò)（求最短路的網(wǎng)絡(luò)）中的邊如果如果如果然后求長度網(wǎng)絡(luò)的最短路確定最小費用可增廣鏈例長度網(wǎng)絡(luò)由于有小于零的權(quán)值，要用值迭代法求最短路對長度網(wǎng)絡(luò)的改進簡化成本定義從到關(guān)于的可增廣鏈的長度增廣鏈上任意中間節(jié)點的三種可能情況可以用代替生成計算最小費用的可增廣鏈用代替計算最小費用的可增廣鏈的好處和滿足松弛條件最短路網(wǎng)絡(luò)無負數(shù)，可用Dijkstra算法對第二個問題的回答那么存在對偶變量和一起滿足松弛條件定理如果下述條件滿足：1）滿足所有中間節(jié)點的流量平衡條件2）存在對偶變量和一起滿足松弛條件3）是從到關(guān)于的最小費用可增廣鏈4）沿對按前面的算法調(diào)整獲得一旦證明了上述定理，馬上可以說明前面的最小費用流算法或者能夠證明沒有可行解，或者能夠給出最優(yōu)解對用生成的長度網(wǎng)絡(luò)的每個，用表示從到的最短路，如果從到?jīng)]有道路，令，用表示最小費用增廣鏈及其前向和后向邊，由最小費用增廣鏈的定義可知定義如下下面說明，這樣定義的和一起滿足松弛條件，從而完成對前面定理的證明首先可以看出（反證）所以，如果能夠證明上面條件成立，就可完成證明首先考慮的情況，又要分別考慮兩種情形1）2）（不一定在增廣鏈上）對的情況可類似證明利用對偶變量的最小費用流求解算法1）令2）如果，停止3）令，構(gòu)造長度網(wǎng)絡(luò)4）求出從到每個的最短路長，如果到某個沒有最短路，令5）如果，停止（沒有可增廣鏈）6）利用從到的最短路和所有的修改原變量和對偶變量，并用修改后的數(shù)值替換原來的數(shù)值，同時修改總流量，然后回到2）例求總流量為10的

最小費用流令，長度網(wǎng)絡(luò)為求得增廣鏈（紅線）和所有的（括號內(nèi)的數(shù)）求出（）利用可增廣鏈調(diào)整流量第一次迭代后的信息均在下圖中，其中頂點后的數(shù)是對偶變量值，容量和費用對下面的數(shù)據(jù)對是流量簡化成本可驗證松弛條件利用上圖構(gòu)造長度網(wǎng)絡(luò)圖求得增廣鏈（紅線）和所有的利用求出利用可增廣鏈調(diào)整流量第二次迭代后的信息可驗證松弛條件利用上圖構(gòu)造長度網(wǎng)絡(luò)求得增廣鏈（紅線）和所有的利用求出利用可增廣鏈調(diào)整流量第三次迭代后的信息可驗證松弛條件由于總流量等于10已經(jīng)滿足約束，所以是最優(yōu)解運輸問題運輸表描述產(chǎn)地銷地產(chǎn)量銷量運輸問題的圖描述產(chǎn)地銷地產(chǎn)量銷量在流量平衡和非負約束下極小化總的運輸費用產(chǎn)銷平衡運輸問題的數(shù)學規(guī)劃模型（線性規(guī)劃問題）產(chǎn)銷平衡假定：有可行解最后一個約束多余，等式約束可寫成共有個等式約束注意：其中列向量表示模型例產(chǎn)地銷地產(chǎn)量銷量圖表示產(chǎn)生基本可行解如果一組變量（紅線表示）形成回路在中令其他變量等于0如果一組變量（紅線表示）不含回路在中令其他變量等于0上述第一種情況的運輸表產(chǎn)地銷地產(chǎn)量銷量上述第二種情況的運輸表產(chǎn)地銷地產(chǎn)量銷量結(jié)論：運輸問題一組變量的系數(shù)線性無關(guān)的充要條件是在圖或表中不含有回路基本可行解的個數(shù)用最小元素法產(chǎn)生基本可行解基本思想：優(yōu)先安排單位運輸成本最小的運輸方式產(chǎn)地銷地產(chǎn)量銷量產(chǎn)地銷地產(chǎn)量銷量產(chǎn)地銷地產(chǎn)量銷量產(chǎn)地銷地產(chǎn)量銷量產(chǎn)地銷地產(chǎn)量銷量產(chǎn)地銷地產(chǎn)量銷量最后刪除兩個約束不會形成回路每次刪除一個約束（節(jié)點）變量產(chǎn)生基本可行解等價于在運輸圖中生成一個支撐樹由流量平衡方程依次可得對應的可行流計算檢驗數(shù)回憶檢驗數(shù)計算公式令（對偶變量）產(chǎn)地銷地產(chǎn)量位勢行位勢列銷量利用運輸表解對偶變量（位勢法）產(chǎn)地銷地產(chǎn)量位勢行位勢列銷量產(chǎn)地銷地產(chǎn)量位勢行位勢列銷量產(chǎn)地銷地產(chǎn)量位勢行位勢列銷量利用對偶變量計算檢驗數(shù)（視）改進基本可行解產(chǎn)地銷地產(chǎn)量銷量已知以下基本可行解和負的檢驗數(shù)讓進基（取值大于零）可改進基本可行解由于基本可行解形成一個支撐樹，加入任何非基變量一定和某些基變量形成回路加入形成回路產(chǎn)地銷地產(chǎn)量銷量在和基變量形成的回路中，讓基變量依次減少或增加的增加值，可保持等式約束滿足產(chǎn)地銷地產(chǎn)量銷量取，可得下面新的基本可行解出基，目標函數(shù)等于原目標值加上算法總結(jié)1）用最小元素法確定一個基本可行解2）用位勢法計算所有非基變量的檢驗數(shù)3）如果所有檢驗數(shù)不小于零，已得最優(yōu)解，否則找出最小檢驗數(shù)對應的非基變量以及與其形成回路的基變量，據(jù)此確定相應非基變量的增加值以及回路基變量的新值，然后回到上一步繼續(xù)迭代總產(chǎn)量大于總銷量（產(chǎn)銷不平衡）的運輸問題優(yōu)化模型處理辦法引入假想銷地優(yōu)化模型往假想銷地的運量沒有成本定義假想銷地的銷量指派問題例

開辦五家新商店，要五家建筑公司分別承建，各公

司營造費用報價如下，如何指派使總造價最小商店費用報價公司標準指派問題的一般提法有件事要個人完成，每人做一件事，已知第個人做第件事的成本是，要確定人和事之間一對一的指派方案，使完成這件事的總費用最小稱為指派問題的系數(shù)矩陣定義整數(shù)規(guī)劃模型產(chǎn)地銷地產(chǎn)量銷量標準指派問題是一個特殊的產(chǎn)銷平衡運輸問題當且僅當一組變量不含回路時，其對應的系數(shù)矩陣的列向量線性無關(guān)推論一組線性無關(guān)的系數(shù)向量對應的變量中，至少有一個變量所在行或列沒有其它基變量在運輸問題的討論中已得出下面的結(jié)論推論運輸問題的基變量取值一定等于產(chǎn)量或銷量或它們的差或它們的差的差產(chǎn)地銷地產(chǎn)量銷量例推論產(chǎn)量和銷量都是非負整數(shù)的運輸問題的基本可行

解的每個分量一定是非負整數(shù)推論下述運輸問題的基本可行解滿足0-1約束！產(chǎn)地銷地產(chǎn)量銷量結(jié)論不用考慮0-1變量約束！求解下述運輸問題可得標準指派問題的解盡管可以用求解運輸問題的算法求解標準指派問題，由于存在大量的退化解，經(jīng)常出現(xiàn)換基不能改進目標函數(shù)的情況，這種做法效率不高進一步挖掘標準指派問題的特點可以獲得更加有效的算法，這就是所謂的匈牙利算法標準指派問題的第一個有用的性質(zhì)任取和任意實數(shù)，用和分別表示將的第行或第列減去以后得到的系數(shù)矩陣，則以，或為系數(shù)矩陣的指派問題的最優(yōu)方案相同理由：目標函數(shù)差一個常數(shù)，約束相同，最優(yōu)解也相同標準指派問題的第二個有用的性質(zhì)如果的所有元素中沒有負數(shù)，且存在個行列號都互不相同的零元素（簡稱為獨立零元素），那么對應的標準指派問題的最優(yōu)目標值等于零，最優(yōu)方案可以由獨立零元素的位置確定例如最優(yōu)解算法設(shè)想（匈牙利算法）一、利用第一個性質(zhì)產(chǎn)生獨立零元素二、對給定矩陣找到最大的獨立零元素組三、當最大的獨立零元素組的零元素數(shù)目不夠

時增加獨立零元素的數(shù)目通過以上步驟的迭代找到足夠的獨立零元素例一、順序?qū)γ啃忻苛袦p去最小值產(chǎn)生零元素1）用紅圈標出一些某行或某列僅有的零元素，再通過行列交換把這些零換到左上角（后者非必須）行交換二、對給定矩陣找到最大數(shù)目的獨立零元素組列交換2）在沒有紅圈的右下角如果有零，一定是新的獨立零元素3）用直線覆蓋紅圈所在行4）在直線未覆蓋處找零，如果沒有零停止，否則會出現(xiàn)以下兩種情況，其中黑實圈圈住的是新零情況二情況一兩種情況的處理方法前面第一種情況后可能發(fā)生的另外一種情況例未覆蓋的黑圈所在列的紅圈所在行存在沒有列直線覆蓋的零，和前面的第二種情況一樣，但是該黑圈所在行有紅圈，不能將該零選為獨立零元素此時要覆蓋剩下的零必須加直線這種情況也一定能夠增加獨立零元素理由：新選零未被行直線覆蓋，而該行有紅圈，紅圈一定被列直線覆蓋，其所在列一定有黑圈（記為A），如果A所在行沒有紅圈，即可按上面圖型顯