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