最小費(fèi)用流問題課件_第1頁
最小費(fèi)用流問題課件_第2頁
最小費(fèi)用流問題課件_第3頁
最小費(fèi)用流問題課件_第4頁
最小費(fèi)用流問題課件_第5頁
已閱讀5頁,還剩102頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

最小費(fèi)用流問題例、最小費(fèi)用流問題目標(biāo):從發(fā)點(diǎn)到收點(diǎn)的總的流量費(fèi)用最小約束:1)容量約束,各邊流量不大于容量

2)流量平衡約束,各點(diǎn)進(jìn)出流量總和相等

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

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

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

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

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

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論