【正文】 行流 f ,若 u 滿足 ????? ??? ??? ?? ,)(0,),( )(0,),( 中各弧是非零弧即在弧中各弧是非飽和弧即在弧ucfuvvucfuvvijijjiijijji 則稱 u 為關于 f 的可增廣路 (鏈 ),否則稱為不可增廣路 . 割 4 從網絡 D 中分離發(fā)點和收點的一個弧的集合稱為 D 的一個割 .或者更直觀的說割是網絡 D 從 sv 到 tv 的必經之路 .因此割集中弧的容量大小對全 網絡的流量起到至關重要的作用 .顯然易得出 :最大流的值不會大于最小割的容量 ,即 ? ? ? ?,)(m inm ax , kcf ts ? () 其中 ??kc 表示割集中弧的容量 . 為了使全網絡流量最大 ,必須設法利用割集中弧的全部容量 ,使得 : ? ? ? ?.)(m inm a x , kcf ts ? () 最大流與最小割的求解 為求解文中提出的問題 ,就是要在網絡 D 中求出最大流和最小割 ,從而用最大流驗證能否滿足施工需要 ,用最小割在割集弧上采取開拓、加寬等措施以加大容量 ,提高全運輸線路上的流量 . 求最大流和最小割的思路 先假設網絡 D 中的任意可行流 ,然后自此出發(fā)設法逐漸增大流值 .如果 sv 到 tv中存在一條路 ,其所有的前向弧未飽和 ,所有后向弧的流具有正值 ,此時總有可能使這條路的前向弧的流增加一個正整數 ? ,所以后向弧的流減少一個 ? ,而且可以同時保持全部弧的流為正值且不超過弧的容量 .所以這樣不會破壞前面所要求的流的相容 條件 ,同時也不會影響不屬于此路的其他弧的流 .但是 D 自 sv 到 tv 的流值則增加了 ? ,所以總有可能逐次增加 tsf, ,使 得 D 自 sv 到 tv 的全部路中任何一條路到至少有一個前向弧被飽和或一條后向弧的流為零 ,變?yōu)椴豢稍鰪V路為止 .當自 sv 到 tv 無可增廣路時 , tsf, 就不再增大 ,即 tsf, 達到最大 .否則總可以按照上述步驟繼續(xù)增大 tsf, ,最后求得最大流 ,最小割的流量滿足 : ? ? ? ?)(m inm ax , kcf ts ? ??.8 () 5 用標記法求最大流和最小割 確定最大流的標記法分為兩個過程 :一個是標記過程 ,二是增長過程 ? ?75 . 1. 標記過程 : 標記過程的目的是尋找可增廣路 ,求出最小割 . (1) 給 sv 標記為 ( , , )s?? ,此 時稱 sv 被標記 ,未檢查 .其他各點未標記 ,未檢查 .其中，第一個記號是代表下標為 i ,即要檢查的下標 .第二個記號用“ +” ,“ ”是代表 :若 ( , ) ( , ) 0c i j f i j??則記之為“ +” 。, ????? ??? ??ijijijijijji cf cfbw () ????? ??? ??? .00, ijijijij ffbw () 于是在 D 中尋求關于 f 的最小費用增廣路等價于在賦權圖 ()wf 中尋求以 sv到 tv 的最短路 .長度為 ? 的弧可以從 ()wf 中略去 . 計算步驟 1. 取 )0(f = 0。割為 : ? ?1 1 1 3 6 2 6 5( , ) ( , ) , ( , ) , ( , ) , ( , )stv v v v v v v v v v? , () 1 1 ,m i n ( , ) 1 1 4 2 1 0 2 7 m a x stv v f??? ? ? ? ? ? ??. () 圖 3 第一次標記過程圖 圖 4 第二次標記過程圖 10 圖 5 最大流與最小割圖 最小費用最大流運輸方案的設計 對圖 2 取初始可行流 0)0( ?f ,見圖 6 所示 .構造賦權有向圖 (0)()wf ,如圖 7所示 .觀察可知從 sv 到 tv 的最短路為 36( , , , )stv v v v ,如圖 7 中粗線 所示 .D 中與圖 7中最短路相應的增廣路 36( , , , )stu v v v v? ,在 u 上對 )1(f 進行調整 ,調整流量為 4?? ,調整后見圖 8 所示 .再構造 賦權有向圖 (1)()wf ,如圖 9 所示 .重復上述步驟直至(6)()wf ,如圖 11 所示 . 圖 6 賦權圖 0)0( ?f 11 圖 7 賦權有向圖 (0)()wf 圖 8 賦權圖 )1(f , (1)( ) 4wf ? 圖 9 賦權有向圖 (1)()wf 12 圖 10 賦權圖 )6(f , (6)( ) 27wf ? 圖 11 賦權圖 (6)()wf 圖 11 中 (6)()wf 已經經過六次調整 ,為了簡單起見 ,中間幾步省略 .圖中(6)()wf 已經不存在 sv 到 tv 的最短路 ,所以 )6(f 為最小費用最大流 .每日最大上壩土石方量為 27 萬 3m ,最小費用為 34,000 元 . 按照上述方法求出運輸線路通行能力下的最大流量 .若能滿足施工需求量 ,按照此運輸方案實施 .若不能滿足 ,則需要開拓和加大割集路段的容量或再增加路線 .本例運輸線路中影響提高運輸流量的關鍵路段時前面所分析得到的割集路段 .即料場 sv 到工程指揮部 1v 段 ,大橋 3v 到壩腳 6v 段 ,工人生活區(qū) 2v 到壩腳 6v 段 ,泄洪口施工區(qū) 5v 到壩上 tv 段 .要提高土石運輸量就要采取措施加大這些段的容量 . 13 最優(yōu)的運輸方案 ,不僅要考慮運輸量最大 ,還要使運輸方案整體達到最優(yōu) ,即達到最小費用最大流 ??8 .本例中最小費用最大流運輸方案如圖 10 所示 ,最大流量為 27 萬 3m /日 ,最小費用為 34,000 元 .這個運輸方案比圖 5 中計算的最大流量每日節(jié)約運輸費用 600 元 .當然執(zhí)行這個方案要在原實施基礎上對有關路段采取一定的措施 . 防洪物資運輸問題 防洪物資運輸模型的建立 防洪物資運輸要求在滿足各水庫防洪物資需求的前提下 ,以最低的運輸費用將盡可能多的防洪物資從各倉庫運送到各水庫大壩 ,這要求考慮三個問題 : 1. 滿足各水庫大壩的最低物資需求 。iq 為第 j 個水庫所至少需要的物資量 。規(guī)定從第 j 個水庫到 t 點的道路運輸能力為 ?? ,從第 j 個水庫到 t 點的道路的單位運輸費用為 ,也可以應用最小費用最大流算法 ??11 對模型進行求解 .求解步驟如下 : 1.