【文章內(nèi)容簡介】 ? 最大流問題的數(shù)學模型 網(wǎng)絡最大流問題 （ 1）網(wǎng)絡 1. 基本概念 給一個有向圖 D ＝ ( V , A ) ，在 V 中指定了一點稱為發(fā)點（記為sv），指定另一點稱為收點（記為tv），其余的點叫中間點。對于 A 中的弧（iv,jv），對應有一個( , ) 0ij i jc v v ?（簡記 c ij ），稱之為弧的容量。通常我們把這樣的 D 叫做網(wǎng)絡，記為 D = ( V , A , C ) 。 山東理工大學管理學院 ? 最大流問題的數(shù)學模型 網(wǎng)絡最大流問題 （ 2）網(wǎng)絡的流 1. 基本概念 定義在弧集 A 上一個非負函數(shù) f = { f ( iv ,jv)} ，并稱 f ( iv ,jv)為弧 ( iv ,jv) 上的流量，簡記 f ij 。流量的集合 f = { f ij } 稱為網(wǎng)絡的流，從發(fā)點到收點的總流量記為 v ( f ) 。 v s v t v 2 v 3 v 4 v 5 v 6 13( 6 ) 9 ( 4 ) 4( 2 ) 5( 1 ) 6( 3 ) 5( 5 ) 9 ( 6 ) 5( 1 ) 4( 1 ) 4( 2 ) 5( 1 ) 10( 2 ) 山東理工大學管理學院 網(wǎng)絡最大流問題 （ 3）可行流 設 f 為一網(wǎng)絡流，當 f 滿足下列條件時，稱為可行流。 容量限制條件 對每一弧 ( iv , jv ) ∈ A ，有 0 ≤ f ij ≤ c ij 平衡條件 對于中間點 iv （ i ≠ s , t ），流入量等于流出量，即 0),(),(?? ???? AvvjiAvvijijjiff對于發(fā)點 sv 有 )(),(),(fvffAvvjsAvvsjsjjs?? ????對于 收 點 tv 有 )(),(),( fvff Avv jtAvv tjtjjt??? ????式中， v ( f )稱為這個可行流的流量，即發(fā)點的凈輸出量或收點的凈輸入量。 山東理工大學管理學院 （ 4） 最大流 網(wǎng)絡 D上流量 v ( f )達到最大的可行流，稱為該網(wǎng)絡的最大流。 最大流問題其實是一個特殊的線性規(guī)劃問題。 ??????????? ??????????Ajvivijcijfi= t fvtsii= sfvjifijftsfvM a x),( 0)()(),( 0 )( )( ..)( 2. 最大流問題的數(shù)學模型： 網(wǎng)絡最大流問題 山東理工大學管理學院 網(wǎng)絡最大流問題 ? 最大流問題的解法 1. 有關(guān)的概念 飽和?。? fij = cij 非飽和?。? fij cij 零流弧 ： fij = 0 非零流弧： fij0 前向弧 （正向?。?，記為 μ+ ： 與鏈的方向一致的弧 后向弧 （反向?。?，記為 μ ： 與鏈的方向相反的弧 v s v t v 2 v 3 v 4 v 5 v 6 13( 6 ) 9 ( 4 ) 4( 2 ) 5( 1 ) 6( 3 ) 5( 5 ) 9 ( 6 ) 5( 1 ) 4( 1 ) 4( 2 ) 5( 1 ) 10( 2 ) 山東理工大學管理學院 網(wǎng)絡最大流問題 ? 最大流問題的解法 1. 有關(guān)的概念 增廣鏈 設 f = {fij}是一個可行流 ， μ是從 vs到 vt的一條鏈 。 若 μ滿足下列條件 ： （ 1） 前向弧 μ+中的每一弧都是非飽和弧 ， 即 （ 2） 后向弧 μ中的每一弧都是非零流弧 ， 即 ijij cf ??0則稱 μ是關(guān)于 可行流 f 的一條增廣鏈。 ijij cf ??0山東理工大學管理學院 網(wǎng)絡最大流問題 ? 最大流問題的解法 1. 有關(guān)的概念 截集 給定網(wǎng)絡 D = （ V ， A ， C ），若點集 V 被分割為兩個非空子集V 1 和 1V ，且 sv ∈ V 1 ， tv ∈ 1V ，則由始點在 V 1 中，終點在 1V 中的所有弧組成的集合稱為網(wǎng)絡的一個截集，記為（ V 1 ， 1V ）。 給定一截集（ V 1 ， 1V ），把截集（ V 1 ， 1V ）中所有弧的容量之和稱為這個截集的容量（簡稱為截量），記為 c （ V 1 ， 1V ），即 截量 ???),(),(1111),(VVvvijjicVVc山東理工大學管理學院 ? 最大流問題的解法 網(wǎng)絡最大流問題 2. 判斷一個可行流是否是最大流的條件 定理 可行流 f 是最大流的充要條件是不存在關(guān)于 f 的增廣鏈 。 此定理為我們提供了尋求網(wǎng)絡中最大流的一個方法： 若給了一個可行流 f，只要去判斷 D中有無關(guān)于 f 的增廣鏈。如果有增廣鏈，則可以改進 f，得到一個流量增大的新的可行流。如果沒有增廣鏈，則得到最大流。 最大流最小截量定理： 任一個網(wǎng)絡 D 中，從 sv 到 tv 的最大流的流量等于分離 sv 、 tv 的最小截集的容量。 山東理工大學管理學院 網(wǎng)絡最大流問題 ? 最大流問題的解法 3. 求網(wǎng)絡最大流的標號算法 Ford—Fulkerson 算法： 從一個可行流 f = {fij}出發(fā) ， 經(jīng)過 標號過程 與 調(diào)整過程 。 （ 1）標號過程 尋找增廣鏈的過程。 （ 2）調(diào)整過程 沿著增廣鏈調(diào)整可行流。 令調(diào)整量 θ是 l(vt)， 即 vt的第二個標號 。 ),( ,),( ,),( , ????????????? ???????jiijjiijjiijijvvfvvfvvff山東理工大學管理學院 網(wǎng)絡最大流問題 ? 最大流問題的應用舉例 例 用標號法求如下網(wǎng)絡的最大流，弧旁的數(shù)為容量。 ｏ ｏ ｏ ｏ ｏ v 1 ｏ ｏ v 2 v 3 v 4 v 5 v t v s 3 4 4 3 3 2 2 2 1ｏ 5 5 5 山東理工大學管理學院 網(wǎng)絡最大流問題 解 首先根據(jù)可行流的條件，給出初始可行流 ，圖中弧旁的數(shù)字為（ c ij , f ij ）。 2, 2 網(wǎng)絡的可行流 2, 1 ｏ ｏ ｏ ｏ ｏ v 1 ｏ ｏ v 2 v 3 v 4 v 5ｏ v t vs 3, 3 4, 4 4, 3 3, 1 3, 0 2, 2 1, 1 5, 3 5, 0 5, 5 山東理工大學管理學院 網(wǎng)絡最大流問題 （ 1）標號過程。針對當前可行流（ v ( f ) = 8）尋找增廣鏈。 ｏ ｏ ｏ ｏ ｏ v 1 ｏ ｏ v 2 v 3 v 4 v 5ｏ v t vs 3, 3 4, 4 4, 3 3, 1 3, 0 2, 2 2, 1 2, 2 1, 1 5, 3 5, 0 5, 5 ( 0,+ ∞ ) ( v 3 ,1) ( v 2 ,1) ( v 4 ,1) ( v 5 ,1) ( vs,1) ( v 1 ,1) 山東理工大學管理學院 網(wǎng)絡最大流問題 （ 2）調(diào)整過程 按 θ = 1 ，在增廣鏈 181。 上調(diào)整 f ，前向弧 f ij + θ ， 后向 弧 f ij ﹣ θ ，其余弧上的 f ij 不變。調(diào)整后 得到 下圖 所示的可行流 。 ｏ ｏ ｏ ｏ ｏ v 1 ｏ ｏ v 2 v 3 v 5ｏ v t v s 3, 3 4, 4 4, 4 3, 2 3, 1 2, 2 2, 0 2, 2 1, 1 5, 4 5, 1 5, 5 ( 0,+ ∞ ) ( v s ,1) 經(jīng)檢查，標號過程無法進行下去，算法終止，得到最大流如上圖所示。 山東理工大學管理學院 ? 作業(yè) 網(wǎng)絡最大流問題 求如下網(wǎng)絡的最大流（弧上的數(shù)字為容量）。 1 1 1 2 3 3 3 4 4 4 4 5 5 6 6 7 9 山東理工大學管理學院 最小費用最大流問題 ? 問題描述 ? 最小費用最大流算法 ? 應用舉例 山東理工大學管理學院 ? 問題描述 最小費用最大流問題 給定網(wǎng)絡 D = （ V , A , C ），在每一條?。?iv ,jv）∈ A 上，除容量 c ij 外還涉及單位流量費用 b（ iv ,jv）≥ 0 （簡記為 b ij ）。如果 f 是 D 的一個可行流，則其總費用為 ???Avvijijjifbfb),()(求 b ( f ) 為最小且流量為某確定值 v ( f )的可行流問題，稱為最小費用流問題；求 b ( f ) 為最小且流量 v ( f ) 為最大的問題，稱為 最小費用最大流問題 。 如果把最小費用看成約束條件，和最大流問題一樣，最小費用流問題也是一個線性規(guī)劃問題，并且求最小費用流實際上是求該線性規(guī)劃問題的可行解，求最小費用最大流問題實際上是求該線性規(guī)劃問題的最優(yōu)解。 山東理工大學管理學院 ? 最小費用最大流的算法 最小費用最大流問題 最小費用最大流的算法通常采用對偶算法，其具體算法步驟如下： 開始時取初始可行流為零流，即 v ( f 0 ) = 0 。在其對應的費用網(wǎng)絡 w ( f 0 ) 上，用求最短路的方法求出從sv到tv的最短路，即尋找最小費用的增廣鏈 μ 0 ；并在容量網(wǎng)絡上沿著 μ 0 調(diào)整流量，再在新的可行流 f 1 的基礎上構(gòu)造新的費用網(wǎng)絡 w ( f 1 ) ，重新尋找最小費用增廣鏈。 如此，在第 k 1 步后得到最小費用流 f k 1 ，再構(gòu)造對應的費用網(wǎng)絡 w ( f k 1 ) ，繼續(xù)尋找從sv到tv的最短路。若不存在最短路，則 f k 1就是最小費用最大流；若存在最短路，則在原流量網(wǎng)絡中得到相應的增廣鏈 μ ，在增廣鏈 μ 上對 f k 1進行調(diào)整，允許的調(diào)整量為： }m i n),(m i nm i n { 11 ?? ?? ?? kijkijij ffc ???山東理工大學管理學院 最小費用最大流問題 調(diào)整后新的可行流 f k 為： ?????????????????????),( ,),( ,),( ,111jikijjikijjikijkijvvfvvfvvff再對 f k 重復上述步驟。 山東理工大學管理學院 ? 應用實例 最小費用最大流問題 求下圖所示的網(wǎng)絡中從 sv 到 tv 的最小費用最大流，其中每條弧上的數(shù)字為（ b ij ， c ij ）， b ij 為單位費用， c ij 為容量。 v1 v4 v2 v 3 v s v t ( 20 , 3) ( 22 , 10 ) ( 12 , 8) ( 15 , 7) ( 14 , 6) ( 18 , 4) ( 25 , 5) ( 13 , 5) ( 1 1 , 6) 山東理工大學管理學院 最小費用最大流問題 解 （ 1 ）取初始可行流 f 0 = 0 ，構(gòu)造相應的費用網(wǎng)絡 w ( f 0 ) ，如下圖所示。 （ 2 ）在 w ( f 0 ) 上用 D ij k s t r a 算法求出 sv 到 tv 的最短路（即最小費用鏈），如圖中雙線所示： sv → 1v → 3v →