【正文】 ijc0??ijc22 引理 最優(yōu)性條件 ()~()等價于 ， 對于 N(x)中任意的 (i,j)弧 , 0 ??ijc 假設 ()~()成立 , 則對于原網(wǎng)絡中的一條弧 (i,j), 當 0時 , 即 ，所以根據(jù)條件 ()有 = , 即(i,j)弧為飽和弧 , 所以它不屬于殘量網(wǎng)絡 N(x). ?ijcijji c?? ?? ijx iju 假設 N(x)中任意的 (i,j)弧 , 0. 對于原網(wǎng)絡中的弧 (i,j): ??ijc當 時 ， 即 0, 所以 = =( )= 0, 因此 (j,i)弧不屬于殘量網(wǎng)絡 N(x). 所以 =0. ?ijcijji c?? ???jicijjic ?? ?? jiijc ?? ?? ?ijcijx當 時 ， 即 0, (i,j)弧不屬于殘量網(wǎng)絡 N(x), = ?ijcijji c????ijx iju當 時 ， (i,j),(j,i)弧均屬于殘量網(wǎng)絡 N(x). 所以 , 所以 0??jic0??ijcijji c?? ??ijij ux ??023 思路： 從流值不一定達到 v的 st可行流開始 ， 迭代中始終保持最優(yōu)性條件 ()~()成立 ， 直到流值達到 v為止 . 迭代包括兩個方面：對弧上流的增廣；對節(jié)點上勢的修改 當 N0(x)中找不到增廣路且流值小于 v時，必須進行下一個過程，修改節(jié)點上的勢 . 原始 對偶算法就是在允許網(wǎng)絡 N0(x)中尋找增廣路并進行增廣 （ 最大流 ） 為保證流的增廣過程中始終保持最優(yōu)性條件 ()~()，原始 對偶算法只沿滿足 的弧增廣流量 . ijji c?? ??N(x)中滿足 的弧組成的子網(wǎng)絡稱為允許網(wǎng)絡（ Admissible Network），記為 N0(x) = ijji c?? ??? ?ijijijji uxcAji ???? ,|),( ?? ? ?0,),(|),( ???? ijijji xcAjiij ??? 對偶算法 – 基本思想 N0(x)中的弧就是 N(x)中滿足 =0的弧 ?ijc24 對偶算法 – 基本思想 當 N0(x)中找不到增廣路且流值小于 v時，必須修改節(jié)點上的勢 . ?保持最優(yōu)性條件 ()~()， ?并且希望修改后 N0(x)中可以找到增廣路 可以證明 , 修改后最優(yōu)性條件 ()~()仍然成立，且將會有新的弧增加到 N0(x)中 . 希望把 N(x)中一些不滿足 =0的弧也納入 N0(x)中 . ?ijc以 為弧長在 N(x)中計算從節(jié)點 s到所有節(jié)點 i的最短路路長 d(i). ?ijc)(39。 此時網(wǎng)絡可稱為 容量 費用網(wǎng)絡 (一般仍可簡稱為 網(wǎng)絡 ),記為 N=(V,A,C， L,U,D). 最小費用流問題 di 0:供應點 (supply node)或源 (source)、起始點或發(fā)貨點 di 0:需求點 (demand node)或匯 (sink) 、 終止點或吸收點 di ＝ 0:轉運點 (transshipment node)或平衡點、中間點 可以把 L? 0的網(wǎng)絡轉化為 L=0的網(wǎng)絡進行研究 (思考？ ) 除非特別說明 , 假設 L=0,網(wǎng)絡簡記為 N=(V,A,C， U,D). 4 定義 （ 容量 費用網(wǎng)絡中的 流 (flow) 的定義同前一章 ） 流 x的 （ 總 ） 費用 定義為 通常又稱為 轉運問題 (transshipment problem)或 容量受限的轉運問題 (capacitated transshipment problem). 最小費用流問題就是在網(wǎng)絡中尋找總費用最小的可行流 . 最小費用流問題 ???Ajiijij xcxc),()(..)(m in),(tsxcxcAjiijij??? )(,),(:),(:Vidxx iAijjjiAjijij ???? ????)(),(,0 Ajiux ijij ????引理 最小費用流問題存在可行流的必要條件 .0??? Vi id經(jīng)典 的最小費用流問題：單源單匯 (起點 s， 終點 t)， 尋找從 s流到 t的給定流量 (或最大流量 、 最小流量等 )的最小費用流 . vdvd ts ??? , ),(0 tsid i ??線性費用網(wǎng)絡 思考： 經(jīng)典問題與一般問題有什么關系？是否等價？ 5 例 最短路問題 在有向網(wǎng)絡中 ， 令所有弧上容量下界為 0， 容量 （ 上界 ） 為 1，并令圖中節(jié)點 s的供需量為 1， 節(jié)點 t的供需量為 1， 則： 從 s到 t的一條有向路正好對應于網(wǎng)絡中的一個可行流 x （ 弧 (i， j)位于 st路上： xij =1；弧 (i， j)不在 st路上： xij=0） . 如果再令所有弧上的 (單位流量 )的費用為 “ 弧長 ” , 則此時的最小費用流問題就是第五章討論過的最短路問題 . 在第五章我們正是用這樣的方式對最短路問題進行建模的 最小費用流模型的特例及擴展 P s t 6 例 最大流問題 設 s為起點 ,t為終點 ,增加弧 (t,s), 令 最小費用流模型的特例及擴展 s t ????? tsts uc ,1而令所有其他弧上的費用為 0, 所有頂點上的供需量 (外部流量 )全為 0. 7 例 運輸問題 (transportation Problem) 又稱 Hitchcock問題 （ Hitchcock,1941年 ） 完全二部圖 只有源和匯 沒有中間轉運點 S T 最小費用流模型的特例及擴展 )(.),(,0)(,)(,..)(m i n),(:),(:),(AjixTjbxSiaxtsxcijjAjiiijiAjijijAjiijij????????????如果每條弧上還有容量 (上下限 )的限制 , 則稱為 容量受限的運輸問題 (capacitated transportation problem). 有解的必要條件 ?????Tj jSi iba可以不失一般性 ?????Tj jSi iba指派問題 (assignment problem) ||||,1 TSba ji ???8 最小費用流模型的特例及擴展 （ 1） 當一定的流量流過一條弧時 ， 該弧上導致的總費用與流量大小成線性 正比 關系 ， 這樣的流網(wǎng)絡一般稱為 線性費用網(wǎng)絡 . 如果當一定的流量流過一條弧時 ， 該弧上導致的總費用不一定與流量大小成線性正比關系 ， 而是流量大小的一個凹 （ 或凸 ）函數(shù) ， 則這樣的網(wǎng)絡稱為 凹 （ 或凸 ） 費用網(wǎng)絡 ， 相應的最小費用流問題稱為凹 （ 凸 ） 費用網(wǎng)絡上的最小費用流問題 . （ 2） 當流量流過一條弧時 ， 流出該弧的流量 （ 即流入該弧終點的流量 ） 與進入該弧的流量 （ 即流出該弧起點的流量 ） 相等 . 如果當流量流過一條弧時 ， 流出該弧的流量是進入該弧的流量的一個 線性函數(shù) ， 即流出該弧的流量是對進入該弧的流量按一定比例進行放大或縮小的結果 ， 則這樣的流網(wǎng)絡一般稱為 帶增益 (或盈虧 )的流網(wǎng)絡 （ flow with gain work） . 增益除了可以發(fā)生在 弧 上 ， 類似地可以考慮增益發(fā)生在 節(jié)點 上 9 最小費用流模型的特例及擴展 最 小 費 用 流 問 題 指派 問題 運輸 問題 最大流 問題 最短路 問題 帶增益的 最小費用流問題 線性 規(guī)劃 問題 凹費用網(wǎng)絡的最小費用流問題 凸費用網(wǎng)絡的最小費用流問題 狹義模型 廣義模型 凸 規(guī) 劃 10 ?單源單匯網(wǎng)絡 ?可行流 x的 流量 （或 流值 ）為 v=v（ x） = ds = dt ?如果我們并不給定 ds 和 dt , 則網(wǎng)絡一般記為 N=(s, t,V,A,C,U) ?容量可行且轉運點流量守恒的流稱為 st可行流 ，有時為了方便也稱為可行流 . ?最小費用流問題就是在網(wǎng)絡 N=(s,t,V,A,C,U)中計算流值為 v的最小費用流 x ?或者當不給定流值時 , 計算流值最大的最小費用流 x (此時流 x稱為 最小費用最大流 ). 消圈算法與最小費用路算法 最小費用最小流 ? 11 消圈算法與最小費用路算法 定義 對網(wǎng)絡 N=(s,t,V,A,C,U)中給定的 st可行流 x， 網(wǎng)絡 N關于流x的 殘量網(wǎng)絡 N(x) = (s, t, V, A(x), C(x), U(x)) , 其中 A(x), C(x) ， U(x)定義如下： （ residual work， 或增量網(wǎng)絡或輔助網(wǎng)絡 ） 討論算法復雜度時 ， 假定 : ?弧 （ i， j） ?A時 ， 弧 （ j， i） ? A； c ij = cji ?A（ x） =A (允許容量為 0的弧仍然保留在網(wǎng)絡中就可以了 ) ? ? ? ?0,),(|),(,),(|),()( ????? jiijij xAijjiuxAjijixA ??????????,0,),(,),(,)(jijiijijijijij xAijxuxAjixuxu其中稱 , uij(x)為弧 (i,j)上的 殘留容量 (residual capacity). ?????????,0,),(,),(,)(jijiijijijij xAijcuxAjicxc12 定義 W的費用為 ?對于 N(x)中的任何一個有向圈 W, 它一定對應于原網(wǎng)絡 N中的一個增廣圈 (增廣弧構成的圈 )； 通過沿 W對當前流 x進行增廣 ， 可以獲得流值相等的 st可行流 y. 消圈算法的思想 則當增廣的流量為 ?時 只要 N中存在費用為負數(shù)的增廣圈 W，即 C（ W） 0， 則可以通過沿 W 對當前流 x 進行增廣 ， 獲得流值相等但費用更小的 st可行流 y. ??? Wji ij xcWC ),( )()()()()( WCxcyc ??? ?13 設 x0為不同于的可行流 ， 但費用低于 x的費用 ， 即 消圈算法 (cyclecanceling algorithm) 定理 可行流 x為最小費用流的充要條件是 N(x)中不存在負費用增廣圈 . vxvxv ?? )()( 0 )()( 0xcxc ?令 x1 =x0x, 則 ， 即令 x1為網(wǎng)絡 N中的循環(huán)流 . 0)()()(,0 011 ???? xvxvxvx一個循環(huán)流一定可以表示為至多 m個非零圈流之和 ， 所以可以將 x1表示為 r個非零圈流之和 （ ） 。 設對應的有向圈為 Wk， mr ??1????rkkkij WjiWvx11 }),(|)({???????????? rkkrkkkAjiijijAjiij WCWjiWvcxcxc11),(1),(1 )(}),(|)({)(?????? rkkWCxcxcxcxc110 )()()()()(至少存在一個費用為負的增廣圈 . 矛盾 必要性是顯然的 . 反證法證明充分性： 14 N(x)中找負圈可用最短路算法 (如 BellmanFord算法 ， O(m n ) ) 則該算法的復雜度為 O(n m