第五章 運輸系統(tǒng)優(yōu)化控制

交通運輸系統(tǒng)工程集美大學航海學院任亞東201212852001第五章運輸系統(tǒng)優(yōu)化控制123ABContents網(wǎng)絡圖的組成概述網(wǎng)絡圖的繪制第一節(jié)概述PERT（ProgramEvaluationReviewTechnique）網(wǎng)絡計劃技術,計劃協(xié)調(diào)技術，計劃評審技術，統(tǒng)籌法CPM（CriticalPathMethod）關鍵線路法1958年，美國海軍部特種計劃局，在制造北極星導彈的工程管理中提出的。北極星導彈的制造工程由8家總承包公司，250家分包公司，3000家分包公司，9000家廠商承擔。由于使用了PERT技術，提高了工作效率，是整個工程的研制工作提前了兩年完成。1957年，美國化學公司DuPont的M.R.Walker與Rand通用電子計算機公司的J.E.Kelly為了協(xié)調(diào)公司內(nèi)部不同業(yè)務部門的工作，共同研究出關鍵路線方法（簡記作CPM）.首次把這一方法用于一家化工廠的籌建，結(jié)果籌建工程提前兩個月完成.隨后又把這一方法用于工廠的維修，結(jié)果使停工時間縮短了47個小時，當年就取得節(jié)約資金達百萬元的要觀效益?；舅枷肭蠛们罂烨笫〗y(tǒng)籌兼顧基本原理網(wǎng)絡計劃技術：是以工序所需時間為基礎，用描述工序之間相互聯(lián)系的網(wǎng)絡和網(wǎng)絡時間的計算，反映整個工程或任務的全貌，并在規(guī)定條件下，全面籌劃、統(tǒng)一安排，來尋求達到目標的最優(yōu)方案的計劃技術。

網(wǎng)絡圖的類型:信息流網(wǎng)絡時間流網(wǎng)絡物質(zhì)流網(wǎng)絡第二節(jié)網(wǎng)絡圖的組成工作（工序）Activities工作是泛指一項需要消耗人力、物力和時間的具體活動過程，又稱為工序或活動。工作是用箭線表示的。箭尾表示工作的開始，箭頭表示工作的完成。12A工作結(jié)束（箭頭）工作開始（箭尾）工作名稱工作工作時間事項事項（節(jié)點）Event事項是兩個工作之間的銜接點。事項是一項作業(yè)的開始或完工的瞬間階段點，它不消耗人力、物力和時間。節(jié)點用圓圈“○”表示，圓圈中編上整數(shù)號碼，稱為節(jié)點編號。節(jié)點三種類型：開始節(jié)點、結(jié)束節(jié)點、中間節(jié)點。

123456線路Path從始點開始順著箭頭所指的方向，連續(xù)不斷到達終點為止的一條通道稱為線路。網(wǎng)絡圖中所需工時最長的路線稱為關鍵路線。關鍵路線上的工序稱為關鍵工序。注意：（1）關鍵路線的完成時間決定整個工程的完工時間；

（2）關鍵路線可能不止一條。關鍵路線越多，組織工作越好，安排越緊湊；

（3）關鍵路線與非關鍵路線可以轉(zhuǎn)化。虛箭線DummyArrow用虛線畫的箭線，稱為虛作業(yè)，一般無作業(yè)代號，亦無作業(yè)時間，它不占用時間，亦不消耗任何人力物力資源，它只是表示作業(yè)時間的緊前或緊后關系。C123456ABDEF一般網(wǎng)絡圖的繪制可以分為三個步驟：1、任務的分解2、作圖3、編號第三節(jié)網(wǎng)絡圖的繪制一、任務分解1、分解原則2、分解步驟工作之間的關系

緊前工作（precedingactivity）：緊排在該工作之前的工作。

緊后工作（followingactivities）：緊排在本工作之后的工作。

平行工作：如果有多個工序可以同時開工，而完工允許有先后，作業(yè)流程的這一環(huán)節(jié)稱為平行作業(yè)，顯見，平行作業(yè)最有利于縮短工程完工時間。

交叉工作：如果某種任務是多次重復多道工序的作業(yè)，那么可以把各次作業(yè)中的各道工序穿插起來進行，這樣的工作方式稱為交叉作業(yè)。交叉作業(yè)有利于縮短工程完工時間，所以只要有可能，也應該盡量采用。[例]某農(nóng)場有3000公頃土地，在夏收時同一塊地土上必須先割（a工序），再耕地（b工序），最后播種（c工序）。若各工序工期均需12天。統(tǒng)籌圖如圖1，夏收需36天完成。工序a1a2b1b2c1c2緊前工序-a1a1a2,b1b1b2,c1實際上不可能等3000公頃全部收割完后再去耕地，同時另一作業(yè)隊收割另一部分，幾個工序交叉進行。如果將a=a1+a2,b=b1+b2,c=c1+c2,各工期為6天。此時統(tǒng)籌圖如圖2，夏收夏種需24天。

1234abc12121212345678a1b1c1a2b2c2666666如果a=a1+a2+a3,b=b1+b2+b3,c=c1+c2+c3。各工期為4天，工序相互關系如表，統(tǒng)籌圖如圖，總工期縮短至20天，比沒有交叉作業(yè)需36天少16天。工序緊前工序工序緊前工序a1-b3a3,b2a2a1c1b1a3a2c2b2,c1b1a1c3b3,c2b2a2,b1

12375468910a1b1c1a2b2a3c2b3c3444444444繪圖規(guī)則

(1)網(wǎng)絡圖必須按照已定的邏輯關系繪制。

1234ABCD必須正確表達邏輯關系（a）A、B兩項工作依次進行（b）A、B、C三項工作同時開工（c）A、B、C三項工作同時結(jié)束ABABCABC（d）A、B、C三項工作，A結(jié)束后，B、C開始ABCBCA（e）A、B、C三項工作，A、B結(jié)束后，C開始(2)網(wǎng)絡圖中嚴禁出現(xiàn)從一個節(jié)點出發(fā)，順箭頭方向又回到原出發(fā)點的循環(huán)回路。(3)網(wǎng)絡圖中的箭線(包括虛箭線，以下同)應保持自左向右的方向，不應出現(xiàn)箭頭指向左方的水平箭線和箭頭偏向左方的斜向箭線。(4)網(wǎng)絡圖中嚴禁出現(xiàn)雙向箭頭和無箭頭的連線。

123451243

(5)網(wǎng)絡圖中嚴禁出現(xiàn)沒有箭尾節(jié)點的箭線和沒有箭頭節(jié)點的箭線。

(6)嚴禁在箭線上引入或引出箭線

當網(wǎng)絡圖的起點節(jié)點有多條箭線引出(外向箭線)或終點節(jié)點有多條箭線引入(內(nèi)向箭線)時，為使圖形簡潔，可用母線法繪圖。即：將多條箭線經(jīng)一條共用的垂直線段從起點節(jié)點引出，或?qū)⒍鄺l箭線經(jīng)一條共用的垂直線段引入終點節(jié)點。123456ABCDE101112131415IJKLM母線法(7)應盡量避免網(wǎng)絡圖中工作箭線的交叉。當交叉不可避免時，可以采用過橋法或指向法處理(8)網(wǎng)絡圖中相鄰節(jié)點之間只能有一條箭線

(8)網(wǎng)絡圖中應只有一個起點節(jié)點和一個終點節(jié)點

圖（a）中，節(jié)點①、②和③都表示計劃的開始，12、13和14都表示計劃的完成，是錯誤的。此時，正確的畫法如圖（b）。（9）同一項工作在一個網(wǎng)絡圖中不表現(xiàn)兩次以上圖（a）中，工作D出現(xiàn)兩次，這是不允許的。此時應引進虛工作，表達成圖（b）繪圖方法

1．繪制沒有緊前工作的工作箭線，使它們具有相同的開始節(jié)點，以保證網(wǎng)絡圖只有一個起點節(jié)點。

2.依次繪制其他工作箭線。在繪制這些工作箭線時，應按下列原則進行：

(1)當所要繪制的工作只有一項緊前工作時，則將該工作箭線直接畫在其緊前工作箭線之后即可。

ijkAB(2)當所要繪制的工作有多項緊前工作時，應按以下四種情況分別予以考慮：

①對于所要繪制的工作(本工作)而言，如果在其緊前工作之中存在一項只作為本工作緊前工作的工作(即在緊前工作欄目中，該緊前工作只出現(xiàn)一次)，則應將本工作箭線直接畫在該緊前工作箭線之后，然后用虛箭線將其他緊前工作箭線的箭頭節(jié)點與本工作箭線的箭尾節(jié)點分別相連，以表達它們之間的邏輯關系。

②對于所要繪制的工作(本工作)而言，如果在其緊前工作之中存在多項只作為本工作緊前工作的工作，應先將這些緊前工作箭線的箭頭節(jié)點合并，再從合并后的節(jié)點開始，畫出本工作箭線，最后用虛箭線將其他緊前工作箭線的箭頭節(jié)點與本工作箭線的箭尾節(jié)點分別相連，以表達它們之間的邏輯關系。

③對于所要繪制的工作(本工作)而言，如果不存在情況①和情況②時，應判斷本工作的所有緊前工作是否都同時作為其他工作的緊前工作(即在緊前工作欄目中，這幾項緊前工作是否均同時出現(xiàn)若干次)。如果上述條件成立，應先將這些緊前工作箭線的箭頭節(jié)點合并后，再從合并后的節(jié)點開始畫出本工作箭線。

④對于所要繪制的工作(本工作)而言，如果既不存在情況①和情況②，也不存在情況③時，則應將本工作箭線單獨畫在其緊前工作箭線之后的中部，然后用虛箭線將其各緊前工作箭線的箭頭節(jié)點與本工作箭線的箭尾節(jié)點分別相連，以表達它們之間的邏輯關系。

3．當各項工作箭線都繪制出來之后，應合并那些沒有緊后工作之工作箭線的箭頭節(jié)點，以保證網(wǎng)絡圖只有一個終點節(jié)點。4．當確認所繪制的網(wǎng)絡圖正確后，即可進行節(jié)點編號。網(wǎng)絡圖的節(jié)點編號在滿足前述要求的前提下，既可采用連續(xù)的編號方法，也可采用不連續(xù)的編號方法，如1、3、5、……或5、10、15、……等，以避免以后增加工作時而改動整個網(wǎng)絡圖的節(jié)點編號。

ThankYou!第四節(jié)網(wǎng)絡圖時間參數(shù)的計算任亞東201212852001網(wǎng)絡圖時間參數(shù)的計算，是網(wǎng)絡分析的重要環(huán)節(jié)，是編制網(wǎng)絡計劃，尋找關鍵線路的前提。尋找關鍵線路有兩種途徑：1、計算網(wǎng)絡圖中事項的時間參數(shù)2、計算網(wǎng)絡圖中工作的時間參數(shù)網(wǎng)絡時間參數(shù)的計算方法有3種：（1）公式計算法（2）圖上計算法（3）表格計算法一、事項時間參數(shù)的計算1、事項的最早開始時間2、事項的最遲結(jié)束時間3、事項的時差1、事項的最早開始時間1、事項的最早開始時間1、事項最早開始時間定義：從始點起到此事項的最長路線的時間之和。計算順序：=0

（j=2,3，…，n）式中：——箭頭事項的開始時間；

——箭尾事項的最早開始時間；

——工作的工作時間表示方法：事項的最早開始時間算出后，直接標在事項的上方，用“□”框起來ijjj2、事項的最遲結(jié)束時間定義：在這個時間里該事項必須完成，若不能完成，就會影響緊后各項工作按時開始。計算順序：從終點開始，自右向左，逐個計算，直至始點。計算公式：式中：——終點的最遲結(jié)束時間；

——終點的最早開始時間；

——箭尾事項的最遲結(jié)束時間；

——箭頭事項的最遲結(jié)束時間。表示方法：事項的最遲結(jié)束時間算出來后，直接標在事項的下方，用三角形“△”框起來。ii3、事項的時差定義：指事項的最遲結(jié)束時間與最早開始時間之差。計算順序：在網(wǎng)絡圖上自左至右或自右至左計算；計算公式：用符號計算：=△-□時差為零的事項稱為關鍵事項，結(jié)合事項參數(shù)的計算，把關鍵事項串起來，就得到了關鍵線路。二、工作時間參數(shù)的計算1、工作最早開始時間2、工作最早結(jié)束時間3、工作最遲結(jié)束時間4、工作最遲開始時間5、工作總時差6、工作單時差1、工作最早開始時間任何一個工作都必須在其緊前工作結(jié)束后才能開始，緊前工作的最早結(jié)束時間，即是該工作的最早可能開始的時間，簡稱工作最早開始時間，它等于該工作箭尾事項的最早開始時間：2、工作最早結(jié)束時間工作最早結(jié)束時間，是工作可能結(jié)束時間的簡稱，它等于工作最早開始時間加上完成該工作所需要的工作時間。即：3、工作最遲結(jié)束時間在不影響工程最早結(jié)束時間的前提下，工作最遲必須結(jié)束的時間，簡稱工作最遲結(jié)束時間，它等于工作箭頭事項的最遲結(jié)束時間。即：4、工作最遲開始時間在不影響工程最早結(jié)束時間的條件下，工作最遲必須開始的時間，簡稱工作最遲開始時間，它等于工作最遲結(jié)束時間減去完成工作所需的時間。即5、工作總時差在不影響工程最早結(jié)束時間的條件下，工作最早開始或結(jié)束時間可以推遲的時間，稱為該工作的總時差。即：6、工作單時差在不影響緊后工作的最早開始時間的條件下，工作最早時間可以推遲的時間，稱為工作的單時差。即：式中：——工序i→j的緊后工序的最早開始時間。用表格法計算時間參數(shù)工作代號事項時間參數(shù)關鍵工作A*BThankyou！問題：1、工作和事項的區(qū)別工作是指一項有具體活動的過程，需要消耗人力、物力、時間；事項是指兩個工作之間的銜接點，不需要消耗人力，資源，時間。2、“三點估計法”求時間的平均值

平均作業(yè)時間3、說明事項時差的含義事項的時差等于事項的最遲結(jié)束時間減去事項的最早結(jié)束時間，其差值代表事項的富余時間的多少，若是差值為零，則該事項為關鍵事項，，把關鍵事項串起來，就得到了關鍵線路。第五節(jié)網(wǎng)絡圖的優(yōu)化梁晨網(wǎng)絡圖的優(yōu)化與控制，主要討論：工期最短，即縮短工程進度；費用最低，即確定最低成本日程；資源最優(yōu)，使有限的資源得到合理的安排和使用。1、縮短工程進度采取技術措施壓縮關鍵工作的工作時間。比如，采取改進工藝方案、合理劃分工序組成、改進工藝裝備等措施，來壓縮工作時間。采取組織措施在工藝流程允許的條件下，對關鍵線路上的各關鍵工作組織平行作業(yè)或交叉作業(yè)，合理調(diào)配工程技術人員或生產(chǎn)工人，盡量縮短各道關鍵工作的工作時間，達到縮短工期的目的。利用時差從非關鍵工作上抽調(diào)部分人力、物力，集中用于關鍵工作，縮短關鍵工作的時間，達到縮短工期的目的。例題某項工程的有關資料如表所示，另外，每天可以安排的人員數(shù)只有10人，要求工程在15天里完成，應如何安排工程進度，在現(xiàn)有人力資源下按期完成任務？步驟：1、找出現(xiàn)狀：1）畫出網(wǎng)絡圖；2）畫出每天對人員的需要量的直方圖。2、計劃調(diào)整1）網(wǎng)絡圖關鍵線路為：1->2->4->5。關鍵線路的路長為19天，但完工期是15天，不能滿足完工期的要求。2）人員需要量的直方圖0-456-89-10ABCBCDCDF4+4+3=114+3=74+3=74+1=5前4天內(nèi)每天所需人員就為11人，但是每天可以安排的人員只有10人，不能滿足人員需求的要求。0-456-89-10ABCBCDCDF4+4+3=114+3=74+3=74+1=5444337計劃人員為10人3、計劃調(diào)整為了在現(xiàn)有人力資源條件下，按期完工，所以在保證關鍵工作的人員配置的情況下，要想辦法從非關鍵工作抽調(diào)人力，支援關鍵工作。比如，對計劃作如下調(diào)整：從非關鍵工作A上抽調(diào)人員2名，分別支援關鍵工作B上1名，關鍵工作D上1名。這樣，工作A的工作時間將延長至8天，而工作B和工作D的工作時間都將縮短為4天。從非關鍵工作A上抽調(diào)人員2名，分別支援關鍵工作B中1名，關鍵工作D中1名。工作A的工作時間將延長至8天，而工作B和工作D的工作時間都將縮短為4天關鍵線路為：1->2->4->5。非關鍵線路為：1->4->5、1->3->5。A抽調(diào)2名人員，原來工作要4個人，所以現(xiàn)在工作時間要加倍，變?yōu)?天。A抽調(diào)1名人員給B，B原來需要4個人做5天。(4/5)x5=4，故加多1個人，工期變?yōu)?天。從非關鍵工作A上抽調(diào)人員2名，分別支援關鍵工作B中1名，關鍵工作D中1名。工作A的工作時間將延長至8天，而工作B和工作D的工作時間都將縮短為4天從非關鍵工作F上抽調(diào)人員2名，支援關鍵工作E，這樣工作F的工作時間將延長至3天，而工作E的工作時間將縮短為7天[E:(7/9)x9=7天；F:(3/1)x1=3天]。調(diào)整后，工期為15天，滿足要求，且每天堆人員的需要量也不超過10人。25519253591總結(jié)：縮短工程進度繪制網(wǎng)絡圖畫出每天對人員的需要量的直方圖，對比條件限制計劃調(diào)整從非關鍵工作上抽調(diào)人員分別支援關鍵工作，使非關鍵工作時間延長，關鍵工作時間縮短。請自己做一遍某項工程的有關資料如表所示，另外，每天可以安排的人員數(shù)只有10人，要求工程在15天里完成，應如何安排工程進度，在現(xiàn)有人力資源下按期完成任務？1、請畫出網(wǎng)絡圖2、請畫出每天對人員的需要量的直方圖3、請作計劃調(diào)整：從非關鍵工作A上抽調(diào)人員2名給工作B和D，從非關鍵工作F上抽調(diào)人員2名支援工作E2、時間成本優(yōu)化基本思想：縮短工程進度，僅僅考慮了系統(tǒng)的時間因素，若要達到系統(tǒng)整體的最優(yōu)，還必須綜合考慮時間、成本各方面的因素。也就是既要時間最短，又要成本最低。就成本而言，一項工程或任務，一般都具有三類成本：直接成本、間接成本和趕工成本。直接成本：直接用來完成工程任務的費用成為直接成本。例如：人工費、材料費、燃料費。直接費用直接分攤到每一道工序，若要縮短工序的工作時間，相應地就要增加一部分直接費用。間接成本：在某些工程項目中，間接成本是按照各道工序所消耗的時間比例進行分攤的。如管理人員的工資、辦公費、采購費等就屬于間接成本。工序的工作時間越短，分攤到該工序的間接費用就越少；工程周期越短，則工程的間接費用就越少。趕工成本：在增加了人力、物力等資源以后，使工期得以縮短而需要的費用。工程總費用=直接費用+間接費用+趕工費用時間成本優(yōu)化兩個目標盡可能使工期最短使完成工程所需的總費用最低基本概念正常時間：指按原計劃進行所需要的時間。趕工時間：指多派人力物力后，完成該工作所需要的時間。正常成本：指按原計劃進行所需要的成本。趕工成本：指趕工使工期縮短后該工程的成本。成本斜率：指趕工一天所需要的成本。例如某工程由4項工作組成，其有關資料如表所示。又知，該工程的間接成本為每天4500元，試進行時間成本優(yōu)化。例題某工程由4項工作組成，其有關資料如表所示。又知，該工程的間接成本為每天4500元，試進行時間成本優(yōu)化。方法：1）找出該工程的直接費用；2）畫出網(wǎng)絡圖，找出關鍵線路；3）找出總費用；4）改進某工程由4項工作組成，其有關資料如表所示。又知，該工程的間接成本為每天4500元，試進行時間成本優(yōu)化。1、直接費用=10+15+12+8=45千元2、關鍵線路為1->2->3->4，路長為12，即總工期為12天。3、總費用=45000+4500x12+0=99000元改進富裕線路為1->2->4，路長為10，總工期為10天有2天的富裕時間。為使工期最短，就要縮短關鍵線路上的工作時間；同時，為了使成本最低，就要從成本斜率最低（單位時間的成本最低）的關鍵工作上著手來縮短工期。改進：方案一分析關鍵線路的關鍵工作ACD，工作D的趕工成本斜率最低，故在工作D上趕工。（工作D最多可趕工3天，但若趕工3天，則關鍵線路1-2-3-4的工期就變?yōu)?天，工期小于線路1-2-4的工期，這是不允許的）。故工作D最多只能趕工2天。富余線路不能比關鍵線路工時多，否則就不是資源支援，而是犧牲了改進：方案一故工作D最多只能趕工2天。就有兩條關鍵線路1->2->3->4和1->2->4，工期均為10天。D=3天10|10改進：方案二由于此時有兩條關鍵線路，故若要再縮短工期，就要同時考慮兩條關鍵線路。分析改進方案一，可知，此時可選擇的趕工方案如表所示。（前或后，同時的元素不同）10|10D=3天改進：方案二從表中可以看到，第3種方案的趕工費用最低，故首先選擇B、D各趕工1天的方案。這樣，關鍵線路仍然保持不變，工期變?yōu)?天。9|9D=2天B=6天D=3天從表中可以看到，第3種方案的趕工費用最低，故首先選擇B、D各趕工1天的方案。這樣，關鍵線路仍然保持不變，工期變?yōu)?天。改進：方案三由圖可知，若再要趕工，應選擇A趕工，A可以趕工2天，故在A工作上趕工2天，工期變?yōu)?天。7|7D=3天B=6天A=1天D=2天改進：方案三選擇A趕工，工期變?yōu)?天?？傎M用45000+45000x7+2000x3+1000x1+4000x2=91500元此時可以趕工的方案只剩下B、C同時趕工，但若B、C同時趕工1天，趕工費用為5000元，大于工程每天的間接費用（4500元），故再繼續(xù)趕工已經(jīng)不合算。間接費用：在某些工程項目中，間接成本是按照各道工序所消耗的時間比例進行分攤的。如管理人員的工資、辦公費、采購費等就屬于間接成本。工序的工作時間越短，分攤到該工序的間接費用就越少；工程周期越短，則工程的間接費用就越少總結(jié)：時間成本優(yōu)化第一步按最小的成本斜率，找到最好的趕工工作?？紤]趕工能趕多少天，找出關鍵線路和總工期第二步考慮可選擇的趕工方案，找到趕工成本最低的方案考慮趕工時間，找出總工期第三步再考慮趕工可選擇的方案，找出總工期進行改進直到趕工成本小于間接成本為止請自己練習一遍某工程由4項工作組成，其有關資料如表所示。又知，該工程的間