黃永康，嚴(yán)　凌

(上海理工大學(xué)管理學(xué)院，上海200093)

?

改進(jìn)的隨機(jī)PERT下尋找關(guān)鍵路徑的新方法

黃永康，嚴(yán)凌

(上海理工大學(xué)管理學(xué)院，上海200093)

[摘要]改進(jìn)了隨機(jī)PERT下尋找關(guān)鍵路徑的方法.定義了隨機(jī)路徑時間變量的比較原則并據(jù)此確定概率關(guān)鍵路徑；利用關(guān)于正態(tài)分布函數(shù)的不等式能對聯(lián)合概率高精度估計的特性驗(yàn)證了概率關(guān)鍵指數(shù)較小時的概率關(guān)鍵路徑的可信度；最后，實(shí)例闡明了隨機(jī)關(guān)鍵路徑方法.

[關(guān)鍵詞]關(guān)鍵路徑; 概率關(guān)鍵路徑; PERT; 概率關(guān)鍵指數(shù)

1引言

PERT(計劃評審技術(shù))是利用網(wǎng)絡(luò)分析制定計劃以及對計劃給以評價，它能夠合理的安排人財物等資源，是現(xiàn)代項(xiàng)目管理的重要手段和技術(shù)[1].對于完成時間的不確定性或者隨機(jī)性，早期學(xué)者們提出了用分布函數(shù)來研究活動完成時間并給出一些數(shù)學(xué)期望和方差的計算方法[2,3],這開啟人們研究PERT的新思路.

概括起來有如下兩種方式：其一，就是基于期望值和方差的方法把活動完成時間的隨機(jī)性轉(zhuǎn)化為確定性.自Beta分布假設(shè)以來眾多研究對這種分布的性質(zhì)在的網(wǎng)絡(luò)分析上的應(yīng)用性質(zhì)有較多的深入的研究[4-6]；但也有很多學(xué)者對這簡單的便于理解應(yīng)用的分布的假設(shè)提出質(zhì)疑[7,8]，是否有其他分布函數(shù)更實(shí)用.因此，在總結(jié)以往研究理論成果可以給予如下三個易見的概率分的概括：基于Beta分布下，完成時間由最可能、最樂觀、最悲觀三個時間可以確定；基于三角分布下，可由三點(diǎn)時間唯一確定；而在Gamma分布，其時間范圍沒有時間限制；這些分布都可以通過改變Beta分布函數(shù)的參數(shù)實(shí)現(xiàn)，同時，Beta分布函數(shù)的右偏性質(zhì)與項(xiàng)目工程完成時間的實(shí)際吻合，因此多采用Beta分布將不確定的時間轉(zhuǎn)化為單一確定的時間以確定關(guān)鍵路徑.其二，計算完成時間準(zhǔn)確的概率分布函數(shù).Dolin和Sirvance(1990)在極端分布上做出了努力[9]，F(xiàn)atemi和Hashemin(1999)提出了轉(zhuǎn)化方法簡化多元重積分[10].但精確地分布函數(shù)因受到網(wǎng)絡(luò)中活動的數(shù)目、活動的概率分布及活動間的相互關(guān)系等因素的影響，這些都涉及較為嚴(yán)格的數(shù)學(xué)計算這給應(yīng)用帶來很大不變.

本文在總結(jié)以往研究的基礎(chǔ)上，旨在改進(jìn)在隨機(jī)性下尋找關(guān)鍵路徑的方法，探索正態(tài)分布在關(guān)鍵路徑的選擇中的應(yīng)用，同時利用三個不等式能夠高精度的估算聯(lián)合概率的特性驗(yàn)證在概率關(guān)鍵指數(shù)較小時選擇概率關(guān)鍵路徑的可信度.

2模型建立

2.1　模型假設(shè)

PERT下的工業(yè)項(xiàng)目大多數(shù)都是繁雜多步驟作業(yè)[11].在考慮到各個節(jié)點(diǎn)之間有眾多作業(yè)，作業(yè)間的相互關(guān)聯(lián)性，每個作業(yè)的完成時間的分布函數(shù)不可俱知的情況下，依據(jù)中心極限定理和正態(tài)分布的良好的性質(zhì)，有如下假設(shè)：

(i) 活動完成時間長度服從正態(tài)分布；

(ii) 活動時間是相互獨(dú)立的隨機(jī)變量.

2.2　理論模型

在實(shí)數(shù)理論中有關(guān)序數(shù)的理論可知:對?x,y∈,max{x,y}必為其中之一，不會出現(xiàn)第三個數(shù)字.然而，隨機(jī)過程中，x,y都屬于隨機(jī)變量時，max{x,y}一般卻不會是x,y二者中的任一個，通常是會出現(xiàn)第三個隨機(jī)變量的.這一理論對于非確定性活動完成時間的研究是重要的，特別是在多維正態(tài)分布的前提下就更顯得很有價值.故為得到一個活動完成時間的估計值，在隨機(jī)不確定的活動時間集上我們重新定義序論.

假定活動完成時間集Ψ={α1,…,αk}，以隨機(jī)長度τ(αK)表示活動αk.

由多維正態(tài)分布的性質(zhì)[12,13]可得：以(X,Y)表示二元正態(tài)隨機(jī)向量，μ=(μ1,μ2)′表示其期望向量，其協(xié)方差矩陣為

在|r|<1時，隨機(jī)變量Z=X-Y的期望值為μ1-μ2,那么

假定Φ(x)是標(biāo)準(zhǔn)正態(tài)分布的分布函數(shù)，可以得到如下等式：

(1)

μ1≥μ2.

(2)

據(jù)定義2，可如下驗(yàn)證其滿足序列的定義：

非對稱性：若

同時出現(xiàn)，也就是說αK,αS有相同的期望值和方差.因此，它們有同一個正態(tài)分布，故它們是非對稱的.

傳遞性：根據(jù)式子(1)，(2)是容易驗(yàn)證的.

因此，這樣確定的一個隨機(jī)性序列是滿足自反性，非對稱性及傳遞性的.故根據(jù)定義2確定的一個完成時間集{τ(αK),…,τ(αS)},規(guī)定以符號“”標(biāo)明序列次序，如τ(αK)τ(αS).

2.3　模型驗(yàn)證

一般地，依據(jù)定義2可以方便的尋找到概率關(guān)鍵路徑，但是當(dāng)概率關(guān)鍵指數(shù)等于或者略微大于0.5下的情況，人們往往對所確定的概率關(guān)鍵路徑是懷疑和不自信的.下面基于不等式給予證明，依據(jù)定義2尋找到的關(guān)鍵路徑仍是自信的.

為證明不等式給出一個簡化的積分公式[14]：

(3)

證令F(K)=Φ(x,y；kr),那么

那么

(4)

以z=kr代入(4)，得

當(dāng)0

所以

同理可有如下不等式

實(shí)際上，Monhor(2010)通過數(shù)值運(yùn)算證明了以上三個不等式對聯(lián)合概率的真實(shí)值估計可得到一個高度和真實(shí)值相近的近似值[15],這將對下面條件概率是有用的.

P(X≥μ1+ε|X≤Y)=1-P(X≤μ1+ε|X≤Y).

(5)

(6)

那么

(7)

因?yàn)?/p>

所以P(X≥μ1+ε|X≤Y)<0.5.故在確定概率關(guān)鍵路徑Y(jié)下，錯誤的選擇X的概率是遠(yuǎn)小于0.5的，這意味著犯錯的概率是遠(yuǎn)小于選擇正確的概率，故Y是概率關(guān)鍵路徑.所以，定義2對尋找到概率關(guān)鍵路徑是可以自信的.

3算例

節(jié)點(diǎn)集為{1,2,3,4,5},兩點(diǎn)間路徑時間的分布分別為

X12~N(6，4)，X25~N(18，5)，X23~N(9，9)，X13~N(5，3)，

X24~N(19，27.4)，X45~N(5，4)，X34~N(9，9)，

所以繪制如圖1所示的它們的網(wǎng)絡(luò)圖.

圖1　某網(wǎng)絡(luò)計劃圖

3.1　模型的應(yīng)用求解

根據(jù)假設(shè)可以得到如表1所示的所有路徑及路徑時間表.

表1　路徑及其路徑時間

由定義2，可以得到此路徑序列為

X1?X2?X3?X4.

(8)

因此，路徑1→2→4→5就是概率關(guān)鍵路徑且P(x4≤30)=0.5.也就是說有50%的機(jī)會以30個單位時間完成計劃.對于0.5的概率,這對于區(qū)間估計、假設(shè)檢驗(yàn)等是小概率，但是因項(xiàng)目在實(shí)際運(yùn)作中的不可重復(fù)性因此得到的數(shù)據(jù)和經(jīng)驗(yàn)是很少的并且還有很多的隨機(jī)性等等，這些原因決定在運(yùn)營過程中很難有十足的把握也就是大的概率值，所以在項(xiàng)目管理中0.5的概率值仍然還有相當(dāng)?shù)膽?yīng)用價值.

如果把計劃完成時間調(diào)整為31個單位時間，那么

P(X4≤31)=0.568.

(9)

同理

P(X4≤32)=0.633，

(10)

P(X4≤33)=0.692.

(11)

可以看到當(dāng)完成時間調(diào)整為33的時候就有近0.7的概率確定這條概率路徑，這一概率值足以讓項(xiàng)目經(jīng)理自信運(yùn)營.同時，這也體現(xiàn)了模型的靈活性，項(xiàng)目經(jīng)理在計劃完成時間的選擇上有一定的空間.

3.2　 進(jìn)一步討論

以上是根據(jù)定義2求得的概率關(guān)鍵路徑，不過在概率關(guān)鍵指數(shù)較小的情形出現(xiàn)下，我們往往要進(jìn)一步驗(yàn)證，所以可以依據(jù)式子(7)直接驗(yàn)證.

根據(jù)公式(1)和聯(lián)合概率分布性質(zhì)易得

P(X3≤X4)=0.560，

(12)

P(X2≤X3)=0.813.

(13)

由定義2知，X2相比X3有接近1的概率不是關(guān)鍵路徑，而X3相比X4據(jù)定義知不是關(guān)鍵路徑，但概率關(guān)鍵指數(shù)也只有0.56的概率，因此，我們可以驗(yàn)證在概率關(guān)鍵指數(shù)較小時路徑.

根據(jù)式子(7)可知，在X4是概率關(guān)鍵路徑下錯誤選擇X3概率是

P(X3≥30|X3≤X4)=1-P(X3≤30|X3≤X4)≤0.148.

(14)

因此，在求得概率關(guān)鍵路徑下錯誤的選擇的概率X3僅有0.148，當(dāng)然,項(xiàng)目經(jīng)理對所選擇的關(guān)鍵路徑有足夠的自信.

4結(jié)論

隨機(jī)關(guān)鍵路徑法是確定型關(guān)鍵路徑方法的一個推廣，它相比以往CPM嚴(yán)重依賴多個估計值，在尋找概率關(guān)鍵路徑上有改進(jìn).此方法根據(jù)每個活動的分布特征值確定出關(guān)鍵路徑，而且在項(xiàng)目完成時間選擇上也有更大的靈活性.此外，由于正態(tài)分布函數(shù)的良好性質(zhì)使得確定關(guān)鍵路徑時使用到的聯(lián)合概率分布函數(shù)的應(yīng)用更為方便，驗(yàn)證關(guān)鍵路徑也更加的方便.最后，不等式對聯(lián)合概率的估計有著良好的精度這也利于應(yīng)用其驗(yàn)證所選擇的概率關(guān)鍵路徑的可信度.

[參考文獻(xiàn)]

[1]Maccrimmon K R, Ryavec C A. PERT假設(shè)的一個分析研究[J].運(yùn)籌學(xué)，1964(12):6-17.

[2]Malcolm D G, Roseboom J H, Clark C E, Fazar.網(wǎng)絡(luò)評審計劃應(yīng)用[J].運(yùn)籌學(xué),1959,7(5):646-669.

[3]Martin J.一個有向無環(huán)圖的時間分布[J].運(yùn)籌學(xué),1965,13:46-66.

[4]Sasieni M W.一個PERT時間的解釋[J].管理科學(xué)，1986,32:1652-1653.

[5]Littlefield T K, Randolph P H.有關(guān)PERT時間問題的回答[J].管理科學(xué),1993,39:1086—91.

[6]Gallagher C A.一個PERT假設(shè)的解釋[J].管理科學(xué),1987,33:1360.

[7]Charles G A.一個PERT假設(shè)的的解釋的回答[J].管理科學(xué)，1987,33(10).

[8]Cheung T Y.最大網(wǎng)絡(luò)流問題的八種方法的數(shù)值模擬比較[J].數(shù)學(xué)軟件,1980,6(1):1-16.

[9]Odin B, Sirvance M.隨機(jī)網(wǎng)絡(luò)和極值分布[J].計算機(jī)與運(yùn)籌學(xué)，1990,17(4):397-409.

[10]Fatemi G S M T, Hashemin SS.有關(guān)隨機(jī)網(wǎng)絡(luò)的一個新的分析算法和高斯積分方法[J].歐洲運(yùn)籌學(xué)，1999,114:610-625.

[11]曹光明,白思俊. 國外PERT/CPM網(wǎng)絡(luò)計劃技術(shù)發(fā)展的三個方面[J].系統(tǒng)工程理論與實(shí)踐，1993,3.

[12]茆詩松，程依鳴，濮曉龍.概率論與數(shù)理統(tǒng)計教程[M].北京：高等教育出版社,2004.

[13]Strom A, Peter B.經(jīng)濟(jì)學(xué)家的數(shù)學(xué)手冊[M].上海：復(fù)旦大學(xué)出版社, 2001.

[14]Plackett RL.多維正態(tài)分布降維公式[J].Biomerika,1954,41:351-360.

[15]Monhor D.一個新的隨機(jī)PERT下關(guān)鍵路徑的概率方法[J].中歐運(yùn)籌學(xué),2011,19:615-633.

An Improved New Method of Searching the

Critical Path in Stochastic PERT

HUANGYong-kang，YANLing

(Business School, University of Shanghai for Science and Technology, Shanghai 200093, China)

Abstract:This paper improves the method of searching the critical path in stochastic PERT. We defined the comparison principle of the time variable of random path and used the principle todetermine probabilistically critical path; we also used the inequality characteristics of the normal distribution function which can estimate the joint probability in high precision to verify the credibility in the case of having small probabilistic criticality index; finally, an illustrative example to search the critical path is presented.

Key words:critical path； probabilistically critical path； PERT ； probabilistic criticality index

[基金項(xiàng)目]上海市教委科研創(chuàng)新重點(diǎn)項(xiàng)目(12ZZ137)

[收稿日期]2014-07-28

[中圖分類號]TU 723.3

[文獻(xiàn)標(biāo)識碼]B

[文章編號]1672-1454(2015)02-0014-06