當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

计划评审方法和关键路线法【PERT/CPM、统筹方法】

發布時間：2023/12/14 编程问答 29 豆豆

生活随笔收集整理的這篇文章主要介紹了计划评审方法和关键路线法【PERT/CPM、统筹方法】小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

【1】圖與網絡模型及方法：圖與網絡的基本概念

【2】圖&網絡模型應用—最短路徑問題

【3】樹：基本概念與最小生成樹

【4】匹配問題：匈牙利算法、最優指派、相等子圖

【5】Euler 圖和 Hamilton 圖

【6】計劃評審方法和關鍵路線法【統籌方法】：廣泛地用于系統分析和項目管理

【7】最小費用流及其求法：

【8】最大流問題??

【10】鋼管訂購和運輸問題

1 計劃網絡圖

1.1 計劃網絡圖的概念? ? ? ? ? ? ? ? ? ? ? ??1.2 建立計劃網絡圖應注意的問題

2 時間參數

2.1 事件時間參數? ? ? ? ? ? ?

（1）事件的最早時間? ? ? ? ? ? ? ? ? ? ?（2）事件的最遲時間

2.2 工作的時間參數?

（1）工作的最早可能開工時間與工作的最早可能完工時間

（2）工作的最遲必須開工時間與工作的最遲必須完工時間

2.3 時差

（1）工作的總時差? ? ? ? ? ? ? ? ?（2）工作的單時差

3 計劃網絡圖的計算

3.1 建立計劃網絡圖? ? ? ? ? ? ? ? ? ? ??3.2 寫出相應的規劃問題

3.3 問題求解? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??3.4 將關鍵路線看成最長路

4 關鍵路線與計劃網絡的優化

4.1 計劃網絡優化的數學表達式? ? ? ? ? ? ? ? ? ? ?4.2 計劃網絡優化的求解

5 完成作業期望和實現事件的概率

計劃評審方法（program evaluation and review technique, PERT）和關鍵路線法（critical path method, CPM）是網絡分析的重要組成部分，它廣泛地用于系統分析和項目管理。計劃評審與關鍵路線方法是在 20 世紀 50 年代提出并發展起來的，1956 年，美國杜邦公司為了協調企業不同業務部門的系統規劃，提出了關鍵路線法。1958 年，美國海軍武裝部在研制“北極星”導彈計劃時，由于導彈的研制系統過于龐大、復雜，為找到一種有效的管理方法，設計了計劃評審方法。由于 PERT 與 CPM 既有著相同的目標應用，又有很多相同的術語，這兩種方法已合并為一種方法，在國外稱為 PERT/CPM，在國內稱為統籌方法（scheduling method）。

1 計劃網絡圖

例 20?某項目工程由 11 項作業組成（分別用代號 A, B,...., J , K 表示），其計劃完成時間及作業間相互關系如表 9 所示，求完成該項目的最短時間。

例 20 就是計劃評審方法或關鍵路線法需要解決的問題。

1.1 計劃網絡圖的概念

【定義】稱任何消耗時間或資源的行動稱為作業。稱作業的開始或結束為事件，事件本身不消耗資源。在計劃網絡圖中通常用圓圈表示事件，用箭線表示工作，如圖 9 所示，1，2，3 表示事件， A, B 表示作業。由這種方法畫出的網絡圖稱為計劃網絡圖。

? ? ? ? ? ? ? ? ? 虛工作用虛箭線“”表示。它表示工時為零，不消耗任何資源的虛構工作。其作用只是為了正確表示工作的前行后繼關系。定義在計劃網絡圖中，稱從初始事件到最終事件的由各項工作連貫組成的一條路為路線。具有累計作業時間最長的路線稱為關鍵路線。 ?

由此看來，例 20 就是求相應的計劃網絡圖中的關鍵路線。

1.2 建立計劃網絡圖應注意的問題

（1）任何作業在網絡中用唯一的箭線表示，任何作業其終點事件的編號必須大于其起點事件。

（2）兩個事件之間只能畫一條箭線，表示一項作業。對于具有相同開始和結束事件的兩項以上的作業，要引進虛事件和虛作業。

（3）任何計劃網絡圖應有唯一的最初事件和唯一的最終事件。

（4）計劃網絡圖不允許出現回路。

（5）計劃網絡圖的畫法一般是從左到右，從上到下，盡量作到清晰美觀，避免箭頭交叉。

2 時間參數

2.1 事件時間參數

（1）事件的最早時間

事件 j 的最早時間用表示，它表明以它為始點的各工作最早可能開始的時間，也表示以它為終點的各工作的最早可能完成時間，它等于從始點事件到該事件的最長路線上所有工作的工時總和。事件最早時間可用下列遞推公式，按照事件編號從小到大的順序逐個計算。

設事件編號為1,2,..., n ，則

其中?是與事件 j 相鄰的各緊前事件的最早時間，t(i, j) 是作業(i, j) 所需的工時。終點事件的最早時間顯然就是整個工程的總最早完工期，即

?= 總最早完工期 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7）

（2）事件的最遲時間

事件i 的最遲時間用表示，它表明在不影響任務總工期條件下，以它為始點的工作的最遲必須開始時間，或以它為終點的各工作的最遲必須完成時間。由于一般情況下，我們都把任務的最早完工時間作為任務的總工期，所以事件最遲時間的計算公式為：

其中是與事件i 相鄰的各緊后事件的最遲時間。

公式（8）也是遞推公式，但與（6）相反，是從終點事件開始，按編號由大至小的順序逐個由后向前計算。

2.2 工作的時間參數

（1）工作的最早可能開工時間與工作的最早可能完工時間

一個工作(i, j) 的最早可能開工時間用?表示。任何一件工作都必須在其所有緊前工作全部完工后才能開始。

工作(i, j) 的最早可能完工時間用?表示。它表示工作按最早開工時間開始所能達到的完工時間。它們的計算公式為：

這組公式也是遞推公式。即所有從總開工事件出發的工作(1, j)，其最早可能開工時間為零；任一工作(i, j) 的最早開工時間要由它的所有緊前工作(k,i) 的最早開工時間決定；工作(i, j) 的最早完工時間顯然等于其最早開工時間與工時之和。

（2）工作的最遲必須開工時間與工作的最遲必須完工時間

一個工作(i, j) 的最遲開工時間用??? 表示。它表示工作(i, j) 在不影響整個任務如期完成的前提下，必須開始的最晚時間。

工作(i, j) 的最遲必須完工時間用表示。它表示工作(i, j) 按最遲時間開工，所能達到的完工時間。它們的計算公式為：

這組公式是按工作的最遲必須開工時間由終點向始點逐個遞推的公式。凡是進入總完工事件 n 的工作(i, n) ，其最遲完工時間必須等于預定總工期或等于這個工作的最早可能完工時間。任一工作(i, j) 的最遲必須開工時間由它的所有緊后工作( j, k) 的最遲開工時間確定。而工作(i, j) 的最遲完工時間顯然等于本工作的最遲開工時間與工時的和。

由于任一個事件i （除去始點事件和終點事件），既表示某些工作的開始又表示某些工作的結束。所以從事件與工作的關系考慮，用公式（9），公式（10）求得的有關工作的時間參數也可以通過事件的時間參數公式（6），公式（8）來計算。如工作(i, j) 的最早可能開工時間?就等于事件i 的最早時間。工作(i, j) 的最遲必須完工時間等于事件 j 的最遲時間。

2.3 時差

工作的時差又叫工作的機動時間或富裕時間，常用的時差有兩種。

（1）工作的總時差

在不影響任務總工期的條件下，某工作(i, j) 可以延遲其開工時間的最大幅度，叫做該工作的總時差，用 R(i, j) 表示。其計算公式為：

即工作(i, j) 的總時差等于它的最遲完工時間與最早完工時間的差。顯然 R(i, j) 也等于該工作的最遲開工時間與最早開工時間之差。

（2）工作的單時差

工作的單時差是指在不影響緊后工作的最早開工時間條件下，此工作可以延遲其開工時間的最大幅度，用 r(i, j) 表示。其計算公式為：

即單時差等于其緊后工作的最早開工時間與本工作的最早完工時間之差。

3 計劃網絡圖的計算

以例 20 的求解過程為例介紹計劃網絡圖的計算方法。

3.1 建立計劃網絡圖

首先建立計劃網絡圖。按照上述規則，建立例 20 的計劃網絡圖，如圖 10 所示。

3.2 寫出相應的規劃問題

3.3 問題求解

用 LINGO 軟件求解例 20。編寫 LINGO 程序如下：

model: sets: events/1..8/:x; operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6, 5 7,5 8,6 7,6 8,7 8/:t; endsets data: t=5 10 11 4 4 0 15 21 25 35 0 20 15; enddata min=x(8)-x(1); @for(operate(i,j):x(j)>x(i)+t(i,j)); end

計算結果給出了各個項目的開工時間，如 ?x1 = 0 ，則作業 A, B,C 的開工時間均是第 0 天； ?x2 = ?5，作業 E 的開工時間是第 5 天； x3 = 10，則作業 D 的開工時間是第 10 天；等等。每個作業只要按規定的時間開工，整個項目的最短工期為 51 天。

盡管上述 LINGO 程序給出相應的開工時間和整個項目的最短工期，但統籌方法中許多有用的信息并沒有得到，如項目的關鍵路徑、每個作業的最早開工時間、最遲開工時間等。

例 21（續例 20）求例 20 中每個作業的最早開工時間、最遲開工時間和作業的關鍵路徑。

編寫 LINGO 程序如下：

model: sets: events/1..8/:x,z; operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6, 5 7,5 8,6 7,6 8,7 8/:s,t,m,c,y; endsets data: t=5 10 11 4 4 0 15 21 25 35 0 20 15; m=5 8 8 3 4 0 15 16 22 30 0 16 12; c=0 700 400 450 0 0 0 600 300 500 0 500 400; d=49; @text(txt2.txt)=x,z; enddata min=mincost+sumx; mincost=@sum(operate:c*y); sumx=@sum(events:x); @for(operate(i,j):s(i,j)=x(j)-x(i)+y(i,j)-t(i,j)); n=@size(events); x(1)=0; x(n)<d; @for(operate:@bnd(0,y,t-m)); z(n)=x(n); @for(events(i)|i#lt#n:z(i)=@min(operate(i,j):z(j)-t(i,j)+y(i,j))); end

最遲開工時間的分析需要用到松弛變量 sij ，當 sij > 0時，說明還有剩余時間，對應作業的工期可以推遲 sij 。例如，s78 = 1，作業（7，8）（ J ）的開工時間可以推遲 1 天，即開工時間為 36。再如 s46 = 2 ，作業（4，6）（ F ）可以推遲 2 天開始， 3 s14 = ，作業（1，4）（C ）可以推遲 3 天開始，但由于作業（4，6）（ F ）已能夠推遲 2 天，所以，作業（1，4）（C ）最多可推遲 5 天。由此，可以得到所有作業的最早開工時間和最遲開工時間，如下表所示，方括號中第 1 個數字是最早開工時間，第 2 個數字是最遲開工時間。

從上表可以看出，當最早開工時間與最遲開工時間相同時，對應的作業在關鍵路線上，因此可以畫出計劃網絡圖中的關鍵路線，如圖 11 粗線所示。關鍵路線為 1→3→ 5→6→8。

3.4 將關鍵路線看成最長路

如果將關鍵路線看成最長路，則可以按照求最短路的方法（將求極小改為求極大）求出關鍵路線。

例 22 用最長路的方法，求解例 20。 ?按上述數學規劃問題寫出相應的 LINGO 程序。

model: sets: events/1..8/:d; operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6, 5 7,5 8,6 7,6 8,7 8/:t,x; endsets data: t=5 10 11 4 4 0 15 21 25 35 0 20 15; d=1 0 0 0 0 0 0 -1; enddata max=@sum(operate:t*x); @for(events(i):@sum(operate(i,j):x(i,j))-@sum(operate(j,i):x(j,i))=d(i)); end

求得工期需要 51 天，關鍵路線為 1→3→5→6→8。

4 關鍵路線與計劃網絡的優化

例 23（關鍵路線與計劃網絡的優化）假設例 20 中所列的工程要求在 49 天內完成。為提前完成工程，有些作業需要加快進度，縮短工期，而加快進度需要額外增加費用。下表列出例 20 中可縮短工期的所有作業和縮短一天工期額外增加的費用?，F在的問題是，如何安排作業才能使額外增加的總費用最少。

例 23 所涉及的問題就是計劃網絡的優化問題，這時需要壓縮關鍵路徑來減少最短工期。

4.1 計劃網絡優化的數學表達式

4.2 計劃網絡優化的求解

用 LINGO 軟件求解例 23，程序如下：

model: sets: events/1..8/:x; operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6, 5 7,5 8,6 7,6 8,7 8/:t,m,c,y; endsets data: t=5 10 11 4 4 0 15 21 25 35 0 20 15; m=5 8 8 3 4 0 15 16 22 30 0 16 12; c=0 700 400 450 0 0 0 600 300 500 0 500 400; d=49; enddata min=@sum(operate:c*y); @for(operate(i,j):x(j)-x(i)+y(i,j)>t(i,j)); n=@size(events); x(n)-x(1)<d; @for(operate:@bnd(0,y,t-m)); end

作業(1,3)(B) 壓縮 1 天的工期，作業(6,8)(K) 壓縮 1 天工期，這樣可以在 49 天完工，需要多花費 1200 元。如果需要知道壓縮工期后的關鍵路徑，則需要稍復雜一點的計算。

例 24 （續例 23）用 LINGO 軟件求解例 23，并求出相應的關鍵路徑、各作業的最早開工時間和最遲開工時間。解為了得到作業的最早開工時間，仍在目標函數中加入 ?，記 zi 表示事件i 的最遲開工時間，其它處理方法與前面相同。寫出相應的 LINGO 程序如下：

計算出所有作業的最早開工時間和最遲開工時間，見表 12。

當最早開工時間與最遲開工時間相同時，對應的作業就在關鍵路線上，圖 12 中的粗線表示優化后的關鍵路線。從圖 5-10 可以看到，關鍵路線不止一條。

5 完成作業期望和實現事件的概率

在例 20 中，每項作業完成的時間均看成固定的，但在實際應用中，每一工作的完成會受到一些意外因素的干擾，一般不可能是完全確定的，往往只能憑借經驗和過去完成類似工作需要的時間進行估計。通常情況下，對完成一項作業可以給出三個時間上的估計值：最樂觀值的估計值（ a ），最悲觀的估計值（b ）和最可能的估計值（ m ）。

設 ?是完成作業(i, j) 的實際時間（是一隨機變量），通常用下面的方法計算相應的數學期望和方差。

例 25 已知例 20 中各項作業完成的三個估計時間如下表所示。如果規定時間為 52 天，求在規定時間內完成全部作業的概率。進一步，如果完成全部作業的概率大于等于 95％，那么工期至少需要多少天？

解對于這個問題采用最長路的編寫方法。按公式（13）和公式（14）計算出各作業的期望值與方差，再由期望時間計算出關鍵路線。從而由公式（16）和公式（17）得到關鍵路線的期望與方差的估計值，再利用分布函數@psn(x)，計算出完成作業的概率與完成整個項目的時間。寫出相應的 LINGO 程序如下：

model: sets: events/1..8/:d; operate(events,events)/1 2,1 3,1 4,2 5,3 4,3 5,4 6,5 6, 5 7,5 8,6 7,6 8,7 8/:a,m,b,et,dt,x; endsets data: a=3 8 8 3 2 0 8 18 18 26 0 11 12; m= 5 9 11 4 4 0 16 20 25 33 0 21 15; b=7 16 14 5 6 0 18 28 32 52 0 25 18; d=1 0 0 0 0 0 0 -1; limit=52; enddata @for(operate:et=(a+4*m+b)/6;dt=(b-a)^2/36); max=tbar; tbar=@sum(operate:et*x); @for(events(i):@sum(operate(i,j):x(i,j))-@sum(operate(j,i):x(j,i))=d(i)); s^2=@sum(operate:dt*x); p=@psn((limit-tbar)/s); @psn((days-tbar)/s)=0.95; end

求得關鍵路線的時間期望為 51 天，標準差為 3.16，在 52 天完成全部作業的概率為 62.4%，如果完成全部作業的概率大于等于 95％，那么工期至少需要 56.2 天。