【導(dǎo)讀】許多實際問題都可以轉(zhuǎn)化為最小費用流問題。R為弧上的權(quán)函數(shù)，弧（i，j）對應(yīng)的權(quán)C（i，j）記。為cij，稱為?。╥，j）的單位流量的成本或費用;0的網(wǎng)絡(luò)轉(zhuǎn)化為L=0的網(wǎng)絡(luò)進行研究(思考？除非特別說明,假設(shè)L=0,網(wǎng)絡(luò)簡記為N=.最小費用流問題就是在網(wǎng)絡(luò)中尋找總費用最小的可行流.引理最小費用流問題存在可行流的必要條件.0??小費用流問題就是第五章討論過的最短路問題.設(shè)s為起點,t為終點,增加弧(t,s),所有頂點上的供需量全為0.可以不失一般性??大小成線性正比關(guān)系，這樣的流網(wǎng)絡(luò)一般稱為線性費用網(wǎng)絡(luò).益(或盈虧)的流網(wǎng)絡(luò).如果我們并不給定ds和dt,則網(wǎng)絡(luò)一般記為N=. 容量可行且轉(zhuǎn)運點流量守恒的流稱為s-t可行流，有時為了方。或者當(dāng)不給定流值時,計算流值最大的最小費用流x(此時流x. 其中稱,uij為弧(i,j)上的殘留容量.

　　

【正文】 矛盾 . 因此 B1所對應(yīng)的n1條弧一定是連通的 (不考慮方向 ), 即這些弧構(gòu)成一棵支撐樹 . 充分性 . B1所對應(yīng)的 n1條弧構(gòu)成一棵支撐樹 , 則 r(B1)=n1. 因此是一組基 . 60 把 B1所對應(yīng)的弧集合 (支撐樹 )用 T表示 ， 則 ： ?所有非樹弧 （ 非基弧 ） 對應(yīng)于非基變量 , 其上的流量為 0。 ?只有 T中的弧 （ 樹弧 ， 或稱基弧 ） 對應(yīng)于基變量 . 給定支撐樹后 , 如何 確定樹弧上的流量并使之滿足可行條件 ？ 算法的一般思路 – 流的計算 流 x不一定是可行的 , 即某些樹弧上的流量可能為負數(shù) . 我們把使得相應(yīng)的流 x為可行流的基稱為 可行基 , 支撐樹稱為 可行樹 . 算法只對 可行樹 操作 ！ T j xij=dj i 61 勢的計算 容量無限 ， 互補松弛條件 ： 算法的一般思路 如何獲得 ? (即節(jié)點上的勢 )？ 單純形算法中 , 檢驗數(shù)的值為 (C?B), 這里 ?為對偶變量 . 對于最小費用流問題 , (i,j)弧對應(yīng)的檢驗數(shù)的值為 jiijij cc ??? ???當(dāng) = 0 時 ， =0 ； () 當(dāng) 0 時 ， = 0 ； () ijxijx ?ijc?ijc?設(shè)給定了一個基本可行解 x, 基矩陣所對應(yīng)的可行樹為 T. 由于只有樹弧上的流量可以為正數(shù) , 所以只有樹弧才可能滿足 (). ? 支撐樹上的弧共有 (n1)條 , 而對偶變量 (節(jié)點上的勢 )共有 n個 . 在相差一個常數(shù)的意義下 , 由 T中的弧滿足 =0可以唯一地確定對偶變量 . jiijijcc ??? ???可以任意選定一個節(jié)點 （ 這一節(jié)點通常稱為 “ 根 ” （ Root）） , 令它的勢為 0。 然后利用 ()計算與它相鄰的其它節(jié)點上的勢 , 如此重復(fù)就可以方便地獲得所有節(jié)點上的勢 . 如果此時使得 ()也成立 , 則 x就是原問題的最優(yōu)解 . 62 算法的一般思路 – 旋轉(zhuǎn)變換 ?W為一個負費用圈 , 所以沿 W增廣流量將會使得總費用下降 . ?為了在 W中找出一條弧出基 , 我們應(yīng)當(dāng)令增廣的流量等于 W 所有弧上當(dāng)前流量中的最小值 , 而取到該最小值的弧出基 ? 如果 W =?, 則原問題是無界的 , 即最小費用可以趨于負無窮 為了找出一條弧出基 , 我們可以看出 T?{(p,q)}一定含有唯一的圈W, 我們把弧 (p,q) 的方向定義為 W的方向 . W的費用為 若 x不最優(yōu) , 則存在一條非樹弧 (p,q)使得 ()不成立 , 即 0， 弧 (p,q)可以進入基 . ?pqc?????pqWjijiijWjijiijWjiijWjiij cccccWC ????????? ???????? ???? ),(),(),(),()()()(63 STEP 0. 獲得一個初始的可行樹 T及對應(yīng)的基本可行解 x 步驟 STEP 1. 計算對偶變量 ?. 算法的一般思路 STEP 2. 判斷是否最優(yōu)解 , 若是 , 則停止 。 否則選定一個進基變量(即選進基弧 (p,q)). STEP 3. 選定一個出基變量 (即選出基弧 ), 如果找不到這樣的弧 , 則原問題是無界的 , 停止 。否則進行下一步 . STEP 4. 設(shè) W為 T?{(p,q)}所含的圈 . 沿 W的正向增廣流量 , 即修改x 及對應(yīng)的可行樹 T, 回到 STEP 1. 問題 獲得一個初始的可行樹 T及對應(yīng)的基本可行解 x ？ 退化與循環(huán) ？ 90%以上退化 容量有界情形 ？ 復(fù)雜度 ？ 一般非為多項式算法 ， 但可以設(shè)計多項式算法 64 略 算法的一般思路 – 例 65 計算測試表明 ， 網(wǎng)絡(luò)單純形法中往往 90%以上的旋轉(zhuǎn)是退化的 . 能否要求 每次所操作的可行樹 “ 都不相同 ” ？ 處理退化的方法 定義 假定計算節(jié)點上的勢時所選定的根節(jié)點是固定的 . 對于可行樹 T中的一條樹弧 (i,j), 如果 T中從根到 j的路通過節(jié)點i， 則 (i,j)稱為遠離根節(jié)點的弧 （ Downward Pointing Arc） . 如果 T中的所有流量為 0的弧都是遠離根節(jié)點的弧 ， 則稱可行樹 T為 強可行樹 （ Strongly Feasible Spanning Tree） . 例 假設(shè)弧上的數(shù)字表示當(dāng)前可行流 . 節(jié)點 1為根節(jié)點 . T1={(1,3),(3,2),(3,4)} 為 強 可行樹 , T2={(1,3),(2,3),(3,4)}不是強可行樹 ,因為 T2中 (2,3) 不是遠離根節(jié)點的弧 . 1 2 3 4 0 0 0 0 2 2 66 引理 如果網(wǎng)絡(luò)單純形算法中生成的所有可行樹都是強可行樹 ， 則這些樹互不相同 . 處理退化的方法 如果 T為生成樹 ， r為根節(jié)點 ， 記 證明 : 如果網(wǎng)絡(luò)單純形算法中的旋轉(zhuǎn)變換不是退化的 ， 則相應(yīng)的可行樹對應(yīng)的可行流費用互不相同 ， 因此這些樹也一定互不相同 . 所以 ， 我們只需要考慮旋轉(zhuǎn)變換退化的情況 . ?? ?? Vi irT )()( ???考慮算法過程中連續(xù)生成的兩棵強可行樹 T， =T ?{(p,q)}\{(k,l)}, 即 (p,q)為進基弧 , (k,l)為出基弧 , 且從 T到 的旋轉(zhuǎn)是退化的 . TT67 處理退化的方法 記 對應(yīng)的勢為 , 根據(jù)勢的確定方法 , 可以得到 (留作練習(xí) ): ?T當(dāng) i?Tp 時 , = ?i 。 i?當(dāng) i?Tq 時 , = ?i + 。 i? ?pqc旋轉(zhuǎn)變換前后 , (p,q)上的流量都是 0, 由于 是強可行樹 , 所以 (p,q)弧一定是遠離根節(jié)點 r的弧 . (p,q)弧將 分解為兩棵子樹 和 , 并且 p, q分別屬于 和 , 則 r ? . TT pT qTpT qT pT因此 , T和 是兩棵不同的強可行樹 . T所以 = + | | （ 0） )(T? )(T?qT?pqc)(T? ?pqc q p pT qTTr k l 68 首先 ， 初始的基本可行解是對應(yīng)于一棵強可行樹； 其次 ， 我們要求旋轉(zhuǎn)變換只生成強可行樹 . 處理退化的方法 設(shè)旋轉(zhuǎn)之前 ， 強可行樹為 T， (p,q)為進基弧 , T ?{(p,q)}包含的圈為 W. 假設(shè) W ??， 令 ?=min{xij|(i,j) ?W }, ={(i,j)| xij = ?} , 則 為所有可能的出基弧的集合 . WWT q p r k l p記 是 T中從根節(jié)點 r到節(jié)點 p的路與圈 W的第一個交點 , 令出基弧 (k,l)為從 出發(fā)沿圈 W的正向前進時第一次所遇到的 中的弧 pp W69 處理退化的方法 T q p r k l p下面證明 = T ?{(p,q)}\{(k,l)}仍然是強可行樹 . T如果旋轉(zhuǎn)是非退化的 , 則我們只需要檢驗 \{(k,l)}中的弧在 中是否為遠離根節(jié)點的弧 。 WT如果旋轉(zhuǎn)是退化的 , 則我們只需要檢驗 ?{(p,q)}\{(k,l)}中的弧在 中是否為遠離根節(jié)點的弧 . WT 由于出基弧 (k,l)為從 出發(fā)沿圈 W的正向前進時第一次所遇到的 中的弧 , 所以上述問題的答案都是肯定的 , 即 是強可行樹 . pW T70 一般可以采用大 M方法 （ BigM Method） 構(gòu)造初始的強可行樹 . 加入一個人工節(jié)點 0， 并假設(shè)其供需量為 0. 然后對原網(wǎng)絡(luò)中的所有節(jié)點 i, 按如下步驟加入人工?。? 如果 di0, 則加入人工弧 (i,0)。 否則加入人工弧 (0,i) . 初始的基本可行解 記所有人工弧的集合為 , 所有人工弧上的費用假定為一個充分大的正數(shù) M, 并稱原網(wǎng)絡(luò)假入人工弧后的新網(wǎng)絡(luò)為人工網(wǎng)絡(luò) . )0(T 0)0(T 是人工網(wǎng)絡(luò)的一棵 (初始 ） 強可行樹 )0(T71 由于 M是一個充分大的正數(shù) , 因此當(dāng)算法終止時 , 有三種情況 : (1) 人工網(wǎng)絡(luò)上的最小費用流問題有有界的最優(yōu)解 , 且最優(yōu)解中所有人工弧上的流量為 0, 則原問題也有有界的最優(yōu)解 , 且人工網(wǎng)絡(luò)上非人工弧上的流量正好就是原問題的最優(yōu)解 . (2) 人工網(wǎng)絡(luò)上的最小費用流問題有有界的最優(yōu)解 , 且最優(yōu)解中某些人工弧上的流量不為 0, 則原問題是不可行的 . 實際計算中 M取多大才是 “ 充分大 ” ？ 理論上： M (n 1)C/2 初始的基本可行解 (3) 人工網(wǎng)絡(luò)上的最小費用流問題沒有有界的最優(yōu)解 (即最優(yōu)值趨向負無窮 ), 則原問題也沒有有界的最優(yōu)解 (即最優(yōu)值趨向負無窮 ). 實用中 ： 自適應(yīng)策略 先取 M為某中等規(guī)模大小的正數(shù)計算 。 若最優(yōu)解中有人工弧上的流量不為 0, 則增加 M的規(guī)模重新計算 . 如果 M的取值不足夠大 , 即使原問題有有界的最優(yōu)解 , 人工網(wǎng)絡(luò)上的最小費用流問題可能也會沒有有界的最優(yōu)解 (即最優(yōu)值趨向負無窮 ). 72 基可以用所有弧的一個劃分 (T,L,U)來表示 , 其中 T是一棵支撐樹 , L是非樹弧中流量等于下界的弧的集合 , U是非樹弧中流量等于上界的弧的集合 . 三元組 (T,L,U)可以稱為基結(jié)構(gòu) (有時也直接簡稱為基 ), 或支撐樹結(jié)構(gòu) . 最高標(biāo)號預(yù)流推進算法 用支撐樹表示基 , 只有樹弧上的流量可以不等于下界和上界 , 而所有非樹弧上的流量只能等于下界或上界 . CxmindBxts ?..給定一個基結(jié)構(gòu) (T,L,U), 非樹弧上的流量已經(jīng)確定 , 所以樹弧上的流量也可以方便地根據(jù)節(jié)點上的流量守恒約束計算出來 , 并且也是唯一的 . 如果這些流量同時滿足容量的上下界約束 , 則 (T,L,U)是可行支撐樹結(jié)構(gòu) (簡稱 可行樹結(jié)構(gòu) ). 節(jié)點上的勢也可以與前面的討論完全類似地進行計算 . 容量有界的情形 ijijij uxl ??73 初始的強可行樹結(jié)構(gòu)：仍然可以構(gòu)造人工網(wǎng)絡(luò) , 采用大 M方法 . 最高標(biāo)號預(yù)流推進算法 定義 假定計算節(jié)點上的勢時所選定的 “ 根節(jié)點 ” 是固定的 . 在可行樹結(jié)構(gòu) (T,L,U) 中 , 如果樹弧中所有流量等于下界的弧都是遠離根節(jié)點的 , 并且樹弧中所有流量等于上界的弧都不是遠離根節(jié)點的 (可以稱為面向根節(jié)點的 ), 則 (T,L,U)是強可行樹結(jié)構(gòu) . 具體細節(jié) （ 略 ， 自己看書 ） 容量有界的情形 74 最高標(biāo)號預(yù)流推進算法 說明 目前 ， 求解最小費用流問題的多項式時間算法中 ， 復(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