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