圖與網(wǎng)絡分析

5

圖與網(wǎng)絡分析教學目的與要求通過對本章的學習，使學生掌握圖的基本概念；掌握用矩陣法求圖中任意兩點間的最短路線；掌握可行流、可行流的流量、最大流、割、割的容量、最小割、增廣鏈的概念；能熟練地用標號法求有向圖與無向圖中從一個點到另一個點的最短路徑；熟練地用Ford-Fulkerson標號法求最大流；熟練繪制簡單的網(wǎng)絡圖，掌握工序時間參數(shù)的確定方法及各種時間參數(shù)的計算；掌握網(wǎng)絡圖的優(yōu)化與調整，會縮短總工期，實現(xiàn)時間、費用、資源的優(yōu)化配置；學會運用圖論的觀點去分析解決簡單的實際問題。圖論是運籌學的一個重要分支，它已經廣泛地應用于物理學控制論、信息論、工程技術、交通運輸、經濟管理、電子計算機等各個領域。對于科學研究，市場和社會生活中的許多問題，可以用圖論的理論和方法來加以解決。例如，各種通信線路的架設、輸油管道的鋪設、鐵路或者公路交通網(wǎng)絡的合理布局等問題，都可以應用圖論的方法，簡便、快捷地加以解決。隨著科學技術的進步，特別是電子計算機技術的發(fā)展，圖論的理論獲得了更進一步的發(fā)展，應用更加廣泛。如果將復雜的工程系統(tǒng)和管理問題用圖的理論加以描述，可以解決許多工程項目和管理決策的最優(yōu)問題。因此，圖論越來越受到工程技術人員和經營管理人員的重視。5

圖與網(wǎng)絡分析5.1圖論問題的提出5.2圖論的基本概念5.3最短路徑問題5.4網(wǎng)絡最大流問題5.5網(wǎng)絡計劃◎知識歸納◎習題與思考題5.1圖論問題的提出5.1.1圖論概述圖論始于1736年，源于對著名的“哥尼斯堡七橋問題”的研究。歐拉解決問題的基本步驟是這樣的：既然島與河岸無非是橋梁的連接點，兩岸陸地也是橋通往的地點，那就不妨用一個頂點表示一個陸地的區(qū)域，用連接相應頂點的線段表示每一座橋，這樣的處理，在不改變問題實質的情況下，把現(xiàn)實生活中的人步行過橋問題抽象成圖5.1(b)。于是哥尼斯堡七橋問題的解答就等價于能否一筆畫出上述圖5.1(b)的問題了。接著他考察了這個圖的結構特征，他的結論是：在任意頂點處能實現(xiàn)一筆畫的結果總是使與該頂點連接的線段一進一出，因此通過該頂點的線段數(shù)總是偶數(shù)。對整個圖來說，至多有兩個頂點(相當于人步行的起點和終點)有可能通過奇數(shù)條線段，觀察圖5.1(b)，可立即發(fā)現(xiàn)它的四個頂點均與奇數(shù)條線段連接，因此，它不可能被一筆畫出從而也就證明了不可能存在通過哥尼斯堡七橋每座橋一次且僅一次再回到原地的走法。歐拉不僅解決了七橋問題，他在解決七橋問題時中所運用的抽象分析方法(把具體問題抽象為結構簡單的圖形)和所采用的論證方法，經過不斷發(fā)展，形成了以僅包括頂點和邊的圖為工具去解決許多領域中實際問題的新的數(shù)學思想方法?？瓷先ニ坪跻饬x不大的七橋問題，導致了一個新的數(shù)學分支——圖論的誕生。圖5.1哥尼斯堡七橋問題

1847年，克希霍夫用圖論分析電路網(wǎng)絡，這是圖論最早應用于工程科學，以后隨著科學的發(fā)展，圖論在解決運籌學、網(wǎng)絡理論、信息論、控制論、博弈論以及計算機科學等各個領域的問題時，顯示出越來越大的作用。圖論在各種物理學科、工程領域、社會科學和經濟問題中的廣泛應用，使它受到數(shù)學和工程界的特別重視。對于這樣一門應用廣泛的科學，其包含的內容當然是浩瀚如海，我們這里只準備介紹一些基本的概念和定理，以及一些典型的應用實例。5.1.2圖論在現(xiàn)代物流中的運用在現(xiàn)代物流管理實踐中，我們經常遇到如何制定管理計劃或設備購置計劃，使收益最大或費用最小的問題；在現(xiàn)有交通網(wǎng)絡中，如何使調動的物資數(shù)量最多且費用最小等。這類問題均可借助于圖論知識得以解決。（1）最短路徑問題假定圖5.2是一個由城市v1到城市v6的交通圖，線旁的數(shù)字表示各條路線的距離，那么最短路徑問題就是尋找一條從城市v1到城市v6的最短路徑。如果數(shù)字不是代表距離，而是時間，那么所求的最短路徑是指總時間最短；如果數(shù)字代表費用，那么最短路徑問題就是求一系列活動的總費用最少，因此在這里最短路的概念是廣義的。最短路徑問題可以用線性規(guī)劃的方法求解，但算法很不經濟。圖論給出了多種較為簡便的求解最短路徑問題的方法。如求從某一點至其他各點之間最短距離的狄克斯屈算法；求網(wǎng)絡圖上任意兩點間最短距離的矩陣算法。圖5.2（2）最大流問題設有一批物資要從v1發(fā)運到v6，圖5.3是其交通圖，每條線代表連接兩地的路線，線旁的數(shù)字表示該線的容量，即該路線單位時間內的最大通過能力，顯然每條線上單位時間內通過的貨物流量不能超過該線的最大通過能力。問應如何選擇路徑，才能使得從v1到v6的總運量最大？這是一個與提高效益有關的問題，它不只適用于交通輸送問題，在許多實際的網(wǎng)絡系統(tǒng)中都存在著流量和最大流問題，如金融系統(tǒng)中有現(xiàn)金流，通信系統(tǒng)中有信息流等等。最大流問題是特殊的線性規(guī)劃問題，自然可用單純形法求解，但利用圖論的方法更加簡便。圖5.3（3）資源優(yōu)化問題利用網(wǎng)絡分析的方法，我們可以在現(xiàn)代物流項目管理中縱觀計劃任務的全局，把握各項活動之間的相互關系，抓住問題的關鍵，找出最佳的解決方案。特別在資源改變的情況下，可以做到及時調整與改善、重新統(tǒng)籌安排，以保證在整個過程中自始至終能夠最合理地使用人力、財力和物力，保證多快好省地完成任務。網(wǎng)絡分析中的資源優(yōu)化問題主要體現(xiàn)在兩個方面：一是人力、設備和動力的合理安排，二是網(wǎng)絡的時間與費用的優(yōu)化。返回5.2圖論的基本概念圖論的研究對象是由頂點和頂點之間的邊構成的圖形，這是一種非常具體、非常容易了解的數(shù)學模型。所以，圖論所提供的工具將有助于人們領會如何選用或建立數(shù)學模型，這對幫助管理人員作出正確決策，以達到提高經營管理水平和經濟效益的目的是有好處的。另外，與傳統(tǒng)數(shù)學方法的抽象深奧相比，圖論的理論和方法更具有鮮明、直觀和形象化的特點。對于從事經濟工作、管理工作的讀者來說，圖論也許是一門比較平易近人的數(shù)學學問，它不僅有用，而且容易入門和掌握。5.2.1節(jié)點，邊，圖，網(wǎng)絡圖論中所研究的圖，是指反映或描述自然界或人類社會中，大量的事物及事物之間關系的圖形?！纠?.1】某地區(qū)有五個鎮(zhèn)A、B、C、D、E，它們之間有公路相通的情況，如圖5.4(a)所示。圖5.4在圖論中，我們只關心兩點間是否有聯(lián)系，至于公路的大小、等級、狀況均無關緊要，亦不需考慮線段（邊）的長度，點的位置帶有隨意性，它們并不按比例尺畫，如五個鎮(zhèn)之間的連接圖也可畫成如圖5.4(b)所示。（1）節(jié)點圖中線的交點稱為節(jié)點（頂點），它的集合用V＝{vi}表示，通常表示有形或無形的事物或實體。（2）邊節(jié)點間的連線稱為邊，它的集合用E＝{eij}表示（也可直接用ei表示），邊通常表示事物與事物（點與點）之間的聯(lián)系或特定的關系。（3）圖圖是由點和線（連線可帶箭頭，也可不帶，前者叫弧，后者叫邊）組成的圖形。一般用G＝（V，E）表示，V是圖G節(jié)點的集合，E是圖G邊的集合。（4）網(wǎng)絡一個圖連同定義在其邊集上的實函數(shù)一起稱為一個網(wǎng)絡。定義在邊集上的實函數(shù)稱為邊的權數(shù)。5.2.2無向圖與有向圖（1）無向圖如果一個圖中所有的邊都沒有方向，則稱其為無向圖，記作G＝（V，E）。連接點的邊記作［vi,vj］，或者［vj,vi］。如圖5.5，該圖就是無向圖。（2）有向圖如果一個圖中所有的邊都是有方向的，那么稱它為有向圖，如圖5.6。有向圖的邊又稱為弧，記作D＝（V，A）。其中V表示有向圖D的點集合，A表示有向圖D的弧集合。一條從vi指向vj方向的弧，記作（vi,vj）。（3）混合圖若某一圖中，有些邊有方向，有些邊沒有方向，則稱該圖為混合圖，如圖5.7所示。圖5.6圖5.75.2.3端點，關聯(lián)邊，相鄰，次，鏈（1）端點與關聯(lián)邊如果有e＝{vi，vj}，那么稱（vi，vj）是邊e的端點，并稱e是（vi，vj）的關聯(lián)邊。圖5.8中的e24、e34、e45均是v4的關聯(lián)邊。（2）相鄰如（vi，vj）是邊e的端點，則稱vi與vj相鄰，如圖5.8中的v2與v4，v4與v5等是相鄰，而v2與v5則不是。圖5.8圖5.9（3）環(huán)與多重邊某一邊e的兩個端點相同則稱e為環(huán)，如e22。兩個頂點之間的邊數(shù)≥2時,叫多重邊，如e13、e13′就是二重邊，如圖5.9所示。（4）次一個頂點v具有關聯(lián)邊的總數(shù)稱為該頂點的次，記作d（v）（每個環(huán)視作兩條邊），如圖5.9所示。d（v1）=3，d（v2）=4，d（v5）=1。（5）鏈無向圖G＝（V，E）中，稱兩兩相鄰的點及其相關聯(lián)的邊構成的點邊序列{v1，e1，v2，e2，…，en-1，vn}為從v1到vn的一條鏈，v1、vn分別稱為鏈的始點和終點，鏈長為n。若一條鏈的始點與終點重合，則稱為閉鏈(在無向圖中閉鏈又稱為回路），否則，稱為開鏈。點邊序列中若只有重復的點而無重復的邊，則稱為簡單鏈。點邊序列中若既沒有重復的點也無重復的邊，則稱為初等鏈（也稱為通路）。返回5.3最短路徑問題最短路徑問題是圖論中十分重要的最優(yōu)化問題之一，它作為一個經常被用到的基本工具，可以解決物流實際中的許多問題，比如輸送管道鋪設、運輸線路安排、配送中心選址、設施設備更新等等，也可以用于解決其他的最優(yōu)化問題。最短路徑問題的算法較多，這里主要介紹狄克斯屈標號法和距離矩陣摹乘法及其相關應用。5.3.1狄克斯屈標號法狄克斯屈標號法是狄克斯屈在1959年提出的，適用于所有權數(shù)均為非負（即一切wij≥0,wij表示頂點vi與vj的邊的權數(shù)）的網(wǎng)絡，能夠求出網(wǎng)絡的任一點vs到其他各點的最短路，為目前求這類網(wǎng)絡最短路的最好算法。其基本思路是：若（v1,v2,…,vn-1,vn）是從v1到vn的最短路徑，則（v1,v2,…,vn-1）也必是從v1到vn-1的最短路徑。這個算法實際上也給出了尋求從一個始定點vs到任意一個點vj的最短路。下面來介紹一下狄克斯屈標號法的算法步驟：首先規(guī)定：P（vj）為從始點vs到vj的最短距離，是固定標號；T（vj）為從始點vs到vj的最短距離上界，是臨時標號；P（vs）＝0，這表示從vs到vs的最短距離為0；T（vj）＝＋∞（j=2，3，…,n）。（1）給始點vs以P標號,P（vs）＝0，可用“（）”標出；其余節(jié)點均給T標號，T（vj）＝＋∞（j=2，3，…,n），可不標出。（2）設節(jié)點vi為剛得到P標號的點，考慮點vj，其中（vi，vj）∈E，且vj為T標號。對vj的T標號進行如下修改：T（vj）＝min［T（vj），P（vi）+wij］。（3）比較所有具有T標號的節(jié)點，把最小者改為P標號，即：P（vk）＝min［T（vj）］。當存在兩個以上最小者時，可同時改為P標號。若全部節(jié)點均為P標號，則停止，否則用vk代替vj，返回步驟（2），直到所有點都標上P標號。5.3.2距離矩陣摹乘法在最短路徑問題中，常常要求網(wǎng)絡上任意兩點間的最短距離。這類問題可以多次采用狄克斯屈算法來計算，但比較煩瑣；此外，在求任意點至某點或某點至任意點最短路徑問題中，有很多網(wǎng)絡往往有負權，此時用狄克斯屈標號法求解就會失效。而距離矩陣摹乘法可以適用于一切網(wǎng)絡的最短路徑求解問題，而且可直接求出網(wǎng)絡中任意兩點間的最短路徑。距離矩陣摹乘法是基于這樣的事實：如果節(jié)點vs到結點vj的最短路徑總是沿著某一特定路徑先到達節(jié)點vi，然后再沿邊（vi,vj）到達節(jié)點vj，則這一特定路徑肯定也是節(jié)點vs到節(jié)點vi的最短路徑。其具體做法是：設一個網(wǎng)絡N有n個結點，其中任意兩點vi與vj之間都有一條邊（vi,vj），其權數(shù)wij≥－∞。若vi與vj不相鄰，則虛設一條邊（vi,vj），并令其權數(shù)為wij=∞。如此可以定義一個矩陣：

W＝（wij）n×n則其為網(wǎng)絡N的距離矩陣。任何網(wǎng)絡都有這樣的距離矩陣，據(jù)此可以求出從各點到某點、某點到各點或任意兩點間的最短路徑。下面我們分類說明：（1）求各點至某點的最短路設要尋找各點vi（i＝1,2,…,n）至某點vr的最短路徑。令d(k)ir為走k步到達vr的最短距離，則有d(k)ir=wir（i=1,2,…,n）。再將從vi走k步到達vr的路徑都分為兩段，即先從vi走一步到達vj，其最短距離為wij；再從vj走k-1步到達vr，其最短距離為d(k-1)jr，則有：令則由矩陣W＝（wij）n×n可知，列矩陣dk中的第i個元素d(k)ir，是距離矩陣W的第I行（wi1,wi2,…,win）與列矩陣dk-1的對應元素求和后取小而取得的。以上算法的矩陣運算記為：這被稱為矩陣摹乘法。若出現(xiàn)dk=dk-1，則列矩陣dk中的元素就是各點到vr的最短距離。（2）求某點至各點的最短路徑假設要找某點vr至各點vj（j=1,2,…,n）的最短路徑。令l(k)rj為從vr走k步到達vj的最短距離，則有d(1)rj=wrj（j＝1,2,…,n）。再將從vr走k步到達vj的路徑都分為兩段，即先從vr走k-1步到達vi，其最短距離為l(k-1)ri；再從vi走一步到達vj，其最短距離為wij，則有：令，則由矩陣W=（wij）n×n可知，列矩陣lk中的第j個元素d(k)rj，是列矩陣dk-1的對應元素與距離矩陣W的第j列（w1j,w2j,…,wnj）求和后取小而取得的。以上算法的矩陣運算記為：若出現(xiàn)lk=lk-1，則列矩陣lk中的元素就是點vr到各點的最短距離。（3）求各點至各點的最短路徑首先記矩陣由前面的內容可知：當k=1時，D1=W。

設Dk=Dk-1×Dk-1,k=2,3,…,p，其中此時Dp即給出各點到各點的最短距離。若wij≥0（i,j＝1,2,…,n），則關于p值估計如下：

2p-1-1≤n-2≤2p-1,即p-1≤lg(n-1)/lg2≤p，或出現(xiàn)Dk=Dk-1。5.3.3應用舉例【例5.9】某工廠使用一臺設備，每年年初工廠要作出決定：繼續(xù)使用，還是購買新的。如果繼續(xù)使用舊的，要付維修費；若要購買一套新的，要付購買費。試確定一個5年計劃，使總支出最小。若已知設備在各年的購買費，及不同機器役齡時的殘值與維修費如表5.1所示。項目第1年第2年第3年第4年第5年購買費1112131414機器役齡0~11~22~33~44~5維修費5681118殘值43210表5.1單位：萬元解把這個問題化為最短路徑問題。用點vi表示第i年初購進一臺新設備，虛設一個點v6，表示第5年年底。邊（v1，vj）表示第i年購進的設備一直使用到第j年年初（即第j-1年年底）。邊（vi，vj）上的數(shù)字表示第i年年初購進設備，一直使用到第j年年初所需支付的購買、維修的全部費用（可由表5.1計算得到）。例如：（v1，v4）邊上的28是第一年年初的購買費11加上三年的維修費5、6、8，減去3年役齡機器的殘值2之差；（v2，v4）邊上的20是第二年年初購買費12減去機器殘值3與使用二年維修費5、6之和，見圖5.18。圖5.18這樣設備更新問題就變?yōu)榍髲膙1到v6的最短路徑問題。（1）v1（0）；（2）min｛(k12),k13,k14,k15,k16｝＝12,給v2標號（12），（v1，v2）加粗線；（3）min｛(k13),k14,k15,k16,k23,k24,k25,k26｝

=｛19,…13+12,…｝＝19

給v3標號（19），（v1，v3）加粗線；（4）min{(k14),k15,k16,k24,k25,k26,k34,k35,k36｝

=｛59,…19+30,…12+20,…｝＝28

給v4標號（28），（v1，v4）加粗線；（5）min｛(k15),k16,k25,k26,(k35),k36,k45,k46｝

=｛40,…41,…40,…43,…｝＝40,對應兩條邊給v5標號（40），（v1，v5）加粗線,（v3，v5）加粗線；（6）min｛k16,k26,(k36),k46,k56,｝＝min｛59,53,49,50,55｝=49

給v6標號（49），（v3，v6）加粗線。計算結果：v1→v3→v6為最短路徑，路長為49。返回5.4網(wǎng)絡最大流問題在許多實際的網(wǎng)絡系統(tǒng)中都存在著流量和最大流問題。例如鐵路運輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流，金融系統(tǒng)中的現(xiàn)金流，通信系統(tǒng)中的信息流等等。而網(wǎng)絡系統(tǒng)最大流問題是圖與網(wǎng)絡流理論中十分重要的最優(yōu)化問題，它對于解決生產實際問題起著十分重要的作用。5.4.1網(wǎng)絡最大流的基本概念（1）網(wǎng)絡流網(wǎng)絡：設一個賦權有向圖D=（V，A），在v中指定一個發(fā)點vs和一個收點vt，其他的點叫做中間點。對于D中的每一個弧（vi,vj）∈A，都有一個權cij叫做弧的容量。我們把這樣的圖D叫做一個網(wǎng)絡系統(tǒng)，簡稱網(wǎng)絡，記做D=（V，A，C）。網(wǎng)絡流：指在一定條件下渡過一個網(wǎng)絡的某種流在各邊上的流量的集合。定義在弧集合A上的一個函數(shù)：F＝{f(vi,vj)}＝{fij}，則f(vi,vj)＝fij叫做弧在(vi,vj)上的流量，簡記為fij。如圖5.20所示，(a)圖上數(shù)字為弧容量，(b)圖上括號內數(shù)字為弧流量。圖5.20網(wǎng)絡系統(tǒng)上流的特點：①發(fā)點的總流出量和收點的總流入量必相等；②每一個中間點的流入量與流出量的代數(shù)和等于零；③每一個弧上的流量不能超過它的最大通過能力（即容量）。（2）可行流可行流：是指滿足以下條件的一個網(wǎng)絡流。①容量條件：對于每一個?。╲i,vj）∈A,有0≤fij≤cij。

②平衡條件：對于發(fā)點vs，有對于收點vt，有∑ftj-∑fjt＝-v（f）對于中間點，有∑fij-∑fji＝0

其中發(fā)點的總流量（或收點的總流量）v（f）叫做這個可行流的流量。（3）最大流最大流：是指在一個網(wǎng)絡中，流量最大的可行流?？尚辛髦衒ij＝cij的弧叫做飽和弧，fij＜cij的弧叫做非飽和弧。fij＞0的弧為非零流弧，fij＝0的弧叫做零流弧。如下圖5.21所示，(v4,v3)是飽和弧，其他的弧是非飽和弧，并且都是非零流弧。設μ是網(wǎng)絡D中連接發(fā)點vs和收點vt的一條鏈。定義鏈的方向是從vs到vt，于是鏈μ上的弧被分為兩類：一是弧的方向與鏈的方向相同，叫做前向弧，前向弧的集合記做μ+;二是弧的方向與鏈的方向相反，叫做后向弧，后向弧的集合記做μ-。如圖5.21所示，則在鏈（vs,v1,v2,v3,v4,vt）中，μ+＝{(vs,v1),(v1,v2),(v2,v3),(v4,vt)},μ-＝{(v4,v3)}。圖5.21增廣鏈：f是一個可行流，如果鏈μ滿足以下條件：①在?。╲i,vj）∈μ+上，有0≤fij＜cij,即μ+中的每一條弧都是非飽和弧。②在弧（vi,vj）∈μ-上，有0＜fij≤cij,即μ-中的每一條弧都是非零流弧。則稱μ為從vs到vt的關于f的一條增廣鏈。例如在圖5.21中，鏈μ=（vs,v1,v2,v3,v4,vt）就是一條增廣鏈。5.4.2網(wǎng)絡的截集和截集容量(1）網(wǎng)絡的截集設一個網(wǎng)絡D＝（V，A，C）。如果節(jié)點集V被分為兩個非空集合S、，發(fā)點vs∈S，收點vt∈,那么將弧集(S,)叫做是分離vs和vt的截集。

（2）截集容量

設一個截集(S,)，則截集(S,)中所有弧的容量之和，稱為這個截集的容量，記為C(S,)，亦即C(S,)=∑cij。5.4.3網(wǎng)絡最大流的標號法根據(jù)上面的結論，我們可以得出一個尋求網(wǎng)絡系統(tǒng)最大流的方法：如果網(wǎng)絡D中有一個可行流f，只需判斷網(wǎng)絡是否存在關于可行流f的增廣鏈。如沒有增廣鏈，那么f一定是最大流；如有增廣鏈，那么可以按照上述結論（3），不斷改進和增大可行流f的流量，最終可以得到網(wǎng)絡中的一個最大流。下面我們就一起來了解求解網(wǎng)絡最大流問題的方法：標號法。從網(wǎng)絡中的一個可行流f出發(fā)（如果D中沒有f，可以令f是零流），運用標號法，經過標號過程和調整過程，可以得到網(wǎng)絡中的一個最大流。用給頂點標號的方法來定義V1*。在標號過程中，有標號的頂點是V1*中的點，沒有標號的頂點不是V1*中的點。如果vt有了標號，表示存在一條關于f的增廣鏈。如果標號過程無法進行下去，并且vt未被標號，則表示不存在關于f的增廣鏈。這樣，就得到了網(wǎng)絡中的一個最大流和最小截集。（1）標號過程在標號過程中，網(wǎng)絡中的點或者是標號點（分為已檢查和未檢查兩種），或者是未標號點。每個標號點的標號包含兩部分：第一個標號表示這個標號是從哪一點得到的，以便找出增廣鏈；第二個標號是為了用來確定增廣鏈上的調整量θ。標號過程開始，先給vs標號（0，+∞），這時，vs是標號未檢查的點，其他都是未標號點。一般的，取一個標號未檢查點vi，對一切未標號點vj：

①如果在?。╲i,vj）上，fij<cij，那么給vj標號（vi,l(vj)），其中l(wèi)(vj)＝min［l(vi),cij-fij］。這時，vj成為標號未檢查點。②如果在?。╲i,vj）上，fij>0，那么給vj標號（-vi,l(vj)），其中l(wèi)(vj)＝min［l(vi),cij-fij］。這時，vj成為標號未檢查點。于是vi成為標號已檢查的點。重復以上步驟，如果所有的標號都已經檢查過，而標號過程無法繼續(xù)進行下去，則標號結束。這時的可行流就是最大流。但是，如果vt被標上號，表示得到一條增廣鏈μ，轉入下一步調整過程。（2）調整過程首先按照vt和其他的點的第一個標號，反向追蹤，找出增廣鏈μ。例如，令vt的第一個標號是vk，則弧（vk,vt）在μ上。再看vk的第一個標號，若是vi，則弧（vi,vk）都在μ上。以此類推，直到vs為止。這時，所找出的弧就成為網(wǎng)絡D的一條增廣鏈μ。取調整量θ＝l(vt),即vt的第二個標號。令非增廣矩陣上的各弧流量不變。再去掉所有的標號，對新的可行流f′＝{fij′}重新進行標號過程，直到找到網(wǎng)絡D的最大流為止。

返回5.5網(wǎng)絡計劃用網(wǎng)絡分析的方法編制的計劃稱為網(wǎng)絡計劃。它是幫助人們分析工作活動規(guī)律，揭示任務內在矛盾的科學有效的方法。它提供了一種描述計劃任務中各項活動相互邏輯關系的圖解模型，即網(wǎng)絡圖。利用它和有關的計算方法，可以看清計劃的全局，分析其規(guī)律，以揭示矛盾，抓住關鍵，并用科學的方法調整計劃安排，找出最好的計劃方案。網(wǎng)絡計劃技術的主要內容包括計劃評審技術（PERT）和關鍵路線法（CPM）。兩者的基本原理是相同的，即經過科學分析，將一個工程項目分解成許多作業(yè)（這里所指的作業(yè)，可以是一項設計工作，可以是一個零件的制造過程，也可以是某種活動等），將這些作業(yè)按其相互聯(lián)系及先后順序，繪制出網(wǎng)絡圖。通過估計完成各項作業(yè)所需的作業(yè)時間，確定每項作業(yè)的進度日程，并在網(wǎng)絡圖上找出完成工程項目的關鍵線路，予以重點安排，使工程項目在合理的短時間內完成。通過網(wǎng)絡圖的調整，可以尋求出實現(xiàn)工程項目的最優(yōu)安排方案。但在具體應用時兩者有所不同，前者注重對各項工作安排的評價和審查，更多地應用于研究與開發(fā)項目；后者強調對各項工作要素間關系及關鍵路線的研究，主要應用于以往在類似工程中已取得一定經驗的工程。5.5.1網(wǎng)絡計劃的基本概念（1）網(wǎng)絡圖、工作、事項網(wǎng)絡圖是由箭線、節(jié)點和權組成，用來表示工作流程的有向、有序的網(wǎng)狀圖形。一個網(wǎng)絡圖表示一項計劃任務。節(jié)點表示一個事項。它是一個工作的開始或結束以及工作之間的連接狀態(tài)。箭線表示一項工作。它的出發(fā)節(jié)點叫做工作的起點節(jié)點，箭頭指向的節(jié)點叫做工作的終點節(jié)點。任何工作都可以用其箭線前、后的兩個節(jié)點的編碼來表示，起點節(jié)點編碼在前，終點節(jié)點編碼在后。權表示為完成某個工作所需要的時間或資源等數(shù)據(jù)。網(wǎng)絡圖中的工作（也稱工序）是計劃任務按需要粗細程度劃分而成的、消耗時間或同時也消耗資源的一個子項目或子任務。工作可以是單位工程，也可以是分部工程、分項工程；一個施工過程也可以作為一項工作。在一般情況下，完成一項工作既需要消耗時間，也需要消耗勞動力、原材料、施工機具等資源。但也有一些工作只消耗時間而不消耗資源，如混凝土澆筑后的養(yǎng)護過程和墻面抹灰后的干燥過程等。工序的名稱或內容寫在箭線上方；工序的時間寫在箭線下方。所謂事項是指工程計劃的始點、終點以及其中的兩道或兩道以上工序的交點，又稱為事件或節(jié)點。在時間上，它表示指向某事項的工序全部完成后，該事項后面的工序才能開始，這意味著前后工序的交接。網(wǎng)絡圖中的節(jié)點都必須有編號，其編號嚴禁重復，并應使每一條箭線上箭尾節(jié)點編號小于箭頭節(jié)點編號。事項用圓圈“〇”表示，編號寫在圓圈內。網(wǎng)絡圖有雙代號網(wǎng)絡圖和單代號網(wǎng)絡圖兩種。雙代號網(wǎng)絡圖是應用較為普遍的一種網(wǎng)絡計劃形式。以下我們僅介紹雙代號網(wǎng)絡圖，如圖5.27所示。圖5.27(雙代號)網(wǎng)絡圖（2）工藝關系與組織關系工藝關系和組織關系是工作之間先后順序關系——邏輯關系的組成部分。工藝關系：生產性工作之間由工藝過程決定的、非生產性工作之間由工作程序決定的先后順序關系稱為工藝關系。如圖5.28所示，支模1—扎筋1—混凝土1為工藝關系。組織關系：工作之間由于組織安排需要或資源（勞動力、原材料、施工機具等）調配需要而規(guī)定的先后順序關系稱為組織關系。如圖5.28所示，支模1—支模2，扎筋1—扎筋2等為組織關系。圖5.28某混凝土工程網(wǎng)絡計劃圖（3）緊前工作、緊后工作、平行工作和虛工作緊前工作：在網(wǎng)絡圖中，相對于某工作而言，緊排在該工作之前的工作稱為該工作的緊前工作。如圖5.27中，工作A是工作B與工作C的緊前工作。圖5.28中，扎筋1與支模2都是扎筋2的緊前工作。緊后工作：在網(wǎng)絡圖中，相對于某工作而言，緊排在該工作之后的工作稱為該工作的緊后工作。如圖5.27中，工作B與工作C都是工作A的緊后工作。圖5.28中，扎筋1與支模2都是支模1的緊后工作。平行工作：在網(wǎng)絡圖中，相對于某工作而言，可以與該工作同時進行的工作即為該工作的平行工作。如圖5.27中，工作B與工作C就是平行工作。圖5.28中，扎筋1與支模2就是平行工作。緊前工作、緊后工作及平行工作是工作之間邏輯關系的具體表現(xiàn)，只要能根據(jù)工作之間的工藝關系和組織關系明確其緊前或緊后關系，即可據(jù)此繪出網(wǎng)絡圖。它是正確繪制網(wǎng)絡圖的前提條件。在網(wǎng)絡圖中，有時存在虛箭線，虛箭線不代表實際工作，我們稱之為虛工作。虛工作既不消耗時間，也不消耗資源。虛工作主要用來表示相鄰兩項工作之間的邏輯關系。但有時為了避免兩項同時開始、同時進行的工作具有相同的開始節(jié)點和完成節(jié)點，也需要用虛工作加以區(qū)分。如圖5.27所示，節(jié)點③與節(jié)點⑥之間用了虛工作，表示工作B要先于工作G完成，即工作B完成后，才能開始工作G。圖5.28中，節(jié)點③與節(jié)點④之間用了虛工作。（4）先行工作和后續(xù)工作先行工作：相對于某工作而言，從網(wǎng)絡圖的第一個節(jié)點（起點節(jié)點）開始，順箭頭方向經過一系列箭線與節(jié)點到達該工作為止的各條通路上的所有工作，都稱為該工作的先行工作。如圖5.27中，工作A、工作B、工作C與工作E都是工作G的先行工作。圖5.28中，支模1、扎筋1、支模2都是扎筋2的先行工作；支模1、扎筋1、支模2、扎筋2、混凝土1都是混凝土2的先行工作。后續(xù)工作：相對于某工作而言，從該工作之后開始，順箭頭方向經過一系列箭線與節(jié)點到網(wǎng)絡圖最后一個節(jié)點（終點節(jié)點）的各條通路上的所有工作，都稱為該工作的后續(xù)工作。如圖5.27中，工作C、工作E、工作G都是工作A的先行工作。圖5.28中，扎筋1、混凝土1、混凝土2都是支模1的后續(xù)工作；支模2、扎筋2、混凝土2都是支模1的后續(xù)工作。5.5.2網(wǎng)絡圖繪制（1）網(wǎng)絡圖繪制步驟在一項工程或任務的組織安排中，將任務分解為若干工序，找出工序之間的先后關系及每道工序的估計完成時間，并在此基礎上建立工序明細表；然后根據(jù)這個明細表，用圖論方法，按工序之間的先后關系及完成時間做出一張賦權有向圖；最后對所有事項（節(jié)點）進行順序編號，就建立了該項工程或工作的一張網(wǎng)絡圖。一般的，建立網(wǎng)絡圖分三步。第一步，建立工序明細表；第二步，根據(jù)明細表和畫法規(guī)定作出賦權有向圖；第三步，對圖進行順序編號?！纠?.14】現(xiàn)有某建筑工程的工序表，工序間先后關系及每道工序所需時間如表5.3所示。繪制其網(wǎng)絡圖。工序代號名稱或內容緊前工序時間(天)工序代號名稱或內容緊前工序時間(天)A設計—8E上頂D13B挖地基A20F安裝電器D15C打地基B10G安裝管道D20D主體工程C60H室內裝潢E、F、G30表5.3工序明細表解根據(jù)表5.3作網(wǎng)絡圖。圖5.29某建筑工程網(wǎng)絡計劃圖（2）網(wǎng)絡圖的繪制規(guī)則①正確表達各項工作之間的邏輯關系。如圖5.30所示，A、B、C、D、E五項工作，A、B完成后C開始，B、D完成后E開始。圖5.30圖5.31②網(wǎng)絡圖中，嚴禁出現(xiàn)循環(huán)線路。如圖5.31的畫法是錯誤的。③在網(wǎng)絡圖中不允許出現(xiàn)帶有雙向箭頭或無箭頭的連線。如圖5.32的畫法是錯誤的。圖5.32④在網(wǎng)絡圖中不允許出現(xiàn)沒有箭尾節(jié)點和箭頭節(jié)點的箭線。如圖5.33的畫法是錯誤的。圖5.33⑤網(wǎng)絡圖只能有一個事項表示整個計劃的開始點，同時也只能有一個事項表示整個計劃的完成點（即只能有一個起點和一個終點）。應將沒有緊前工序的（即沒有箭頭進入的）所有節(jié)點合為一個起點，沒有緊后工序的所有節(jié)點合為一個終點，同時不能有缺口。如圖5.34的畫法是錯誤的。圖5.34⑥當網(wǎng)絡圖的起點節(jié)點有多條外向箭線或終點節(jié)點有多條內向箭線時，為使圖形簡潔，可用母線法繪制。如圖5.35。圖5.35⑦在網(wǎng)絡圖中，不允許出現(xiàn)同樣代號的多項工作。如圖5.36的畫法是錯誤的。圖5.36⑧盡量避免箭線交叉。當交叉不可避免時可采用暗橋法、斷線法等方法表示。如圖5.37所示。圖5.37⑨網(wǎng)絡圖節(jié)點編號規(guī)則。原則上說，只要不重復、不漏編，每根箭線的箭頭節(jié)點編號大于箭尾節(jié)點的編號即可。但一般的編號方法是：網(wǎng)絡圖的第一個節(jié)點編號為1，其他節(jié)點編號按自然數(shù)從小到大依次連續(xù)編排，最后一個節(jié)點的編號就是網(wǎng)絡圖節(jié)點的個數(shù)。有時也采取不連續(xù)編號的方法以留出備用節(jié)點號。5.5.3網(wǎng)絡的關鍵線路及時間參數(shù)確定5.5.3.1關鍵線路的概念線路：網(wǎng)絡圖中從起點節(jié)點開始，沿箭頭方向順序通過一系列箭線與節(jié)點，最后到達終點節(jié)點的通路稱為線路。線路既可依次用該線路上的節(jié)點編號來表示，也可依次用該線路上的工作名稱來表示。例如，圖5.27中線路①②③⑤⑦和線路A、B、D、F是同一線路。圖5.28中，線路①②③⑤⑥與線路支模1、扎筋1、混凝土1、混凝土2是同一條線路。圖5.38中線路①②③⑦⑩和線路A、B、C、D、L、M是同一條線路。關鍵線路：在關鍵線路法中，線路上所有工作的持續(xù)時間總和稱為該線路的總持續(xù)時間?？偝掷m(xù)時間最長的線路稱為關鍵線路，關鍵線路的長度就是網(wǎng)絡計劃的總工期。在網(wǎng)絡計劃中，關鍵線路可能不止一條。而且在網(wǎng)絡計劃執(zhí)行過程中，關鍵線路還會發(fā)生轉移。關鍵工作：關鍵線路上的工作稱為關鍵工作。在網(wǎng)絡計劃的實施過程中，關鍵工作的實際進度提前或拖后，均會對總工期產生影響。因此，關鍵工作的實際進度是建設工程進度控制工作中的重點。5.5.3.3時間參數(shù)的計算網(wǎng)絡計劃的時間參數(shù)既可以按工作計算，也可以按節(jié)點計算。（1）按工作計算法所謂按工作計算法，就是以網(wǎng)絡計劃中的工作為對象，直接計算各項工作的時間參數(shù)。這些時間參數(shù)包括：工作的最早開始時間和最早完成時間、工作的最遲開始時間和最遲完成時間、工作的總時差和自由時差。此外，還應計算網(wǎng)絡計劃的計算工期。①計算工作的最早開始時間和最早完成時間工作最早開始時間和最早完成時間的計算應從網(wǎng)絡計劃的起點節(jié)點開始，順著箭線方向依次進行。其計算步驟如下：以網(wǎng)絡計劃起點節(jié)點為開始節(jié)點的工作，當未規(guī)定其最早開始時間時，其最早開始時間為零。工作的最早完成時間可利用公式（5.1）進行計算：

EFi-j=ESi-j＋Di-j(5.1)其他工作的最早開始時間應等于其緊前工作最早完成時間的最大值。網(wǎng)絡計劃的計算工期應等于以網(wǎng)絡計劃終點節(jié)點為完成節(jié)點的工作的最早完成時間的最大值。②確定網(wǎng)絡計劃的計劃工期網(wǎng)絡計劃的計劃工期應按公式（5.2）或公式（5.3）確定。

當已規(guī)定了要求工期時，計劃工期不應超過要求工期，即：Tp≤Tr(5.2)當未規(guī)定要求工期時，可令計劃工期等于計算工期，即：Tp＝Tc(5.3)③計算工作的最遲完成時間和最遲開始時間工作最遲完成時間和最遲開始時間的計算應從網(wǎng)絡計劃的終點節(jié)點開始，逆著箭線方向依次進行。其計算步驟如下：以網(wǎng)絡計劃終點節(jié)點為完成節(jié)點的工作，其最遲完成時間等于網(wǎng)絡計劃的計劃工期Tp。LFi-n=Tp(5.4)工作的最遲開始時間可利用公式（5.5）進行計算：

LSi-j-LFi-j－Di-j

(5.5)其他工作的最遲完成時間應等于其緊后工作最遲開始時間的最小值。④計算工作的總時差工作的總時差等于該工作最遲完成時間與最早完成時間之差，或該工作最遲開始時間與最早開始時間之差。⑤計算工作的自由時差工作自由時差的計算應按以下兩種情況分別考慮：對于有緊后工作的工作，其自由時差等于本工作之緊后工作最早開始時間減本工作最早完成時間所得之差的最小值。對于無緊后工作的工作，也就是以網(wǎng)絡計劃終點節(jié)點為完成節(jié)點的工作，其自由時差等于計劃工期與本工作最早完成時間之差。⑥確定關鍵工作和關鍵線路在網(wǎng)絡計劃中，總時差最小的工作為關鍵工作。特別的，當網(wǎng)絡計劃的計劃工期等于計算工期時，總時差為零的工作就是關鍵工作。找出關鍵工作之后，將這些關鍵工作首尾相連，便構成從起點節(jié)點到終點節(jié)點的通路，位于該通路上各項工作的持續(xù)時間總和最大，這條通路就是關鍵線路。在關鍵線路上可能有虛工作存在。關鍵線路上各項工作的持續(xù)時間總和應等于網(wǎng)絡計劃的計算工期，這一特點也是判別關鍵線路是否正確的準則。在上述計算過程中，是將每項工作的六個時間參數(shù)均標注在圖中，故稱為六時標注法。（2）按節(jié)點計算法所謂按節(jié)點計算法，就是先計算網(wǎng)絡計劃中各個節(jié)點的最早時間和最遲時間，然后再據(jù)此計算各項工作的時間參數(shù)和網(wǎng)絡計劃的計算工期。下面是按節(jié)點計算法計算時間參數(shù)的過程。①計算節(jié)點的最早時間節(jié)點最早時間的計算應從網(wǎng)絡計劃的起點節(jié)點開始，順著箭線方向依次進行。其計算步驟如下：網(wǎng)絡計劃起點節(jié)點，如未規(guī)定最早時間，其值等于零。其他節(jié)點的最早時間應按公式（5.6）進行計算：ETj=max{ETi＋Di-j}(5.6)網(wǎng)絡計劃的計算工期等于網(wǎng)絡計劃終點節(jié)點的最早時間，即：Tc=ETn(5.7)ETn——網(wǎng)絡計劃終點節(jié)點n的最早時間。②確定網(wǎng)絡計劃的計劃工期網(wǎng)絡計劃的計劃工期應按公式（5.2）或公式（5.3）確定。③計算節(jié)點的最遲時間節(jié)點最遲時間的計算應從網(wǎng)絡計劃的終點節(jié)點開始，逆著箭線方向依次進行。其計算步驟如下：網(wǎng)絡計劃終點節(jié)點的最遲時間等于網(wǎng)絡計劃的計劃工期，即:LTn=Tp(5.8)其他節(jié)點的最遲時間應按公式(5.9)進行計算：LTi=min{LTj－Di-j}(5.9)④根據(jù)節(jié)點的最早時間和最遲時間判定工作的六個時間參數(shù)工作的最早開始時間等于該工作開始節(jié)點的最早時間。工作的最早完成時間等于該工作開始節(jié)點的最早時間與其持續(xù)時間之和。工作的最遲完成時間等于該工作完成節(jié)點的最遲時間。即：LFi-j=LTj(5.10)工作的最遲開始時間等于該工作完成節(jié)點的最遲時間與其持續(xù)時間之差，即：LSi-j=LTj－Di-j(5.11)工作的總時差：TFi-j=LFi-j－EFi-j=LTj－(ETi＋Dij)=LTj－ETi－Di-j(5.12)由公式（5.12）可知，工作的總時差等于該工作完成節(jié)點的最遲時間減去該工作開始節(jié)點的最早時間所得差值再減其持續(xù)時間。工作的自由時差等于該工作完成節(jié)點的最早時間減去該工作開始節(jié)點的最早時間所得差值再減其持續(xù)時間。特別需要注意的是，如果本工作與其各緊后工作之間存在虛工作，其中的ETj應為本工作緊后工作開始節(jié)點的最早時間，而不是本工作完成節(jié)點的最早時間。⑤確定關鍵線路和關鍵工作在雙代號網(wǎng)絡計劃中，關鍵線路上的節(jié)點稱為關鍵節(jié)點。關鍵工作兩端的節(jié)點必為關鍵節(jié)點，但兩端為關鍵節(jié)點的工作不一定是關鍵工作。關鍵節(jié)點的最遲時間與最早時間的差值最小。特別的，當網(wǎng)絡計劃的計劃工期等于計算工期時，關鍵節(jié)點的最早時間與最遲時間必然相等。關鍵節(jié)點必然處在關鍵線路上，但由關鍵節(jié)點組成的線路不一定是關鍵線路。當利用關鍵節(jié)點判別關鍵線路和關鍵工作時，還要滿足下列判別式：ETi＋Di-j=ETj或LTi＋Di=j=LTj如果兩個關鍵節(jié)點之間的工作符合上述判別式，則該工作必然為關鍵工作，它應該在關鍵線路上。否則，該工作就不是關鍵工作，關鍵線路也就不會從此處通過。(3）標號法標號法是一種快速尋求網(wǎng)絡計算工期和關鍵線路的方法。它利用節(jié)點計算法的基本原理，對網(wǎng)絡計劃中的每一個節(jié)點進行標號，然后利用標號值確定網(wǎng)絡計劃的計算工期和關鍵線路。下面是標號法的計算過程：網(wǎng)絡計劃起點節(jié)點的標號值為零。其他節(jié)點的標號值應根據(jù)公式（5.13）按節(jié)點編號從小到大的順序逐個進行計算：bj=max{bi＋Di-j}(5.13)當計算出節(jié)點的標號值后，應該用其標號值及其源節(jié)點對該節(jié)點進行雙標號。所謂源節(jié)點，就是用來確定本節(jié)點標號值的節(jié)點。如果源節(jié)點有多個，應將所有源節(jié)點標出。網(wǎng)絡計劃的計算工期就是網(wǎng)絡計劃終點節(jié)點的標號值。關鍵線路應從網(wǎng)絡計劃的終點節(jié)點開始，逆著箭線方向按源節(jié)點確定。5.5.4網(wǎng)絡計劃的優(yōu)化網(wǎng)絡計劃的優(yōu)化是指在一定約束條件下，按既定目標對網(wǎng)絡計劃進行不斷改進，以尋求滿意方案的過程。網(wǎng)絡計劃的優(yōu)化目標應按計劃任務的需要和條件選定，包括工期目標、費用目標和資源目標。根據(jù)優(yōu)化目標的不同，網(wǎng)絡計劃的優(yōu)化可分為工期優(yōu)化、費用優(yōu)化和資源優(yōu)化三種。5.5.4.1工期優(yōu)化所謂工期優(yōu)化，是指網(wǎng)絡計劃的計算工期Tc不滿足要求工期Tr時，通過壓縮關鍵工作的持續(xù)時間以滿足要求工期目標的過程。在優(yōu)化過程中通過壓縮關鍵線路的持續(xù)時間來滿足工期要求，需要注意，不能將關鍵線路壓縮成非關鍵線路，當出現(xiàn)多條關鍵線路時，必須將各條關鍵線路的持續(xù)時間壓縮同一數(shù)值。工期優(yōu)化的步驟與方法為：（1）找出關鍵線路，求出計算工期。（2）按要求工期計算應縮短的時間。（3）根據(jù)下列諸因素選擇應優(yōu)先縮短持續(xù)時間的關鍵工作：①縮短持續(xù)時間對工程質量和施工安全影響不大的工作；②有充足資源儲備的工作；③縮短持續(xù)時間所需增加的費用最少的工作。（4）將應優(yōu)先縮短的工作縮短至最短持續(xù)時間，并找出關鍵線路，若被壓縮的工作變成了非關鍵工作，則應將其持續(xù)時間適當延長至剛好恢復為關鍵工作。（5）重復上述過程直至滿足工期要求或工期無法再縮短為止。當采用上述步驟和方法后，工期仍不能縮短至要求工期則應采用加快施工的技術、組織等措施來調整原施工方案，重新編制進度計劃。如果屬于工期要求不合理，無法滿足時，應重新確定要求的工期目標?！纠?.18】已知某物流工程項目，要求工期Tr=10（周），各工作的邏輯關系如表5.7所示，試對該工程項目進行工期優(yōu)化。工作ABCDEFG緊前工作——AABCC、E時間（周）5343233表5.7解根據(jù)表5.7所示的邏輯關系，得到計劃網(wǎng)絡圖，如圖5.41所示。圖5.41圖中的粗箭頭表示關鍵線路。按照工期要求，對該網(wǎng)絡圖進行工期優(yōu)化，得到優(yōu)化以后的網(wǎng)絡圖，如圖5.42所示。圖5.42即在線路①—②—④—⑥上壓縮2周的工期，線路①—②—⑤—⑥上壓縮1周的工期。5.5.4.2費用優(yōu)化費用優(yōu)化又稱工期成本優(yōu)化，是指尋求工程最低總成本的工期安排，或按要求工期尋求最低成本的計劃安排的過程。在建設工程施工過程中，完成一項工作通?？梢圆捎枚喾N施工方法和組織方法，而不同的施工方法和組織方法，又會有不同的持續(xù)時間和費用。由于一項建設工程往往包含許多工作，所以在安排建設工程進度計劃時，就會出現(xiàn)許多方案。進度方案不同，所對應的總工期和總費用也就不同。為了能從多種方案中找出總成本最低的方案，首先必須分析費用和時間之間的關系。（1）工程費用與工期的關系工程總費用由直接費用和間接費用組成。直接費用由人工費、材料費、機械使用費、其他直接費用及現(xiàn)場經費等組成。施工方案不同，直接費用也就不同；如果施工方案一定，工期不同，直接費用也不同。直接費用會隨著工期的縮短而增加。間接費用包括企業(yè)經營管理的全部費用，它一般會隨著工期的縮短而減少。在考慮工程總費用時，還應考慮工期變化帶來的其他損益，包括效益增量和資金的時間價值等。工程費用與工期的關系如圖5.43所示。圖5.43（2）工作直接費用與持續(xù)時間的關系由于網(wǎng)絡計劃的工期取決于關鍵工作的持續(xù)時間，為了進行工期成本優(yōu)化，必須分析網(wǎng)絡計劃中各項工作的直接費用與持續(xù)時間之間的關系，它是網(wǎng)絡計劃工期成本優(yōu)化的基礎。工作的直接費用與持續(xù)時間之間的關系類似于工程直接費用與工期之間的關系，工作的直接費用隨著持續(xù)時間的縮短而增加，如圖5.43所示。為簡化計算，工作的直接費用與持續(xù)時間之間的關系被近似地認為是一條直線關系。當工作劃分不是很粗略時，其計算結果還是比較精確的。工作的持續(xù)時間每縮短單位時間而增加的直接費用稱為直接費用率。工作的直接費用率越大，說明將該工作的持續(xù)時間縮短一個時間單位，所需增加的直接費用就越多；反之，將該工作的持續(xù)時間縮短一個時間單位，所需增加的直接費用就越少。因此，在壓縮關鍵工作的持續(xù)時間以達到縮短工期的目的時，應將直接費用率最小的關鍵工作作為壓縮對象。當有多條關鍵線路出現(xiàn)而需要同時壓縮多個關鍵工作的持續(xù)時間時，應將它們的直接費用率之和（組合直接費用率）最小者作為壓縮對象。（3）費用優(yōu)化的步驟和方法①計算正常作業(yè)條件下工程網(wǎng)絡計劃的工期、關鍵線路和總直接費用、總間接費用及總費用。②計算各項工作的直接費用率。③在關鍵線路上，選擇直接費用率(或組合直接用費率）最小并且不超過工程間接費率的工作作為被壓縮對象。④將被壓縮對象壓縮至最短，當被壓縮對象為一組工作時，將該組工作壓縮為同一數(shù)值，并找出關鍵線路，如果被壓縮對象變成了非關鍵工作，則需適當延長其持續(xù)時間，使其剛好恢復為關鍵工作為止。⑤重新計算和確定網(wǎng)絡計劃的工期、關鍵線路和總直接費用、總間接費用、總費用。⑥重復上述第③至第⑤步驟，直至找不到直接費用率或組合直接費用率不超過工程間接費用率的壓縮對象為止。此時即求出總費用最低的最優(yōu)工期。⑦繪制出優(yōu)化后的網(wǎng)絡計劃，在每項工作上注明優(yōu)化的持續(xù)時間和相應的直接費用。5.5.4.3資源優(yōu)化資源是指為完成一項計劃任務所需投入的人力、材料、機械設備和資金等。完成一項工程任務所需要的資源量基本上是不變的，不可能通過資源優(yōu)化將其減少。資源優(yōu)化的目的是通過改變工作的開始時間和完成時間，使資源按照時間的分布符合優(yōu)化目標。在通常情況下，網(wǎng)絡計劃的資源優(yōu)化分為兩種，即“資源有限，工期最短”的優(yōu)化和“工期固定，資源均衡”的優(yōu)化。前者是通過調整計劃安排，在滿足資源限制條件下，使工期延長最少的過程；而后者是通過調整計劃安排，在工期保持不變的條件下，使資源需用量盡可能均衡的過程。這里所講的資源優(yōu)化，其前提條件是：①在優(yōu)化過程中，不改變網(wǎng)絡計劃中各項工作之間的邏輯關系；②在優(yōu)化過程中，不改變網(wǎng)絡計劃中各項工作的持續(xù)時間；③網(wǎng)絡計劃中各項工作的資源強度(單位時間所需資源數(shù)量)為常數(shù)，而且是合理的；④除規(guī)定可中斷的工作外，一般不允許中斷工作，應保持其連續(xù)性。通常，將某項工作在單位時間內所需的某種資源數(shù)量稱為資源強度（用rij表示）；將整個計劃在某單位時間內所需某種資源數(shù)量稱為資源需用量（用Qt表示）；將在單位時間內可供使用的某種資源的最大數(shù)量稱為資源限量（用Qa表示）。（1）資源有限——工期最短優(yōu)化在滿足有限資源的條件下，通過調整某些工作的投入作業(yè)的開始時間，使工期不延誤或最少延誤。下面介紹優(yōu)化的步驟與方法。①繪制時標網(wǎng)絡計劃，逐時段計算資源需用量；②逐時段檢查資源需用量是否超過資源限量，若超過進入第③步，否則檢查下一時段；③對于超過的時段，按總時差從小到大累計該時段中的各項工作的資源強度，累計到不超過資源限量的最大值，其余的工作推移到下一時段（在各項工作不允許間斷作業(yè)的假定條件下，將前一時段已經開始的工作應優(yōu)先累計）；④重復上述步驟，直至所有時段的資源需用量均不超過資源限量為止。（2）“工期固定，資源均衡”優(yōu)化在工期不變的條件下，盡量使資源需用量均衡，既有利于工程施工組織與管理，又有利于降低工程施工費用。首先，來了解衡量資源