圖與網(wǎng)絡(luò)分析

5

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

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

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

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

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

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

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

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

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

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

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

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

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

其中發(fā)點的總流量（或收點的總流量）v（f）叫做這個可行流的流量。（3）最大流最大流：是指在一個網(wǎng)絡(luò)中，流量最大的可行流?？尚辛髦衒ij＝cij的弧叫做飽和弧，fij＜cij的弧叫做非飽和弧。fij＞0的弧為非零流弧，fij＝0的弧叫做零流弧。如下圖5.21所示，(v4,v3)是飽和弧，其他的弧是非飽和弧，并且都是非零流弧。設(shè)μ是網(wǎng)絡(luò)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的關(guān)于f的一條增廣鏈。例如在圖5.21中，鏈μ=（vs,v1,v2,v3,v4,vt）就是一條增廣鏈。5.4.2網(wǎng)絡(luò)的截集和截集容量(1）網(wǎng)絡(luò)的截集設(shè)一個網(wǎng)絡(luò)D＝（V，A，C）。如果節(jié)點集V被分為兩個非空集合S、，發(fā)點vs∈S，收點vt∈,那么將弧集(S,)叫做是分離vs和vt的截集。

（2）截集容量

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

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

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

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

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

LSi-j-LFi-j－Di-j

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