【文章內(nèi)容簡介】 (1,0) (1,0) (1,2) 33 對偶算法 – 復(fù)雜性分析 算法每次循環(huán)迭代修改弧上的流值和節(jié)點上的勢各一次 . 由于流值不可能超過 nU, 且任何節(jié)點上的勢不可能低于 nC, 因此總迭代次數(shù)不會超過 min{nU,nC}. 記求解 非負弧長網(wǎng)絡(luò) 的最短路算法的復(fù)雜度為 S(n， m， C), 最大流算法的復(fù)雜度為 M(n， m， U) 本算法復(fù)雜度為 O(min{nU,nC}[S(n， m， nC)+ M(n， m， U)] ) 這一算法仍然不是多項式時間算法 與最小費用路算法相比 , 可能會以每次迭代調(diào)用一次最大流算法為代價 , 希望減少一些迭代次數(shù) . 34 布 置 作 業(yè) 目的 掌握最小費用流問題的 基本概念和建模方法 ； 掌握 消圈算法與最小費用路算法及其 復(fù)雜度； 掌握原始 對偶算法的基本思想。 內(nèi)容 《 網(wǎng)絡(luò)優(yōu)化 》 第 245251頁 3； 6； 15；（第 1講） 思考 4； 5； （不交） 35 網(wǎng) 絡(luò) 優(yōu) 化 Network Optimization 清華大學(xué)數(shù)學(xué)科學(xué)系 謝金星 辦公室：理科樓 2206 （電話： 62787812） Email: 清華大學(xué)課號： 70420203（研） 第 7章 最小費用流問題 (Minimum Cost Flow Problem) 第 2講 36 (OutOfKilter Algorithm) 瑕疵算法 (也翻譯為 “ 狀態(tài)算法 ” )在迭代過程中則對這些條件更為放寬 : ? 只要求滿足節(jié)點上的流量守恒條件 , 而不要求 x為偽流 (即可能不滿足容量約束 ), ? 并且也不一定保持互補松弛條件 . 最小費用路算法和原始 對偶算法的特點 : ? 對偶變量 ?為對偶問題的可行解 , 并始終保持互補松弛條件； ? 但原始變量 x在算法終止前通常不是原問題的可行解 （ 即只是偽流 ， 而不一定滿足節(jié)點上的流量守恒條件 , 即不是流值為 v的可行流 ） . 37 (OutOfKilter Algorithm) 想一想 ,非循環(huán)流的情況是否都可以轉(zhuǎn)化為循環(huán)流的情況 ? 算法的思想： ?通過一定步驟 , 使非最優(yōu)的 “ 程度 ” 不斷降低 ， 最后達到最優(yōu) . ?可以認為 , 瑕疵算法是原始 對偶算法的一種變形 . 瑕疵算法的考察對象： ?循環(huán)流 (Circulation) ：流值為 0的可行流 （ 沒有所謂源點和匯點 , 網(wǎng)絡(luò)中的所有節(jié)點都是轉(zhuǎn)運點 ） ?網(wǎng)絡(luò)中容量下限 L 不一定為 0； 38 Kilter條件 L?0 L=0 最小費用循環(huán)流模型 當 0 時 ， = 0； (’) 當 0 時 ， = ； (’) 當 時 ， = 0. (’) ijij ux ??0ijxijx iju?ijc?ijc?ijc.),(,0..m i n),(:),(:),(AjiuxlVixxtsxcijijijAijjjiAjijijAjiijij?????? ??????當 0 時 ， = ； () 當 0 時 ， = ； () 當 時 ， = 0. () ijijij uxl ??ijxijx iju?ijc?ijc?ijcijl互補松弛條件 jiijij cc ??? ??? Kilter條件 （ 或譯為瑕疵條件 、 狀態(tài)條件等 ） 滿足該條件的弧為無瑕的 (InKilter), 否則稱為有瑕的 (OutOfKilter). 39 Kilter圖 。Kilter數(shù) 如果所有弧都是無瑕的 , 則得到了原問題的最優(yōu)解 . 定義 對于每條弧 (i,j), 我們定義其 Kilter數(shù) （ 瑕疵數(shù) 、 狀態(tài)數(shù) ）為將流量 xij修正為滿足 Kilter條件所需要修改的量 (假設(shè)保持節(jié)點上的勢不變 ), 記為 K (xij)或 kij, 即 Kilter圖 （ 瑕疵圖 、 狀態(tài)圖等 ） 當 0 時 ， = ； () 當 0 時 ， = ； () 當 時 ， = 0. () ijijij uxl ??ijxijx iju?ijc?ijc?ijcijl?ijcijl ijuijx???????????????????.,0,0,0,0,0,其它時且當時且當時當時當ijijijijijijijijijijijijijijijijuxcuxlxcxlcuxclx????40 殘量網(wǎng)絡(luò) 當 xijlij時 , 則 (i,j)?N(x), uij(x)=lijxij, cij(x)=cij 當 xijuij 時 , 則 (j,i)?N(x), uji(x)=xij uij, cji(x)= cij. 瑕疵算法仍然是在殘量網(wǎng)絡(luò)上對弧上的流量進行操作 。 由于流不一定滿足容量約束 , 需定義這時殘量網(wǎng)絡(luò)的構(gòu)造方法 : 把原網(wǎng)絡(luò)中可能增加流量的弧 (前向弧 )、 減少流量的弧 (反向弧 )納入殘量網(wǎng)絡(luò) . 具體 方法如下 : 瑕疵算法的思想： 在算法過程中使弧上的 Kilter數(shù)不斷下降 ,最后降為 0. 當 時 : 如果 xijuij, 則 (i,j)?N(x), uij(x)=uijxij, cij(x)=cij。 如果 xijlij , 則 (j,i)?N(x), uji(x)=xij lij, cji(x)= cij. ijijijuxl ??41 殘量網(wǎng)絡(luò) 可以直接定義弧 (i,j)?N(x)的 Kilter數(shù) ， 分三種情況討論 : 可知 :原網(wǎng)絡(luò)中的任何一條瑕疵弧一定會在殘量網(wǎng)絡(luò)中得到反映(即瑕疵弧不以前向弧的形式出現(xiàn) , 就以反向弧的形式出現(xiàn) ). 當 時 : 如果 (i,j)是瑕疵弧 ( 0), 則其 Kilter數(shù)必然等于 (i,j)的殘留容量 : kij =uij(x) ijijijuxl ?? ?ijc當 xijlij時 : 如果 ? 0, 則 kij = uij(x)=lijxij。如果 0, 則 kij = uijxij. ?ijc ?ijc當 xjiuji 時 :如果 0(即 0),則 kij=xjilji。 如果 ? 0(即 ?0),則kij=uij(x)=xji uji. ?ijc?jic ?jic ?ijc?ijcijl ijuijx42 步驟 STEP 0 . 給出初始勢和初始循環(huán)流 (如 ?=0, x=0). Yakovleva(1959), Minty(1960), Fulkerson(1961)等提出 。 Aashtiani和 Magnanti(1976)給出一種高效率的實現(xiàn)方法 . STEP 1. 計算弧上的 Kilter數(shù) . 若網(wǎng)絡(luò)中不存在瑕疵弧 , 則已經(jīng)得到最優(yōu)解 , 計算結(jié)束；否則在殘量網(wǎng)絡(luò) N(x)中 ， 選擇一條瑕疵?。?p,q） , 繼續(xù)下一步 . STEP 3. 若 （ p,q） 仍為瑕疵弧 , 則沿 P ?{(p,q)} 確定的增廣圈增廣流量 (增廣的流值為該增廣圈的容量 ), 轉(zhuǎn) STEP 1。 否則直接轉(zhuǎn)STEP 1. STEP 2. 在 N(x)\{(q,p)}中 , 以 max{0, }為 （ i,j） 弧的弧長 ， 計算從節(jié)點 q到所有節(jié)點 i 的最短路路長 d(i)， 并記從節(jié)點 q到節(jié)點 p的最短路為 P. 令 ?i = ?i d(i), 繼續(xù) STEP 3. ?ijc主要過程 : 一是對節(jié)點上勢的修改 。 一是沿增廣圈增廣 43 正確性 證明 引理 在瑕疵算法中 , 對節(jié)點上勢的修改不會增加任何弧上的 Kilter數(shù) . 對殘量網(wǎng)絡(luò) N ( x ) 的一條弧（ i , j ） ? ( p , q ) , 由最短路方程得d ( j ) ? d ( i ) + m a x { 0 ,?ijc }, 即 d ( i ) d ( j )? m a x { 0 , ?ijc }. 記修改后的勢39。i? = i? d ( i ), 則 = + = (?i d(i)) +(?j d(j))= +(d(i)d(j))? max{0, } 39。?ijc ijc 39。i? 39。j? ijc ?ijc?ijc ?ijc當 ?0: ? max{0, } =0 () ?ijc 39。?ijc ?ijc ?ijc當 0: ? max{0, } = () ?ijc 39。?ijc ?ijc ?ijc ?ijc而對于弧 （ i,j） = (p,q)， 由于 d(q)=0， d(p) 0, 所以 = + = (?i d(i)) +(?j d(j))= +(d(i)d(j))? () 39。?ijc ijc 39。i? 39。j? ijc ?ijc ?ijc44 正確性 從 Kilter數(shù)的定義知 : 當弧上流量保持不變時 , 只有的符號改變時 , 弧上的 Kilter數(shù)才可能改變 . 下面分別對幾種情況討論 : 節(jié)點上勢的修改不會增加任何弧上的 Kilter數(shù) . 沿增廣圈增廣呢 ? 當 時 :如果 (i,j) 關(guān)于 ?是無瑕弧 ,則關(guān)于 ?’ 也是無瑕弧 。如果 (i,j)關(guān)于 ?是瑕疵弧 ( 0), 則關(guān)于 ?’ 可能是無瑕弧 ,也可能是瑕疵弧 (其 Kilter數(shù)必然等于 (i,j)的殘留容量 : k’ij = kij =uij(x)) ijijij uxl ???ijc當 xjiuji 時 :此時在節(jié)點上勢的修改前后 (i,j)一定都是瑕疵弧 . 與 xijlij類似可證 當 xijlij時 : 此時在節(jié)點上勢的修改前后 （ i,j） 一定都是瑕疵弧 . 如果 ? 0, 則 ?0, k’ij = kij = uij(x)=lijxij不變 . 如果 0, 則 : 若 0,則 k’ij = kij = uijxij不變 。 若 ? 0,則 k’ij = lijxij ? uijxij ?ijc39。?ijc?ijc39。?ijc39。?ijc45 正確性 引理 在瑕疵算法中 , 沿增廣圈 P ?{(p,q)}增廣流量不會增加任何弧上的 Kilter數(shù) , 且弧 (p,q)的 Kilter數(shù)嚴格減少 沿增廣圈 P ?{(p,q)} 增廣流量只可能改變?nèi)ι系幕〖捌浞聪蚧〉?Kilter數(shù) . 對于增廣圈上容量不可行的弧 (i,j), 由殘量網(wǎng)絡(luò)的構(gòu)造方法可知 :流量增廣后該弧的 Kilter數(shù)一定嚴格下降 , 且不會在殘量網(wǎng)絡(luò)中加入新的弧 (j,i). 對于增廣圈上容量可行的弧 , 流量增廣不改變?nèi)萘靠尚谢〉娜萘靠尚行?