基于Chebyshev譜方法的PERT網絡關鍵活動分析

0 引言

項目評審技術[1]（PERT）、關鍵路徑法[2]（CPM）、圖形評審技術[3］（GERT）和風險評估與評審技術[4]（VERT）都是網絡計劃技術中的主要方法，其共同目標是高質量、快速地實現項目管理要求。其中，關于PERT的研究成果涉及諸多方面，包括關鍵活動、關鍵度指數、關鍵路徑、敏感性等[5]。一般來說，研究人員通常對網絡進行分析獲得項目中的關鍵活動，以確定關鍵節點，從而控制和管理項目[6。目前，針對PERT網絡關鍵活動、關鍵度指數的研究比較常用的方法是蒙特卡洛（MonteCarlo，MC）模擬方法，這是一種隨機模擬方法[]。隨著計算機的快速發展，它已被廣泛應用于各個領域的仿真模擬[7-10]。基于現有的模型（如期望和方差），確定活動持續時間的隨機分布類型和相應的分布參數，以獲得蒙特卡洛模擬的概率模型[11]。 Van^[12] 提出使用 MC 抽樣方法來分析PERT網絡。Martin[13]描述了PERT網絡中的關鍵路徑指數和關鍵活動指數的概念。Sigal等[14]采用MC抽樣方法計算了PERT網絡的關鍵路徑指數和關鍵活動指數。Soroush[15]在PERT網絡中提出了最關鍵路徑（MostCriticalPath，MCP）的概念，并將MCP定義為持續時間最長路徑中概率最高的路徑。Fatemi等[16]研究了PERT網絡中與路徑關鍵度、活動關鍵度和路徑概率相關的問題。Zhang等[17]討論了PERT網絡中非關鍵活動的敏感性。Wang等[18]提出了一種基于MC的抽樣方法，確定了PERT網絡中的關鍵路徑和最關鍵活動。根據PERT的特點，它通常用于分析具有多個不確定和不可預測因素的復雜項目[19]。隨著計算機技術的不斷發展，研究人員主要使用MC模擬完成PERT網絡的近似，并為復雜項目網絡中的每個隨機變量建立相應的概率模型[20]。同時，通過對概率模型進行抽樣，計算每個活動所需時間和項目完成時間，還可以利用MC重復模擬以獲得多個樣本，進一步確定項目的預期持續時間和方差，以及項目計劃持續時間的完成概率。然而，MC模擬可以快速地分析簡單的PERT網絡，但針對復雜網絡卻暴露出一些局限性。例如，MC模擬僅適用于分析小規模網絡圖。因此，隨著網絡復雜性不斷提高、網絡節點數量增加和關鍵路徑數量指數增長，MC仿真方法逐漸不再適用。

Chebyshev譜方法是一種用于工程和頻域的數學分析技術。它可以將信號或函數分解為一組基本頻率分量，以更好地理解和分析信號或函數的頻率特性。因此，本文針對大型復雜PERT網絡圖，提出一種基于Chebyshev譜方法的網絡節點關鍵度指數分析方法，并得到網絡節點的關鍵度指數、節點關鍵度排序及網絡最關鍵路徑。本文將Chebyshev多項式與函數相乘，并對整個區間進行積分，將函數分解為一系列譜分量，利用Cheby-shev多項式在有界區間上實現函數的近似。將函數分解為Chebyshev多項式的線性組合后，可以計算每個頻率分量的幅度和相位，以了解函數中不同頻率分量的貢獻及其在時域中的時間信息。與傳統的MC仿真相比，本文提出基于Chebyshev譜方法的PERT網絡節點關鍵度指數計算方法具有顯著的優勢。特別是在大規模和復雜的PERT網絡圖領域，該方法的效率、收斂能力和對資源受限情況的適用性，使其成為項目經理、研究人員尋求優化項目規劃和執行過程的寶貴工具。

1 PERT網絡圖信息構建

1.1 符號描述

通常PERT網絡采用雙代號表示法，假設網絡中共有 Ω_n （ ngt;1 ）個節點，起始節點為節點1，終止節點為節點 n ，網絡中的某項活動用 i-j 表示，i 為活動起始節點， j 為活動終止節點， 1

表示一個PERT網絡， G 為一個有向無環圖，該有序對中 V 是節點集合， E 為鏈接（或邊）的集合。

， v₂ ，…， 表示節點的集合，是一個有限元素集。

表示集合 V 上的任意子集， V?V 表示 V 中元素的有序對集 。

v_j∈Pd （ ?σ_vi） ）表示 v_j 是 v_i 的前置節點。

∈Sc（）表示j是;的后繼節點。

e_i-j 表示活動 i-j 的樂觀估計時間。

l_i-j 表示活動 i-j 的悲觀估計時間。

d_i-j 表示活動 i-j 的平均持續時間。

c_i-j 表示活動 i-j 的正常持續時間。

k_i 表示節點 i 的關鍵度指數。

1. 2 概念定義

1994年Soroush[2I]首次提出最關鍵路線（MostCriticalPath，MCP）的概念，根據Malcolm等22對關鍵活動、關鍵路線和活動關鍵度的定義，本文中PERT網絡相關概念表述如下：

（1）定義1：節點關鍵度指數。其表示某個網絡節點在整個PERT網絡計劃圖中的重要程度，關鍵度指數越大，表示該節點在整個項目中越重要。節點 i 的關鍵度指數用 k_i 表示，關鍵度指數最大的節點為最關鍵節點。

（2）定義2：最關鍵路徑。其表示從起始節點1開始至節點 n 結束的所有路徑中，節點關鍵度指數之和最大的路徑。

1.3 構建圖信息

20世紀50年代末Malcolm等[23]提出經典PERT網絡，它是關鍵路徑法（CriticalPathMeth-od，CPM）的拓展，但二者存在一些差異。CPM通常假設項目活動持續時間是確定的（側重確定性問題）；而PERT則假設活動持續時間是隨機的，通過最樂觀、最悲觀、最可能的估計時間來描述其不確定性（側重不確定問題）。PERT方法中各活動間的邏輯關系明確，但假定某項活動的持續時間為隨機變量，無法給出具體數值。對于時間估計，使用適當的概率分布（譬如三角分布，β 分布等）表示活動時間的隨機性。因此，令 、b 、 ?_m 分別表示某項活動的最樂觀、最悲觀、最可能估計時間，且三者的值可視為隨機概率分布的參數，根據同分布中心極限定理，其頻率趨近于一條正態分布曲線 表示活動持續時間期望， σ²=（ΔbΔ-a）²/36 表示活動持續時間方差。

另外，經典PERT方法有許多假設條件：各活動持續時間服從 β 分布，且相互獨立；對于活動起始節點 i ，用 μ_i 和 σ_i² 表示其不確定性；網絡計劃圖中關鍵路徑上的工序數量足夠大，并能滿足中心極限定理，其他路徑成為關鍵路徑的概率可忽略；網絡計劃中某條路徑的總工期服從正態分布。在以上假設的基礎上確定關鍵路徑，并得到某路徑上項目總工期期望 T_e 和方差 ，公式如下

由上式可知， T_e 越大，路徑越關鍵，當 T_e 為最大值時的路徑為關鍵路徑。若 越小，則該路徑工期期望值的可靠度越高；若 σ_e² 越大，則該路徑工期期望值的可靠度越低，工期不確定性大。根據大數定理，項目工期為正態分布，得到標準偏移值 z ，公式如下

因此， ，其概率密度函數f（T） 為項目計劃工期 T 的完工概率， f（T） 可進一步運用于項目進度計劃制定、資源分配等過程中，公式如下

結合本文，根據PERT網絡計劃的平均持續時間構建圖信息，公式如下

式中， d_i 表示活動 i 的平均持續時間， 、 c_i 分別表示活動 i 的樂觀估計時間、悲觀估計時間和正常持續時間。

2基于Chebyshev 譜方法的 PERT 網絡節點關鍵度指數分析

譜方法采用空間轉換的思想，先將問題的解用正交函數進行譜展開，即可將原始物理空間中的問題等價轉換至譜空間進行求解，求得結果后，再將展開系數轉換至原始物理空間。進行空間轉換的原因在于譜方法具有“無窮階”收斂性，即求解誤差呈指數收斂[25-26]。譜方法通常用來求解微分方程數值解。目前，該方法已廣泛應用于大氣科學、聲學、流體力學等領域[27-30]

活動起始節點 i 的關鍵度指數 k_i 表明若該節點的最早開始時間延遲，則整個網絡的最早完成時間也隨之延遲。因此，一個節點的 k_i 值可通過計算該節點的所有后繼節點的 k 值與該節點到每個后繼節點的松弛時間之和，再除以節點到后繼節點松弛時間的最大值求得，公式如下

其中， E 是PERT網絡中的邊集。每個節點的關鍵度指數 k 的值可以通過求解線性方程求得，公式如下

求解得到 k_i 后，通過 k_i 值判斷每個節點的關鍵度。若 k_i=1 ，則節點 i 為關鍵節點；若 k_ilt;1 ，則節點 i 為非關鍵節點。通過迭代求解上述線性方程組，可使用矩陣乘法進行迭代。設 k^（0）= （204號 （1，1，…，1）^T ，則 k^（i+1）=Mk^（i） ，其中 L，D 是 L 的對角線矩陣， 是 P 的下三角部分，即 P=L+D+U 中的 。不斷迭代求解，直到k^（i+1） 與 k^（i） 之間的差距小于預設精度，即可得到最終的關鍵度指數，公式如下

對鄰接矩陣的譜進行分解，公式如下

式中， A 是由 A 的特征值組成的對角矩陣， 是A 的特征向量矩陣。然后采用譜半徑（鄰接矩陣的最大特征值的模）計算節點的關鍵度指數，公式如下

求得節點 i 的關鍵度指數，公式如下

式中， λ_i 是鄰接矩陣 A 的第 i 個特征值。該式的含義是節點的關鍵度指數與其在鄰接矩陣的特征值中位置有關，特征值離譜半徑越遠，節點的關鍵度指數就越高；當節點的特征值與譜半徑非常接近時，節點的關鍵度指數將會非常高。若某個節點多次出現在鄰接矩陣的特征值中，則在計算該節點的關鍵度指數時，應該將其所有特征值都考慮在內。此外，若譜半徑為零，則所有節點的關鍵度指數都應設置為1。

G 的拉普拉斯矩陣為

L=D-A

式中， A 是圖的鄰接矩陣， 是圖的度矩陣，公式如下

式中， D_ij=0 ， i≠j

定義 L 的特征值為 ，對應的特征向量為 v₁ ， v₂ ，…， v_n 。由于 L 是實對稱矩陣，因此其特征向量是正交的，公式如下

定義每個節點 v_i 的關鍵度指數為 k_i ，公式如下

k_i=max_j=1ⁿ∣v_ij∣

式中， v_ij 表示 v_i 在第 j 個特征向量上的分量，得到k_i 的計算公式，公式如下

由于 k_i 的計算過程涉及 的所有特征向量，因此，需先得到 L 的所有特征向量。采用Cheby-shev譜方法計算 L 的所有特征向量。假設需計算L 的前 k 個特征向量，則需使用 k 階Chebyshev多項式求得 T_k（x） ，公式如下

T_?k（x）=2xT_?k-1（x）-T_?k-2（x）

式中， T₀（x）=1，T₁（x）=x 。通過迭代 L 的特征向量，計算 L 的所有特征向量。假設有一個向量 ，需計算 L 乘以 的結果，可使用Chebyshev多項式展開 ，公式如下

其中， 是 L 的標準化形式，公式如下

由于 的特征值在［－1，1］之間，因此可使用Chebyshev展開 ，公式如下

式中， T_i（x） 是 i 次Chebyshev多項式， x 是 的歸一化特征值，即 2（λ；-λ）-1，c：為系數，公式如下

式中， L_ij 是 的第 i 行第 j 列的元素。展開 后，可以將Chebyshev系數作為特征向量，公式如下

通過 u_i 中的最大值和最小值計算得到歸一化特征值 x_i ，公式如下

求得節點 χ_i 的關鍵度指數，公式如下

k_i=1-x_i

3基于Dijkstra算法的PERT網絡關 鍵路徑分析

Dijkstra算法是一種基于貪心策略的路徑規劃經典算法，基于廣度優選搜索的思想，以起始節點為中心原點進行層層擴展，根據最短路徑長度遞增次序反復進行路徑迭代，直至終止節點停止搜索，得到可行域內的最短路徑。Dijkstra算法在交通、導航、智能停車場等領域應用廣泛，本文采用該算法對PERT網絡節點進行分析。

本文以PERT網絡節點1為起點，以節點 n 為終點，計算從節點1至節點 n 的最短工期時間。具體步驟如下[31-32]：

4案例分析

（1）將PERT有向網絡圖中所有節點劃分為兩個集合，集合 P 表示已訪問的節點集合，集合Q 表示未訪問的節點集合。 d_i 表示當前節點 i 到起始節點1的距離。先將起始節點到任意節點的距離初始為無窮小。

（2）訪問起始節點1，設置 d₁=0 ，并將其起始節點1置于集合 P 內，將起始節點記為當前節點。

（3）在集合 Q 中對當前節點的所有鄰節點進行遍歷，尋找代價最低的節點，并將該節點置于集合 P 內，并檢驗最短路徑是否可松弛。

（4）重復步驟（3），至集合 Q 為空集，完成最短路徑搜索，結束計算。

以G公司運維軟件開發項目為例，分析PERT網絡節點關鍵度指數，尋找網絡最關鍵路徑。G公司運維軟件開發項目網絡活動持續時間估值見表1，G公司運維軟件開發項目網絡計劃圖如圖1所示。

（續）

4.1節點關鍵度指數分析

根據圖1，可得該圖的鄰接矩陣 A 和度矩陣D ，公式如下

而一步求得拉普拉斯矩陣 L ，公式如下

最后，計算每個節點 v_i 的關鍵度指數 k_i ，如下所述。

K =（8.565，8.212，2.818，2.447，3.098，2.070，1.349，0.709，0.316，0.885，0.224，0.761，0.349，0.074，0.304，0.174，0.830，0.730）

4.2最關鍵路徑分析

本文目的是在PERT有向網絡中，根據每個節點的關鍵度指數尋找一條關鍵度指數和最大的路徑，Dijkstra算法是尋找最短路徑的常用算法。因此，在路徑搜索過程中，將訪問節點所花費的代價設置 c_i=1/k_i 。運行Dijkstra 算法，得到關鍵度指數和最大路徑為{1，5，8，10，13，15，18}，對應的關鍵度指數和為14.644。最關鍵路徑示意圖如圖2所示，最關鍵路徑用黑色箭頭加粗標記。即由節點1開始，通過節點5、8、10、13、15，最終到達節點18，該路徑為示例的PERT網絡，從起始節點1開始至節點18結束的所有路徑中，節點關鍵度指數之和最大的路徑。

4.3實驗結論

面對大規模PERT網絡的情況，本文所提方法能夠快速精準地完成PERT網絡節點關鍵度指數和最關鍵路徑的推導，而MC模擬必須重復多次才能實現收斂。然而，在大型項目的總體規劃和推廣過程中，通常需要協調、實施數千項相互依存的活動規劃。因此，活動規模越大，相互依存關系就越復雜，本文所提方法的優越性就越凸顯。

5 結語

本文主要針對網絡計劃圖中的節點進行研究，在大規模和復雜的PERT網絡圖領域，通常涉及許多任務、依賴關系和不確定性，本文創新性提出一種基于Chebyshev譜方法的PERT網絡節點關鍵度指數推導方法，以及基于Dijkstra算法搜索PERT網絡最關鍵路徑的方法。并通過G公司運維軟件開發項目算例分析測試了程序代碼，驗證了所提出方法的可行性和有效性，為項目統籌規劃中的進度管理提供了新的思路。通過上述方法，項目管理人員可以深入了解項目進度、關鍵路徑和資源分配。即使對于非常復雜的項目組，其方法也可以為項自經理和研究人員提供輔助決策，優化項目管理策略，進一步推進項目規劃和執行過程。

然而，本文提出的方法仍有許多問題需要進一步研究。例如，將PERT網絡分析與人工智能、機器學習和大數據分析等其他先進技術和工具相結合，使項目管理更加智能，更好地應對復雜性和不確定性。隨著敏捷項自管理方法的興起，未來的PERT網絡分析工具可能會與敏捷方法集成，以更好地適應頻繁變化的項自環境。隨著實時數據和傳感器技術的發展，其能夠實時監控項自進度和最關鍵路徑，根據實際數據進行調整，實現項目實時動態管理

參考文獻

[1]COTTRELL W D. Simplified program evaluation and review technique（PERT）［J].Journal of Construction Engineering and Management，1999，125（1）：16-22.

[2]HOFMANN P A. Critical path method：an important tool for coordinating clinical care [J].The Joint Commission journal on quality improvement，1993，19（7）：235-246.

[3]ZHOUL，XIE J，GUX，etal.Forecasting return of used productsfor remanufacturingusingGraphical Evaluationand Review Technique（GERT）[J]. International Journal of Production Economics，2016（181）：315-324.

[4]MATTHEISSTH，MOELLERG，KILARJ.Improving industrial readinesswith venture evaluation and review technique（VERT） [J].Interfaces，1982，12（1）：21-26.

[5]ASTARI N M，SUBAGYO A M，KUSNADIK. Perencanaan manajemen proyekdengan metode CPM（Critical Path Method） dan PERT（Program Evaluation and Review Technique）[J]. Konstruksia，2022，13（1）：164-180.

[6」GHOMI S M T F， TEIMOURl E. Path critical index and activity critical index in PERT networks[J].European Journal of Operational Research，2002，141（1）：147-152.

[7]RAYCHAUDHURI S. Introduction to monte carlo simulation [C]//2O08 Winter simulation conference. IEEE，2008.

[8]LIUJ，QI Y，MENG ZY，et al.Self-learning monte carlo method[J].Physical Review B，2017，95（4）：041101.

[9]ZHOU J，AGHILI N，GHALEINI E N，et al.A Monte Carlo simulation approach for effective assessment of flyrock based on intelligent system of neural network [J]. Engineering with Computers，2020（36）：713-723.

[10]MAHDIYAR A，HASANIPANAH M， ARMAGHANI D J， et al. A Monte Carlo technique in safety assessment of slope under seismic condition[J].Engineering with Computers，2017，33 （4）： 807-817.

[11]ZHOUG，ESAKIT，MITANIY，et al.Spatial probabilistic modeling of slope failure using an integrated GIS Monte Carlo simulation approach［J]．Engineering Geology，2O03，68 （3）：373-386.

[12]VANRM.Monte Carlo methods and the PERT problem[J]. Operation Research，1963，11（5）：839-860.

[13]MARTINJJ.Distribution of the time through a directed，acyclic network[J].Operation Research，1965，13（1）：46-66.

[14]SIGAL C E，PRITSKER AB，SOLBERG JJ. The use of cutsets in Monte Carlo analysis of stochastic networks [J].Mathematics and Computers in Simulation，1979，21（4）：376-384.

[15]SOROUSH H M. The most critical path in a PERT network：a heuristic approach［J].European Journal of Operational Research，1994，78（1）：93-105.

[16]FATEMI G S MT，TEIMOURI E.Path critical index and activity critical index in PERT networks [J].European Journal of Operational Research，2002，141（2）：147-152.

[17］ZHANG W，QI JX. Sensitivity analysis on non-critical process in PERTnetwork［J].Technology Economics，2009，28 （12） ： 114-118.

[18]WANG ZF，DINGJY，LIUH，et al. Analysis of critical path and most critical activity in PERT networks based on Monte Carlo method [J].Systems Engineering and Electronics，2012， 34（8）：1646-1651.

[19]CHANG HK，YU W， CHENG S T，et al. The use of a multiplerisk level model to tackle the duration of risk for construction activity[J].KSCE Journal of Civil Engineering，2019（23）： 2397-2408.

[20]WANG RC，OUYANG B，CHU C C. Monte Carlo simulation of project network planning and schedule risk analysis[J]. Computer Simulation，2004（4）：143-147.

[21]SOROUSHH M. The most critical path in a PERT network：a heuristic approach ［J].European Journal of Operational Research，1994，78（1）：93-105.

[22］王卓甫，丁繼勇，劉媛，等．基于MonteCarlo方法的 PERT網絡關鍵路線和最關鍵活動分析［J]．系統工程與 電子技術.2012，34（8），1646-1651.

[23]MALCOLMD G，ROSEBOOM JH.Application of a technique for research and development evaluation [J].opns. Res.1959 （7）：646-669.

[24]MACCRIMMON KR，RYAVEC C A. An analytical studyof the PERT assumptions［J]．Operations Research，1964，12 （1）：16-37.

[25] CANUTO C， HUSSAINI M Y，QUARTERONI A，et al. Spectral methods in fluid dynamics[M].Berlin，German：Spring Verlag，1988.

[26]GOTTLIEB D，ORSZAG S A. Numerical analysis of spectral methods：theory and applications[M].Philadelphia：Society for Industrial，1977.

[27]LI X F. Dynamic modeling and analysis of flexible suspension system based on spectral method [D]. Guangdong University of Technology，2022.

[28］TU H W. Research on efficient underwater acoustic propagation algorithm based on spectral method[D].Changsha：National University of Defense Technology，2021.

[29]TUH，WANG Y，LIU W，et al. A Chebyshev spectral method for normal mode and parabolic equation models in underwater acoustics[J]．Mathematical Problems in Engineering，2020 （5）：7461314.

[30]MURAVSKAYA NP. Spectral methods in physical and chemical measurements [J]. Journal of Physics： Conference Series， 2019，1420（C1）：012005.

[31]RAHAYUDA IG S， SANTIARI NP L Dijkstra and bidirectional Dijkstra ondetermining evacuation routes[J]. Journal of Physics Conference Series Volume，2021，183（1）：12-18.

[32]SAEKYEOL K，TAEHYEOKC，SHINYU K，et al.Sequential graph-based routing algorithm for electrical harnesss，tubes， and hosesina commercial vehicle[J].Journal of Intelligent Manufacturing，2021，32（4）：917-933.PMT

收稿日期：2025-03-11

作者簡介：

張玉婷（通信作者）（1991—），女，博士，工程師，研究方向：聯合作戰體系仿真分析與評估。

楊鏡宇（1971—），男，博士，正高級工程師，博士研究生導師，研究方向：聯合作戰體系仿真分析與評估。