【正文】 ； () 當(dāng) 0 時 ， = 0 ； () ijxijx ?ijc?ijc?設(shè)給定了一個基本可行解 x, 基矩陣所對應(yīng)的可行樹為 T. 由于只有樹弧上的流量可以為正數(shù) , 所以只有樹弧才可能滿足 (). ? 支撐樹上的弧共有 (n1)條 , 而對偶變量 (節(jié)點上的勢 )共有 n個 . 在相差一個常數(shù)的意義下 , 由 T中的弧滿足 =0可以唯一地確定對偶變量 . jiijijcc ??? ???可以任意選定一個節(jié)點 （ 這一節(jié)點通常稱為 “ 根 ” （ Root）） , 令它的勢為 0。 i?當(dāng) i?Tq 時 , = ?i + 。 若最優(yōu)解中有人工弧上的流量不為 0, 則增加 M的規(guī)模重新計算 . 如果 M的取值不足夠大 , 即使原問題有有界的最優(yōu)解 , 人工網(wǎng)絡(luò)上的最小費用流問題可能也會沒有有界的最優(yōu)解 (即最優(yōu)值趨向負(fù)無窮 ). 72 基可以用所有弧的一個劃分 (T,L,U)來表示 , 其中 T是一棵支撐樹 , L是非樹弧中流量等于下界的弧的集合 , U是非樹弧中流量等于上界的弧的集合 . 三元組 (T,L,U)可以稱為基結(jié)構(gòu) (有時也直接簡稱為基 ), 或支撐樹結(jié)構(gòu) . 最高標(biāo)號預(yù)流推進(jìn)算法 用支撐樹表示基 , 只有樹弧上的流量可以不等于下界和上界 , 而所有非樹弧上的流量只能等于下界或上界 . CxmindBxts ?..給定一個基結(jié)構(gòu) (T,L,U), 非樹弧上的流量已經(jīng)確定 , 所以樹弧上的流量也可以方便地根據(jù)節(jié)點上的流量守恒約束計算出來 , 并且也是唯一的 . 如果這些流量同時滿足容量的上下界約束 , 則 (T,L,U)是可行支撐樹結(jié)構(gòu) (簡稱 可行樹結(jié)構(gòu) ). 節(jié)點上的勢也可以與前面的討論完全類似地進(jìn)行計算 . 容量有界的情形 ijijij uxl ??73 初始的強可行樹結(jié)構(gòu)：仍然可以構(gòu)造人工網(wǎng)絡(luò) , 采用大 M方法 . 最高標(biāo)號預(yù)流推進(jìn)算法 定義 假定計算節(jié)點上的勢時所選定的 “ 根節(jié)點 ” 是固定的 . 在可行樹結(jié)構(gòu) (T,L,U) 中 , 如果樹弧中所有流量等于下界的弧都是遠(yuǎn)離根節(jié)點的 , 并且樹弧中所有流量等于上界的弧都不是遠(yuǎn)離根節(jié)點的 (可以稱為面向根節(jié)點的 ), 則 (T,L,U)是強可行樹結(jié)構(gòu) . 具體細(xì)節(jié) （ 略 ， 自己看書 ） 容量有界的情形 74 最高標(biāo)號預(yù)流推進(jìn)算法 說明 目前 ， 求解最小費用流問題的多項式時間算法中 ， 復(fù)雜度較低的幾個算法的最壞時間界為 ))l o g ()/l o g (( 2 nCmnnmO))l o g ()l o g( l o g( nCUnmO)))l o g ()(l o g(( nCnmnmO ?75 布 置 作 業(yè) 目的 掌握 網(wǎng)絡(luò)單純形算法 及復(fù)雜度； 內(nèi)容 《 網(wǎng)絡(luò)優(yōu)化 》 第 245251頁 25 （第 3講） 思考 21； 26； （不交） 76 。 WT如果旋轉(zhuǎn)是退化的 , 則我們只需要檢驗 ?{(p,q)}\{(k,l)}中的弧在 中是否為遠(yuǎn)離根節(jié)點的弧 . WT 由于出基弧 (k,l)為從 出發(fā)沿圈 W的正向前進(jìn)時第一次所遇到的 中的弧 , 所以上述問題的答案都是肯定的 , 即 是強可行樹 . pW T70 一般可以采用大 M方法 （ BigM Method） 構(gòu)造初始的強可行樹 . 加入一個人工節(jié)點 0， 并假設(shè)其供需量為 0. 然后對原網(wǎng)絡(luò)中的所有節(jié)點 i, 按如下步驟加入人工?。? 如果 di0, 則加入人工弧 (i,0)。 否則選定一個進(jìn)基變量(即選進(jìn)基弧 (p,q)). STEP 3. 選定一個出基變量 (即選出基弧 ), 如果找不到這樣的弧 , 則原問題是無界的 , 停止 。 17。:),(),( ?? ???? ?????? ijijijij ccSSjiccSSjiN(x)中的任意弧仍有 0： 保持互補松弛條件 ??ijc即令對 ,: ??? ??? iiSi52 算法思想 (case2) 若 e(S)? r(?,S): ?不變 ， 修改 x, 使得 e(S)嚴(yán)格減少 . 松弛算法 如果 e(j) 0, 則算法沿子樹中從 s 到 j 的一條增廣路增廣流量 . 從 (’)可知 , 這樣的修改不會改變 c(x,?) 的值 , 但使得 S中的節(jié)點上的總盈余減少 由 0e(S)? r(?,S), (S, )中至少有一條弧 (i,j)滿足 =0 ?ijcS如果 0 ? e(j), 則由 S的構(gòu)造方法可知節(jié)點 j 可 以加入到 S中 , 并重新開始下一輪迭代 . 53 松弛算法 – 步驟 （ Bertsekas， 1980’s) STEP 0 . 給出初始勢和初始流 : ? = 0, x = 0. STEP 1. 如果網(wǎng)絡(luò)中不含有任何贏余節(jié)點和虧空節(jié)點 ， 則已經(jīng)得到最優(yōu)解 , 計算結(jié)束；否則在殘量網(wǎng)絡(luò) N(x)中 ， 選擇一個贏余節(jié)點 s, 令 S={s}， 繼續(xù)下一步 . STEP 2. 如果 e(S) r(?,S), 則轉(zhuǎn) STEP 3。 e(i) =0時 , 稱節(jié)點 i為 平衡點 . )39。(),(??????ViiiAjiijij dxc ??如果 0, 則令 xij=0 (下界 )。?jic由算法 STEP3, 只有它為瑕疵弧時才進(jìn)行增廣 , 即 0, 因此增廣會嚴(yán)格減少其 Kilter數(shù) . 39。?ijc39。?ijc ijc 39。 若 ? 0,則 k’ij = lijxij ? uijxij ?ijc39。?ijc ijc 39。i? 39。 否則直接轉(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é)點上勢的修改 。 如果 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) ). 當(dāng) 時 : 如果 (i,j)是瑕疵弧 ( 0), 則其 Kilter數(shù)必然等于 (i,j)的殘留容量 : kij =uij(x) ijijijuxl ?? ?ijc當(dāng) xijlij時 : 如果 ? 0, 則 kij = uij(x)=lijxij。 節(jié)點上的數(shù)字表示節(jié)點的供需量 ). 對偶算法 ,例： 1 2 3 4 2 2 2 2 1， 1 1， 1 1， 2 1， 2 1 2 3 4 0 0 0 0 1， 1 1， 1 4 s 1， 2 t 4 2， 0 2， 0 2， 0 2， 0 x=0, ?=0,計算得到 d=(0,0,0,1,2,1), 修改得到 ?=(0, 0, 0, 1, 2, 1) （ uij， cij） 31 對偶算法 ,例 計算得到 d=(0,0,0,1,0,1) , 修改得到 ?=(0, 0, 0, 2, 2, 2) N0(x) 1 2 3 4 1， 1 1， 1 1， 2 2， 0 2， 0 2， 0 2， 0 1， 2 最大流流值為 2, 增廣 N(x) (1,0) (1,0) (1,1) (2,0) (1,1) (2,0) (1,2) (1,0) (1,0) (1,2) 32 對偶算法 ,例 x的流值達(dá)到 4 得到 最小費用流 最大流流值為 2, 增廣 N0(x) (1,0) (1,0) (2,0) (2,0) (1,2) (1,0) (1,0) (1,2) 33 對偶算法 – 復(fù)雜性分析 算法每次循環(huán)迭代修改弧上的流值和節(jié)點上的勢各一次 . 由于流值不可能超過 nU, 且任何節(jié)點上的勢不可能低于 nC, 因此總迭代次數(shù)不會超過 min{nU,nC}. 記求解 非負(fù)弧長網(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ù)雜度； 掌握原始 對偶算法的基本思想。 ??ijc27 對偶算法 – 正確性 上面幾個引理和討論說明，前面介紹的算法是正確的 . 即 討論 這一引理說明，只要 N(x)中從 s到 t存在有向路（增廣路），則 ?修改為 ?’ 后， 將會有新的弧增加到 N0(x)中 ， N0(x) 中從 s到 t存在有向路（增廣路），即可以對當(dāng)前流進(jìn)行增廣 。 Gowen (1961) 獨立提出的 STEP 0 . 取 x為任一 st可行流、且在同一流值的流中費用最小的流 (如 x=0). STEP 1. 若 x的流值達(dá)到 v, 結(jié)束；否則在殘量網(wǎng)絡(luò) N(x)中判別最小費用路 . 若無這樣的路 ,則流值不可達(dá)到 v, 結(jié)束；否則 STEP 2. STEP 2. 沿該最小費用增廣路增廣流量 (增廣后的流值不超過 v), 轉(zhuǎn) STEP 1. STEP1可用最短路算法：記最短路算法的復(fù)雜度為 S(n， m， C) STEP1~2最多執(zhí)行 O(v )次 復(fù)雜度 ？？？ 最大流流值不超過 nU， 本算法復(fù)雜度為 O(nU?S(n， m， C)) 采用特定的變尺度技術(shù) , 可以得到一些多項式時間算法 19 略 最小費用路算法 ,例： 20 仍然考慮傳統(tǒng)的單源單匯網(wǎng)絡(luò)的最小費用流問題 兩類約束分別引入對偶變量 ?和 z, 則這一問題的對偶問題為 原始 對偶算法 )(.),(,0),0,..)(m i n),(:),(:),(AjiuxtsiVitivsivdxxtsxcijijiAijjjiAjijijAjiijij???????????????? ??????)39。1 網(wǎng) 絡(luò) 優(yōu) 化 Network Optimization 清華大學(xué)數(shù)學(xué)科學(xué)系 謝金星 辦公室：理科樓 2206 （電話： 62787812） Email: 清華大學(xué)課號： 70420203（研） 第 7章 最小費用流問題 (Minimum Cost Flow Problem) 第 1講 2 ? 許多實際問題都可以轉(zhuǎn)化為 最小費用流 問題 S T 最小費用流 問題 的例子 公路交通網(wǎng)絡(luò)：車輛路線確定 最短路問題 最小費用流 問題 1輛車 多輛車 :車流 3 定義 在流網(wǎng)絡(luò) N=(V,A， L,U,D) 上增加如下的權(quán)函數(shù)： C： A? R為弧上的權(quán)函數(shù)，?。?i， j）對應(yīng)的權(quán) C（ i， j）記為 cij ，稱為?。?i