【正文】 ) (vs , 3) (v1 , 1) (v2 , 1) (v4 , 1) vs v1 vt v5 v4 v3 v2 （ 4, 4） （ 10, 7） （ 3, 3） （ 3, 3） （ 3, 3） （ 4, 4） （ 1, 1） （ 2, 1） （ 5, 5） （ 4, 4） （ 7, 6） （ 8, 8） (0 , +?) (vs , 3) 首先給 vs 標號 （ 0， +∞） ， 看 vs,給 v3 標號（ vs ,3） 。 看 v3,在弧 （ v3 ,v2） 上 ， f32=c32,?。?v3 ,v5） 上 ， f35= c35,均不符合條件 。 因此標號過程無法進行下去 ， 不存在從 vS到 vt的增廣鏈 ， 算法結束 。 最大流量 f * = 14 。 167。 在實際的網(wǎng)絡系統(tǒng)中 ， 當涉及到有關流的問題的時候 ， 我們往往不僅僅考慮的是流量 ， 還經(jīng)常要考慮費用的問題 。 比如一個鐵路系統(tǒng)的運輸網(wǎng)絡流 ， 即要考慮網(wǎng)絡流的貨運量最大 ， 又要考慮總費用最小 。最小費用最大流問題就是要解決這一類問題 。 我們首先考察 ， 在一個網(wǎng)絡 D中 ， 當沿可行流 f 的一條增廣鏈 μ， 以調(diào)整量 θ=1改進f ， 得到的新可行流 f ` 的流量 ， 有 v(f ` )= 設一個網(wǎng)絡 D=（ V， A， C） ， 對于每一個弧 (vi ,vj )∈ A ,給定一個單位流量的費用 bij? 0 ， 網(wǎng)絡系統(tǒng)的最小費用最大流問題 ， 是指要尋求一個最大流 f ， 并且流的總費用 達到最小 。 ? ?? Avv jijiji fbfb ),()(=v(f )+1，而此時總費用 b(f ` )比 b(f)增加了 ? ?? ??? ????????????? ?? ?jijijijijijijijibbffbffbfbfb )()()()(結論： 如果可行流 f 在流量為 v(f )的所有可行流中的費用最小，并且 ? 是關于 f 的所有增廣鏈中的費用最小的增廣鏈，那么沿增廣鏈 我們將 叫做這條增廣鏈的費用 。 ? ?? ??? ?jiji bbμ 調(diào)整可行流 f，得到的新可行流 f ` ，也是流量為 v(f’)的所有可行流中的最小費用流。依次類推，當 f ` 是最大流時，就是所要求的最小費用最大流。 顯然，零流 f ={0}是流量為 0的最小費用流。一般地，尋求最小費用流，總可以從零流 f ={0}開始。下面的問題是：如果已知 f 是流量為 v(f)的最小費用流，那么就要去尋找關于 f 的最小費用增廣鏈。 對此，重新構造一個賦權有向圖 M( f )，其頂點是原網(wǎng)絡 D的頂點，而將 D中的每一條弧 ( vi , vj )變成兩個相反方向的弧 （ vi , vj）和 (vj , vi)，并且定義 M ( f )中弧的權 wij為： ????????jijijijijiji cfcfbw當當,?????????00jijijiji ffbw當當,并且將權為 +∞ 的弧從 M( f ) 中略去 。 這樣 ， 在網(wǎng)絡 D中尋找關于 f 的最小費用增廣鏈就等于價于在 M(f )中尋求從 vs 到 vt 的最短路 。 算法開始， 取零流 f (0) ={0}.一般地，如果在第 K1步得到最小費用流 f (K1),則構造圖M(f (k1))。 在圖 M(f (k1))中，尋求從 vs到 vt的最短路。如果存在最短路，則 f (k1)就是最小費用最大流。如果存在最短路，則在原網(wǎng)絡D中得到相對應（一一對應）的增廣鏈 μ0 在增廣鏈 μ上對 f (k–1)進行調(diào)整，取調(diào)整量 ?????? ?? ????)(m i n,)(m i nm i n )()( 11 kjikjiji ffc???令： ????????????其它不變上，在上，在????)()()( 11kjikjikfffji得到一個新的可行流 f(k)，在對 f(k)重復以上的步驟，直到 D中找不到相對應的增廣鏈時為止。 例 求圖 824 所示網(wǎng)絡中的最小費用最大流 ， 弧旁的權是 （ bij , cij） . (bij ,cij) (1, 8) (3,10) (2, 4) (6, 2) (1,7) (4, 10) (2, 5) v1 v2 vs v3 vt 圖 824 解： （ 1） 取初始可行流為零流 f (0)={0},構造賦權有向圖 M(f(0)),求出從 vs到 vt的最短路(vs ,v2 ,v1 ,vt),如圖 中雙箭頭所示 。 (1) (3) (2) (6) (1) (4) (2) M(f(0)) v1 vs v2 v3 vt 圖 a （ 2） 在原網(wǎng)絡 D中 ， 與這條最短路相對應的增廣鏈為 μ=（ vs ,v2 ,v1 ,vt ） 。 （ 3） 在 μ 上對 f (0)={0}進行調(diào)整 ， 取 θ=5，得到新可行流 f (1)， 如圖 。 按照以上的算法 ， 依次類推 ， 可以得到 f (1)， f (2)， f( 3)，f (4)， 流量分別為 5， 7， 10， 11， 并且分別構造相對應的賦權有向圖 M( f(1 )) , M(f (2) ) , M(f(3)),M(f(4))。 由于在 M(f(4))中已經(jīng)不存在從vs到 vt的最短路 ， 因此 ， 可行流 f (4)， v(f(1))=11是最小費用最大流 。 (8,5) (10,0) (4,0) (2,0) (7,5) (10,0) (5,5) 圖 8 . 25b f(1),v( f (1))=5 v1 vs v2 v2 vt M(f (1)) 圖 8 . 25 c v1 (2) ( 1) v3 (1) (3) (6) (1) (4) (2) (1) vs v2 vt (2,0) (5,5) (8,5) (4,0) (7,7) (10,2) (10,0) 圖 8 . 25 d f (2),v( f (2))=7 v1 vs v2 v3 vt M( f (2) ) 圖 8 . 25 e (1) (3) (2) (6) (1) (4) (2) (1) (4) v1 vs v3 vt v2 (8,8) (10,3) (4,3) (2,0) (7,7) (10,2) (5,5) 圖 8 . 25 f f (3),v( f (3))=10 v1 vs v2 v3 vt (1) (3) (2) (6) (1) (4) (2) (4) M( f (3) ) 圖 8 . 25 g (2) (3) v1 vs v2 v3 vt (8,8) (10,4) (4,4) (2,0) (7,7) (10,3) (5,4) 圖 8 . 25 h f (4),v ( f(4)) =11 v1 vs v2 v3 vt (1) (3) (2) (6) (1) (4) (2) (4) M( f (4) ) 圖 8 . 25 i (2) (3) v1 vs v2 v3 vt 167。 網(wǎng)絡計劃 大型項目的開發(fā)涉及很復雜的項目協(xié)調(diào)和管理問題，為使項目管理人員對項目進度有全面的了解，進行有效的控制，必須使用科學的管理方法 . 網(wǎng)絡計劃法是使用最廣泛的方法之一，關鍵路徑法 (CPM)和項目評審技術 (PERT)是兩種使用最廣泛的網(wǎng)絡計劃技術。 網(wǎng)絡計劃方法的優(yōu)點使它適用于生產(chǎn)技術復雜，工作項目繁多，且緊密聯(lián)系的一些跨部門的工作計劃，如： 新產(chǎn)品研制開發(fā) 大型工程項目建設 生產(chǎn)技術準備 復雜設備的大修計劃 網(wǎng)絡計劃方法的基本原理 將工程項目分解為相對獨立的活動，根據(jù)各活動先后順序、相互關系以及完成所需時間做出反映項目全貌的網(wǎng)絡圖；從項目完成全過程著眼，找出影響項目進度的關鍵活動和關鍵路線，通過對資源的優(yōu)化調(diào)度，實現(xiàn)對項目實施的有效控制和管理。 網(wǎng)絡計劃方法的主要功能 1 用網(wǎng)絡圖描述一個實際項目的管理問題 (畫網(wǎng)絡圖 ) 。 2 計算項目的最早、最晚完成和開工時間 (網(wǎng)絡計算 ) 。 3 尋找關鍵活動和關鍵路徑 (網(wǎng)絡分析 )。 4 根據(jù)以上分析對網(wǎng)絡進行優(yōu)化。 8 . 6 . 1 網(wǎng)絡計劃與網(wǎng)絡圖 復雜工程項目可被分解為一系列小的事件或活動，各種事件和活動之間的邏輯順序可以表述為一個由一系列弧和節(jié)點組成的網(wǎng)絡圖； 網(wǎng)絡圖中的有向弧代表各種活動 (或工作 ), 活動完成需要的時間寫在弧上； 節(jié)點表示事件 (或事項 ), 表示活動的開始與結束 , 每個節(jié)點有唯一節(jié)點號； 位于弧的起點和終點的節(jié)點表示活動或事件的開始和結束 , 每個活動有一 個起點和一個終點 : 1 2 5 a 圓圈和里面的數(shù)字代表各事項，寫在箭桿中間的數(shù)字 5 表示完成本工作所需時間，即工作 a ( 1 , 2 )，事項： ( 1 , 2 )。 圖 8 . 26 整個網(wǎng)絡的方向按慣例從左到右地反映活動的邏輯順序 , 并有唯一的起點和終點。 虛工作用箭線“ ” 表示。它表示工時為零，不消耗任何資源的虛構工作。其作用只是正確表示工作的前行后繼關系。 畫網(wǎng)絡圖有以下四個階段 : 一、列出所有活動 一個完整的項目必須被分解為一系列獨立 活動（稱為工序） , 分解程度取決于項目計劃的需要以及相應的管理職能。 二、確定每個活動的緊前工序 項目執(zhí)行的連續(xù)性確定了項目各項活動的前后順序 , 為了從邏輯上搞清楚活動之間的順序關系 , 需要確定每項活動可以開始之前必 須完成的活動 緊前工序。 注意 ： 區(qū)分習慣上發(fā)生的順序和它們在邏輯上應該發(fā)生的順序 , 例如 , 寄出一個發(fā)票的一般 方法是 : (1) 檢查發(fā)票 (2) 將發(fā)票放入信封 (3) 封上信封 (4) 在信封上寫地址 這不是唯一正確方法 , 網(wǎng)絡圖應能反映所有可能性 , 而不僅僅是傳統(tǒng)方法。 三、畫網(wǎng)絡圖 畫網(wǎng)絡圖應注意以下規(guī)則 : 網(wǎng)絡只能有一個總起點和一個總終點 。 1 2 3 4 5 6 7 8 9 圖 8. 27 中，有兩個總起點事項①， ⑦ ；三個總終點事項④，⑥，⑨，不符合規(guī)則。 圖 8 . 27 網(wǎng)絡圖為有向圖 , 且不能有回路； 1 2 3 4 5 6 7 圖 8. 28 中 ③ ?⑤ ? ⑥ ? ③是回路，不符合規(guī)則 圖 8 . 28 兩個節(jié)點之間不能有兩條或兩條以上的弧（兩個及兩個以上的工作） 。 1 2 a b 圖 8 . 29 不符合規(guī)則。 應正確表示活動之間的前行后繼關系 。 如 4 道工作 a , b , c , d 的關系為： c 必須在 a , b 均完成后才能開工，而 d 只要在 b 完工后 圖 8 . 29 即可開工，如畫成下圖是錯誤的，因本來與 a 工作的工作 d 被錯誤地表為必須在 a 完工后才能開工。 a 1 2 3 4 5 b c d 虛擬活動的運用 網(wǎng)絡有時需要包括由虛線表示的 ‘虛擬’ 活 圖 8 . 30 動。首先 , 它可以避免兩個活動有相同的起點和終點 。 其次 , 使用虛擬活動可以幫助表示一些特殊的邏輯依賴關系。 如前面不符合規(guī)則的 圖 8 . 27 ，圖 8 . 29，圖 8 . 30，用添加虛工作的方法改圖為 圖 8 . 31，圖 8 . 32，圖 8 . 33就是正確的了。 1 2 3 a b 圖 8 . 32 1 3 2 4