基于Monte Carlo網絡的進度風險分析

蔡永勇++呂超賢++許燕++徐永紅

摘要：由于現代項目的大型化和項目復雜性的不斷增加，如何對項目的進度進行正確的預測和合理的規劃已經受到越來越多的關注，傳統的CPM/PERT方法已經難以滿足人們的需要。本文對現有的進度評估技術進行了改進，加入了對四種任務邏輯關系的支持，并給出了資源沖突時的解決策略，設計并實現了一個面向復雜項目的進度風險評估方法，不僅支持多種隨機變量的抽樣，還能夠給出工期優化策略，旨在幫助項目決策者根據仿真結果識別關鍵任務，以此來制定合理的工期計劃。

關鍵詞：進度風險評估；Monte Carlo網絡；成本風險

中圖分類號：TP391. 41

文獻標識碼：A

DOI： 10.3969/j.issn.1003-6970.2015.07.013

0 引言

根據現在美國項目管理協會的劃分，風險管理過程分為規劃風險管理、風險識別、實施定性風險分析、實施定量風險分析、規劃風險應對、監控風險6個部分。而風險類型又主要有費用風險、進度風險、技術風險、計劃風險等等。而項目在實際運作中，會受到諸多因素的影響。項目在施工過程中，人們往往將項目的進度作為最重要的控制目標，尤其是在大型工程項目的建設上，項目進度常被當做首要控制目標。

“Monte Carlo”一詞源于摩納哥的Monte Carlo賭場，賭場中“輪盤賭”之類的游戲與概率、隨機抽樣等有著類似的原理。Monte Carlo網絡法亦稱為隨機抽樣法，該法是實驗數學的一個分支，是利用隨機數進行統計實驗來解算數學問題的方法。Monte Carlo網絡的本質是對隨機變量進行概率分布估計，具體的做法是用隨機抽樣來抽取符合特定分布的偽隨機數，采用某種特定方法產生隨機數和隨機變量，仿真隨機事件，對結果進行統計處理，從而得到問題的解。

Monte Carlo網絡方法根據事物運動過程的數量和幾何特征，在確定的分布中提取隨機變量，進行多次抽樣。在具體的實驗中，模擬次數越多，Monte Carlo網絡的精度也越高。

Monte Carlo網絡的基本步驟是：（1）通過敏感性分析，確定風險變量。（2）構造風險變量的概率分布模型。（3）根據項目特點確定風險問題的評價指標，建立風險問題數學模型。（4）根據項目投資者的風險承受能力確定模擬次數N。（5）對各個備選方案風險變量進行隨機抽樣。（6）將各個備選方案的風險變量的隨機抽樣值根據所建立的數學模型或者計算流程圖計算出項目評價基礎數據。（7）對各個備選方案風險變量進行N次重復抽樣，產生各方案的抽樣值。（8）對各方案的結果進行統計分析。

本文應用并優化Monte Carlo網絡算法，包括隨機變量的生成以及考慮任務邏輯關系和資源的關鍵鏈算法且提出了當資源沖突時的解決方法。

1 隨機變量的生成

在進度管理中，任務的工時是一種期望值，應當作隨機變量來處理。而在傳統的CPM方法中，工時直接被當作常量來處理，到了PERT方法中，開始認為工時服從Beta分布，進而通過估算最低值a，最可能值m，以及最高值b，來近似求得服從Beta分布的工時的均值 ，以及方差 ，但依舊誤差很大。鑒于現代復雜項目任務的復雜性，通過隨機方法來進行模擬能夠有效減少誤差。

本文采用Monte Carlo方法，通過構造概率模型并對它進行隨機試驗來解算數學問題。Monte Carlo的核心在于根據已知分布產生簡單子樣，也就是產生一系列相互獨立且服從總體分布的隨機數。計算機高級語言都支持隨機數的產生，且可以認為它們是相互獨立且服從均勻分布的數列，因此剩下的工作就是根據這些服從均勻分布的數列產生服從特定分布的數列。

因為實際項目中任務服從的分布以連續分布為主，因此下面所述的方法和分布若無特殊說明，均是建立在連續分布的基礎上。對于形如 ，的累積分布函數，目前主要的抽樣方法有直接抽樣法（又叫反函數法，逆變換法），合成法和篩選法。

本文針對三種特定的分布分別給出抽樣原理和實現步驟。

1.1 三角分布抽樣

三角分布亦稱辛普森（Simpson）分布，是一種連續概率分布函數。三角分布通常可以看作一種經驗性的描述，比如可以用來描述人口，特別是當數據之間的關系已知而數據量又非常少的時候，它通過最小值、最大值和最可能的值來建立模型進行經驗性的判斷。三角分布的累積分布函數（cumulativedistribution function）如（1）式，其中a為低限、c為眾數、b為上限，其中a代表的含義是出現最小值的概率，b代表的含義是出現最大值的概率，c代表的含義是出現最可能的值的概率：

（1）通過隨機數生成器生成服從U（O，1）的隨機數U。

（2）計算廠（x）的反函數f^-1（x），獲取樣本x=f^-1（U）

因此，對于生成的隨機數U，每次樣本x取值應該為

1.2 正態分布抽樣正態分布又名高斯分布，其概率密度函數為

，而累計積分函數為 ，因為 無法直接計算，可見直接抽樣法對正太分布來說比較困難，目前主要的方法是進行近似計算，比如中提出的算法可以精確到小數點后16位。不過因為步驟繁瑣，難以編程實現，因此這里選用的是Box-Muller方法來進行抽樣。Box-Muller算法隱含的原理雖然深奧，但結論卻是相當簡單：

（1）通過隨機數生成器生成服從U（O，1）的隨機數U和V

（2）計算 和

其中X和Y分別服從標準正太分布且相互獨立，可以任選其一作為抽樣結果，假設選取X作為結果，根據正態分布的特性，通過計算Xxa+μ即可，就可以得到服從N（μ，σ）的抽樣。

1.3 β分布抽樣

β分布是一個作為伯努利分布和二項式分布的共軛先驗分布的密度函數，在機器學習和數理統計學中有重要應用，主要用途就是給受限于有限長度的隨機變量來建立模型。β累積分布函數 ，可以看出直接抽樣也是比較困難的，比較常用的方法有合成法和接受拒絕法。其中合成法依賴的定理是如果x和Y相互獨立，且x服從 ，Y服從 ，那么 服從B（a，β）分布。雖然β分布難以直接抽樣，但γ分布容易抽樣，因此可以通過γ分布來合成β分布，不過γ分布一般通過大量指數分布來合成，也比較耗時，這里采用馮諾依曼提出的接受.拒絕的方法來進行抽樣。endprint

首先滿足β分布的概率密度函數為 ，其中O3（l-x）²。

（1）選擇函數g（y），這里選擇g（y）=1，0≤y

（2）找a，使得對于所有的x，均有 ，這里 ，為了方便，取a=3。

（3）生成y～U（O，1），U～U（O，1），并且判斷U是否大于20Y³（1-Y）²，如果成立Y則為本次抽樣結果，否則重新生成y和U，直至滿足條件為止。

2 任務邏輯關系轉換和進度推進仿真算法

在網絡計劃技術中，通常對圖的研究都僅限于FS型，包括各種經典的圖論算法，也都是把前后節點之間的關系當作FS型來處理。而在實際的項目管理中，前驅任務和后繼任務之間的邏輯關系一共有四種，分別是：

①Finish-to-Start（FS）：如圖1，前輩節點必須先結束，后繼結點才能夠開始。

② Start-to-Start（SS）：如圖2，前輩節點必須先開始，后繼結點才能夠開始。以修路為例，雖然可以一邊挖路一邊鋪瀝青，但是必須要先開始挖路再開始鋪瀝青。

③Finish-to-Finish（FF）：如圖3，前輩節點必須先結束，后繼結點才能夠結束。以鋪線為例，任務一往一棟樓中鋪線，任務二是檢查樓中鋪的線，那么必須等到鋪線完成后，檢查工作才可能停止。

④Start-to- Finish（SF）：如圖4，前輩節點必須先開始，后繼結點才能夠結束。還是以修房子為例，假設修房子必須用到材料A，那么直到材料A送達前，修房子都不可能結束。

基于傳統CPM算法的啟發，本文設計了兼容這四種任務邏輯關系的進度推進仿真算法。

首先，對算法中涉及到的類型進行定義，用一個五元組Task（distri，per， prog，expS，expE，accS，accE）來表示項目中的任務。

其中，distri屬性和per屬性屬于任務的固有屬性，distri屬性代表Task的分布類型，比如三角分布、正態分布和β分布；per屬性代表的是任務的工時。而后面五個屬性是為了在仿真算法中記錄中間結果添加的屬性，其中prog屬性代表仿真過程中當前任務的進度，初始值為0，隨著時間的推進，prog不斷變大，當prog的值等于任務的工時per時，該任務完成（但還不一定結束，還需要參考accE屬性）；expS屬性代表的是任務開始期望數，屬性accS代表的是任務的當前開始期望數，也就是當accS的值等于expS值時，任務可以開始；同理定義expE為任務結束期望數，而accE代表任務的當前結束期望數，當任務的當前結束期望數達到expE后，任務才可以結束。

接著用一個三元組Link（preTask，sucTask，type）來表示任務之間的邏輯關系，其中preTask屬性代表的是該關系連接的前驅Task，而sucTask屬性代表的是與之相連的后繼Task，屬性type則代表了該關系的邏輯類型。

算法思路：對所有的Link進行了遍歷，如果Link是FS或者SS類型，因為前驅任務的開始或者結束才會導致后繼任務的開始，所以后繼任務的開始期望數需要增加。同理如果Link的類型是FF或者SF型，那么需要增加后繼任務的結束期望數。核心思想是根據任務的開始期望數和結束期望數來判斷任務的開始和結束。算法采用了模擬的思想，即每次將所有任務向前推進一定的時間t_min（也就是找出那些距離完成時間最短的任務，t_min為它們的總工時減去當前進度），然后將這些任務的prog屬性加上t_min代表時間向前推進。

本文對Task定義了三種狀態，分別用三個集合加以表示，TR為初始任務的集合，包含的是還未開始的任務，初始為所有的任務集合。TP為進行中任務的集合，當任務的當前開始期望數達標后，認為任務可以開始，這時將任務從TR移動到TP中，代表任務開始。TF為已經結束任務的集合，當任務可以結束時，將任務移動至該集合。

在算法中，每循環一次就相當于一次時間的推進，且在循環中，算法會檢查和修改任務的狀態。其中，時間的推進用prog屬性來表示，通過從零增加prog的值到其工時，代表任務從開始到結束。而檢查任務是否能夠開始則通過判斷任務的當前開始期望數accS是否等于其開始期望數expS，檢查任務是否能夠結束則通過判斷任務的當前結束期望數accE是否等于其結束期望數expE。每當一個任務開始的時候，都需要對其后繼任務進行修改，如果它們之間的關系為SS型，則將后繼任務的accS屬性加1，如果它們之間的關系為SF型，則將后繼任務的accE屬性加1。同理每當一個任務結束的時候，需要對其后繼任務進行更新，如果它們之間的關系為FS型，則將后繼任務的accS屬性加1，如果它們之間的關系為FF型，則將后繼任務的accE屬性加1。

3 基于全拓撲排序的資源沖突解決策略

在考慮資源的情況下，任務執行的邏輯順序不一定就是任務執行的實際順序，關鍵任務工時的和也并非一定等于總工期。因此需要對第2節中的進度推進仿真算法進行改進。由于考慮資源的沖突，此時關鍵路徑不再是唯一制約進度的因素，非關鍵路徑上的任務也可以由于資源缺乏而拖延總工期。跟關鍵鏈法不同，本文的焦點是放在總工期的計算上，而上述算法也是拋棄了原來關鍵路徑的思想，以模擬的角度來考慮問題，以最小任務工時為單位，每次計算往前推進時間。但是，本法與關鍵鏈的思想并不矛盾，同樣可以往關鍵任務和非關鍵任務兩端加上緩沖時間更精確的為項目管理者提供進度規劃方面的建議，本文算法相當于為關鍵鏈提供了一個可行的拉動式進度計劃方案。

當調用進度推進仿真算法時可以發現，資源沖突的問題其實可以等價于任務優先級的問題，即有多個任務并行時，先將資源優先分配給哪個任務，擁有資源的任務可以隨著時間的推進而推進，而缺少資源的任務雖然在任務進行集合Tp中，但是卻不往前推進時間（即每次prog屬性不變）。因此問題被等價到了任務的優先級上，一般來說，在設置任務屬性的時候，也會一起設置任務的優先級，而對于設置了相同優先級的任務，可以通過枚舉的方式，進而運行進度推進仿真算法。具體的步驟是：

（1）首先求出任務網絡圖所有的拓撲排序序列，每一個序列就相當于一種潛在的任務優先級序列，通過回溯來找出所有拓撲排序序列的算法。

（2）對上述求得的序列進行優化，因為如果任務數目較多且任務邏輯關系復雜，全拓撲排序的結果可能非常大，甚至達到百萬的數量級，使得實際程序的運行效率低下。不過所幸實際中任務之間往往存在著各種約束，通過這些約束就能夠去除絕大部分的無用序列，從而使程序的效率得到保障。

4 進度更改算法

進度更改這里主要指的進行進度的壓縮，假設平均總工期為K，用戶設置的目標工期為M，若M

如果考慮任務的權重便可以照葫蘆畫瓢進行算法設計，假設當前有t₁，t₂，¨，t_n那個任務，每個任務的權重分別為P₁，P₂，…，P_n，其中關鍵任務為t_c1，t_c2，…，t_cn，它們的權重為P_c1，P_c2，¨，，p_cn，這里權重代表的是可壓縮性，即權重的數值越大，任務的可壓縮性越強。

在進度壓縮的過程中，重點應該放在關鍵任務上，只需要對它們進行壓縮，但是需要注意壓縮過程關鍵路徑不應該發生改變，那么當在壓縮關鍵任務時，只需要保證關鍵任務的工時即使被壓縮后也應該是同時刻并行任務中最大的即可，所以根據上述一樣的思路，只是在壓縮過程中按照每個任務的權重來進行壓縮，而顯然，因為只考慮關鍵任務，對于t_ci，應該將工時壓縮到 ，此時若關鍵

任務工時小于非關鍵任務的工時，那么強制將非關鍵任務的工時減小到關鍵任務的工時，可見只需要稍稍修改ShrinkHours算法，將壓縮任務時的語句改為按照權重來進行壓縮即可。

最后在仿真完成結束后，需要根據已經保存的仿真中間信息，對項目的進度風險進行預估。假設進行了N次仿真，那么就記錄了N個工期，根據大數定理，當N足夠大時（一般取N為2000到10000次），便可以用這N個樣本值來代替實際值。項目風險同樣通過這N個樣本值來進行計算，本文主要通過總工期區間統計圖和進度風險圖來對風險進行評估。其中，總工期區間統計圖表示的是N個總工期樣本值的分布情況，等價于之前設置的每個任務工時服從分布之和，也就是它們的組合分布，而該分布的期望則代表了最可能出現的總工期。進度風險圖表示的是在不同總工期約束下，項目完成的風險（即失敗率）。對于在工期M下的進度風險，計算公式為 。也就是統計總工期小于等于M的個數，再用1減去其占總個數N的比例。

5 結論

由于現代項目的大型化和項目復雜性的不斷增加，如何對項目的進度進行正確的預測和合理的規劃已經受到越來越多的關注，傳統的CPM/PERT方法已經難以滿足人們的需要。本文對現有的進度評估技術進行了改進，加入了對四種任務邏輯關系的支持，并給出了資源沖突時的解決策略，設計并實現了一個面向復雜項目的進度風險評估方法，不僅支持多種隨機變量的抽樣，還能夠給出工期優化策略，旨在幫助項目決策者根據仿真結果識別關鍵任務，以此來制定合理的工期計劃。