【正文】 1 2 3 a b 圖 8 . 32 1 3 2 4 。 其次 , 使用虛擬活動可以幫助表示一些特殊的邏輯依賴關(guān)系。 a 1 2 3 4 5 b c d 虛擬活動的運用 網(wǎng)絡(luò)有時需要包括由虛線表示的 ‘虛擬’ 活 圖 8 . 30 動。 應(yīng)正確表示活動之間的前行后繼關(guān)系 。 圖 8 . 27 網(wǎng)絡(luò)圖為有向圖 , 且不能有回路； 1 2 3 4 5 6 7 圖 8. 28 中 ③ ?⑤ ? ⑥ ? ③是回路，不符合規(guī)則 圖 8 . 28 兩個節(jié)點之間不能有兩條或兩條以上的?。▋蓚€及兩個以上的工作） 。 三、畫網(wǎng)絡(luò)圖 畫網(wǎng)絡(luò)圖應(yīng)注意以下規(guī)則 : 網(wǎng)絡(luò)只能有一個總起點和一個總終點 。 二、確定每個活動的緊前工序 項目執(zhí)行的連續(xù)性確定了項目各項活動的前后順序 , 為了從邏輯上搞清楚活動之間的順序關(guān)系 , 需要確定每項活動可以開始之前必 須完成的活動 緊前工序。其作用只是正確表示工作的前行后繼關(guān)系。 虛工作用箭線“ ” 表示。 8 . 6 . 1 網(wǎng)絡(luò)計劃與網(wǎng)絡(luò)圖 復(fù)雜工程項目可被分解為一系列小的事件或活動，各種事件和活動之間的邏輯順序可以表述為一個由一系列弧和節(jié)點組成的網(wǎng)絡(luò)圖； 網(wǎng)絡(luò)圖中的有向弧代表各種活動 (或工作 ), 活動完成需要的時間寫在弧上； 節(jié)點表示事件 (或事項 ), 表示活動的開始與結(jié)束 , 每個節(jié)點有唯一節(jié)點號； 位于弧的起點和終點的節(jié)點表示活動或事件的開始和結(jié)束 , 每個活動有一 個起點和一個終點 : 1 2 5 a 圓圈和里面的數(shù)字代表各事項，寫在箭桿中間的數(shù)字 5 表示完成本工作所需時間，即工作 a ( 1 , 2 )，事項： ( 1 , 2 )。 3 尋找關(guān)鍵活動和關(guān)鍵路徑 (網(wǎng)絡(luò)分析 )。 網(wǎng)絡(luò)計劃方法的主要功能 1 用網(wǎng)絡(luò)圖描述一個實際項目的管理問題 (畫網(wǎng)絡(luò)圖 ) 。 網(wǎng)絡(luò)計劃 大型項目的開發(fā)涉及很復(fù)雜的項目協(xié)調(diào)和管理問題，為使項目管理人員對項目進度有全面的了解，進行有效的控制，必須使用科學(xué)的管理方法 . 網(wǎng)絡(luò)計劃法是使用最廣泛的方法之一，關(guān)鍵路徑法 (CPM)和項目評審技術(shù) (PERT)是兩種使用最廣泛的網(wǎng)絡(luò)計劃技術(shù)。 由于在 M(f(4))中已經(jīng)不存在從vs到 vt的最短路 ， 因此 ， 可行流 f (4)， v(f(1))=11是最小費用最大流 。 （ 3） 在 μ 上對 f (0)={0}進行調(diào)整 ， 取 θ=5，得到新可行流 f (1)， 如圖 。 例 求圖 824 所示網(wǎng)絡(luò)中的最小費用最大流 ， 弧旁的權(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),如圖 中雙箭頭所示 。如果存在最短路，則 f (k1)就是最小費用最大流。 算法開始， 取零流 f (0) ={0}.一般地，如果在第 K1步得到最小費用流 f (K1),則構(gòu)造圖M(f (k1))。 對此，重新構(gòu)造一個賦權(quán)有向圖 M( f )，其頂點是原網(wǎng)絡(luò) D的頂點，而將 D中的每一條弧 ( vi , vj )變成兩個相反方向的弧 （ 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 ) 中略去 。一般地，尋求最小費用流，總可以從零流 f ={0}開始。依次類推，當(dāng) f ` 是最大流時，就是所要求的最小費用最大流。 ? ?? Avv jijiji fbfb ),()(=v(f )+1，而此時總費用 b(f ` )比 b(f)增加了 ? ?? ??? ????????????? ?? ?jijijijijijijijibbffbffbfbfb )()()()(結(jié)論： 如果可行流 f 在流量為 v(f )的所有可行流中的費用最小，并且 ? 是關(guān)于 f 的所有增廣鏈中的費用最小的增廣鏈，那么沿增廣鏈 我們將 叫做這條增廣鏈的費用 。最小費用最大流問題就是要解決這一類問題 。 在實際的網(wǎng)絡(luò)系統(tǒng)中 ， 當(dāng)涉及到有關(guān)流的問題的時候 ， 我們往往不僅僅考慮的是流量 ， 還經(jīng)常要考慮費用的問題 。 最大流量 f * = 14 。 看 v3,在弧 （ v3 ,v2） 上 ， f32=c32,弧（ v3 ,v5） 上 ， f35= c35,均不符合條件 。 這時，網(wǎng)絡(luò)中的可行流 f * 即是最大流，最大流的流量 v(f*)= fs1+fs2=，也找出 D的最小截集（ V1， ），其中 V1是標(biāo)號的集合， 是未標(biāo)號的集合。 看 v1,在弧 （ v1 ,v3） 上 ， f13=c13,?。?v2 ,v1） 上 ， f21=0,均不符合條件 。 不 難 看出 ,μ+={(vs ,v1),(v3 ,vt)},μ– ={(v2 ,v1) , (v3 ,v2)}, 取 θ=1， 在 μ 上調(diào)整 f ， 得到 f * = fs1 + θ=1+1=2 在 μ +上 f3t + θ=1+1=2 在 μ +上 f *= f21 –θ=1 – 1=0 在 μ 上 f32 – θ = 1 – 1=0 在 μ 上 其它的不變 vs v1 v2 v3 v4 vt (3 , 3) (5 , 1) (4 , 3) (1 , 1) (1 , 1) (2 , 2) (3 , 0) (5 , 3) (2 , 1) 圖 8 —22 例 8 — 8網(wǎng)絡(luò)圖 (5 , 2) (1 , 0) (1 , 0) (2 , 2) (cij , fij) 調(diào)整后的可行流 f *， 如圖 ， 再對這個可行流從新進行標(biāo)號過程 ， 尋找增廣鏈 。 （ 5） 在 v3 ,v4中任意選一個 ， 比如 v3 ,在?。?v3 , vt） 上 ， f3t =1 c3t =2,故給 vt標(biāo)號 (v3 ,l(vt)),其中 l(vt)=min[l(v3),(c3tf3t)]=min[1,1]= vt被標(biāo)上號 ， 根據(jù)標(biāo)號法 ， 轉(zhuǎn)入調(diào)整過程 。 （ 1） 首先給 vs標(biāo)號 （ 0， +∞） （ 2） 看 vs : 在弧 (vs ,v2)上 ,fs2=cs3=3 , 不 具備標(biāo)號條件 。 vs v1 v2 v3 v4 vt (3 , 3) (5 , 1) (4 , 3) (1 , 1) (1 , 1) (2 , 2) (3 , 0) (5 , 3) (2 , 1) 圖 8 —20 例 8 — 8網(wǎng)絡(luò)圖 解： 用標(biāo)號法 。 ?????????????????),(,),(,jijijijijivvfvvff其它不變 再去掉所有的標(biāo)號，對新的可行流 f ’={f ’ij},重新進行標(biāo)號過程，直到找到網(wǎng)絡(luò) D的最大流為止。 這時 ， 所找出的弧就成為網(wǎng)絡(luò) D 的一條增廣鏈 μ 。 再看 vk的第一個標(biāo)號 ， 若是 vi ， 則弧 (vi ,vk)都在 μ上 。 首先按照 vt 和其它的點的第一個標(biāo)號 ，反向追蹤 ， 找出增廣鏈 μ 。 重復(fù)以上步驟 ， 如果所有的標(biāo)號都已經(jīng)檢查過 ， 而標(biāo)號過程無法進行下去 ， 則標(biāo)號法結(jié)束 。 （ 2） 如果在弧 （ vj ,vi） 上 ， fji 0,那么給vj標(biāo)號 （ vi , l(vj)） .其中 l (vj)=min[ l(vi), fji ].這時 ， vj 成為標(biāo)號未檢查點 。這時 ， vs 是標(biāo)號未檢查的點 ， 其它都是未標(biāo)號點 。 第二個標(biāo)號是為了用來確定增廣鏈上的調(diào)整量 θ。 每個標(biāo)號點的標(biāo)號包含兩部分：第一個標(biāo)號表示這個標(biāo)號是從那一點得到的 。 1． 標(biāo)號過程 在標(biāo)號過程中 ， 網(wǎng)絡(luò)中的點或者是標(biāo)號點 （ 分為已檢查和未檢查兩種 ） 。 如果標(biāo)號過程無法進行下去 ， 并且 vt未被標(biāo)號 ， 則表示不存在關(guān)于 f 的增廣鏈 。 下面用給頂點標(biāo)號的方法來定義 V1*.在標(biāo)號過程中 ， 有標(biāo)號的頂點是 V1*中的點 ，沒有標(biāo)號的點不是 V1*中的點 。如有增廣鏈，那么可以按照定理 ，不斷改進和增大可行流 f 的流量，最終可以得到網(wǎng)絡(luò)中的一個最大流。亦即，如果網(wǎng)絡(luò) D中有一個可行流 f，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流 f 的增廣鏈 。 定理 在一個網(wǎng)絡(luò) D中，最大流的流量等于分離 vs 和 vt 的最小截集的截量。 1V1V1V 定義 設(shè)一個截集 （ V1 , ） .將階截集（ V1 , ） 中所有的弧的容量的和叫做截集的截量 ， 記做 s( V1 , ) , 亦即 1V1V1V? ? ???),(),(,1111VVvvjijicVVs下面的事實是顯然的：一個網(wǎng)絡(luò) D中，任何一個可行流 f 的流量 v (f ) 都小于或等于這個網(wǎng)絡(luò)中任何一個截集 (V1 , )的截量。 定義 設(shè)一個網(wǎng)絡(luò) D=（ V， A， C） 。 設(shè)圖 D=(V， A， C)， 點集 S， T?V,S∩T=ф。 2． 在弧 （ vi,vj） ∈ μ–上 ， 有 0fij?cij,即 μ–中的每一條弧是非零流弧 。 二類是弧的方向與鏈的方向相反 ， 叫做后向弧 ， 后向弧的集合記做 μ–。 設(shè) μ是網(wǎng)絡(luò) D中連接發(fā)點 νs和收點 vt的一條鏈 。我們把 D中 fij=cij的弧叫做飽和弧， fijcij的弧叫 其中發(fā)點的總流量 （ 或收點的總流量 ） v ( f ) 叫做這個可行流的流量 。 網(wǎng)絡(luò)系統(tǒng)中最大流問題就是在給定的網(wǎng)絡(luò)上尋求一個可行流 f,其流量 v(f)達到最大值。 (3)每一個弧上的流量 不能超過它的最大通過能力（即容量） 于是有： v3 v2 v1 v4 vs （ 2） （ 3） （ 2） （ 5） （ 3） （ 3） （ 6） （ 1） （ 1） （ 2） fij vt 圖 定義 網(wǎng)絡(luò)上的一個流 f 叫做可行流 ，如果 f 滿足以下條件 （ 1） 容量條件： 對于每一個弧 （ vi ,vj）∈ A,有 0 ? fij ? cij . （ 2） 平衡條件： ? ?? ???Avv Avvsjjsjs sjfvff),( ),()(對于發(fā)點 vs,有 對于收點 vt,有 ? ?? ????Avv Avvtjjtjt tjfvff),( ),()(對于中間點 ， 有 ? ?? ???Avv Avvijjiji ijff),( ),(0 任意一個網(wǎng)絡(luò)上的可行流總是存在的。 對于實際的網(wǎng)絡(luò)系統(tǒng)上的流 ， 有幾個顯著的特點： (1)發(fā)點的總流出量和收點的總流入量必相等 。 每一個弧旁邊的權(quán)就是對應(yīng)的容量 （ 最大通過能力 ） cij . 圖 （運輸方案），每一個弧上的流量 fij就是運輸量。 網(wǎng)絡(luò) D上的流 ， 是指定義在弧集合 A上的一個函數(shù) f={f(vi ,vj)}={fjj} f(vi ,vj)=fij叫做弧 (vi ,vj)上的流量 。 對于 D中的每一個弧 （ vi ,vj）∈ A,都有一個 權(quán) 叫做弧的 容量 。 ?問題描述 連通網(wǎng)絡(luò) G(V, A) 有 m 個節(jié)點 , n條弧 , 弧 eij 上的流量上界為 cij, 求從起始節(jié)點 vs 到終點 vt 的最大流量。 而網(wǎng)絡(luò)系統(tǒng)流最大流問題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問題 ， 它對于解決生產(chǎn)實際問題起著十分重要的作用 。 最小費用流問題 一 引言