Excel規劃求解在關鍵路線確定中的應用

[摘 要] 本文基于關鍵路線法的基本原理，構建了利用Excel規劃求解完成相應功能的數據結構，實現了規劃求解的計算和模型應用的拓展分析，表明將Excel規劃求解用于關鍵路線確定是可行、可靠、可信的。

[關鍵詞] Excel;規劃求解;關鍵路線

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2010 . 09 . 031

[中圖分類號]F224.33 [文獻標識碼]A [文章編號]1673 - 0194(2010)09- 0082 - 02

1引言

關鍵路線法(Critical Path Method，CPM)是一種通過分析哪個活動序列(哪條路線)進度安排的靈活性(總時差最少)來預測項目工期的網絡分析技術[1]。具體而言，該方法依賴于項目網絡圖和活動持續時間估計，通過正推法計算活動的最早時間，通過逆推法計算活動的最遲時間，在此基礎上確定關鍵路線，并對關鍵路線進行調整和優化，從而使項目工期最短，使項目進度計劃最優。

關鍵路線法的關鍵是確定項目網絡圖的關鍵路線，這一工作需要依賴于活動清單、項目網絡圖及活動持續時間估計等。對此，既可以借助于項目管理軟件完成關鍵路線的計算，也可以采用手工計算等。關鍵路線法已廣泛用于日常的管理活動中，如產品開發、項目管理、資源調度等[2-4]。

關鍵路線法實際上有兩重意義:一是確定關鍵路線，這是關鍵路線法的基礎和核心;二是項目優化。本文專門討論利用Excel規劃求解方法進行關鍵路線的確定。

2Excel規劃求解數據結構及計算

通常，在項目網絡圖中存在著緊前工序和緊后工序，所以項目網絡圖一般是一個有向網絡圖。假設現有一個項目網絡圖如圖1所示，每個工序改稱為路徑，工序的箭頭事項改稱為終點，工序的箭尾事項改稱為始點，整個工程的始點為A結點，工程的終點為Y結點;這個工程共有25個結點(A～H)，60個工序。關鍵線路法就是在這個工程項目網絡圖中找出關鍵路線，也就是從A結點到Y結點的所有線路中找出總長度最小的一條線路。

按照規劃求解的要求構造所需要的Excel工作表，如圖2所示。

單元格A2:C61為各路徑的始點、終點及長度(如A2:C2為A、B、6，即A到B路徑長為6;余類推)。單元格D2:D61為可變單元格，取值0或1，其意義就是相應路徑選中或未選中，其取值將作為規劃求解的約束之一;單元格D62為D2:D61之和，表示得到最優解時從A結點到Y結點所經過的路徑個數。單元格E2:E61為相應可變單元格與路徑長度的乘積，E62為E2:E61之和，即得到最優解時從A結點到Y結點的總路徑長度，作為目標單元格，取“最小”，這是將來進行規劃求解時的目標要求。

某結點凈流出量等于該結點流出量與該結點流入量之差;結點流入量就是各路徑終點為該結點的路徑數，結點流出量就是各路徑始點為該結點的路徑數。在實際找尋關鍵路線時，有些路徑被選中，有些路徑沒有被選中，只有被選中的路徑才可以計量其對相應結點的流入量、流出量。以結點C為例，有3條流入路徑AC、BC、DC，3條流出路徑CF、CG、CH，如BC、AC、CG被選中，則其流入量為2，流出量為1，凈流出量為-1。由于從A結點開始、Y結點結束、中間結點不作停留，所以A結點的凈流出量要等于1，Y結點的凈流出量要等于 -1，其余結點的凈流出量要等于0。關于各結點的凈流出量(單元格I2:I26)的要求都將作為求解約束。規劃求解得出的關鍵路線為A-B-E-J-K-L-M-T-S-X-W-Y，共11個工序，總長度為52。

3規劃求解用于關鍵路線確定的應用拓展

在原先的項目網絡圖基礎上，如果要規定從A結點到Y結點的所有線路中找尋出不包括某條路徑且路線最長的線路，則在上面方法的基礎上增加一個約束就可以了。如要求必須不包括路徑AB，在進行規劃求解時相應增加的一個約束就是:D2=0。由此求出的關鍵路線為:A-C-H-G-L-M-T-S-X-W-Y，總長度46。如同時規定AB、TS均不能選擇，就增加兩個約束D2=0和D53=0，由此求出的關鍵路線為:A-C-H-G-L-Q-R-S-X-W-Y，總長度41。

在原先的項目網絡圖基礎上，如果規定從A結點到Y結點的所有線路中找尋出必須包括某條路徑且路線最長的線路，則也是增加一個約束就可以了。如要求必須包括路徑RS，在進行規劃求解時相應增加的一個約束就是:D48=1，由此求出的關鍵路線為:A-B-E-J-K-L-Q-R-S-X-W-Y，總長度47。如同時規定AC、RS均選擇，就增加兩個約束D3=1和D48=1，由此求出的關鍵路線為:A-C-H-G-L-M-R-S-X-W-Y，總長度41。

在原先的項目網絡圖基礎上，如果規定關鍵路線的起始點不是A結點，而是另外的結點，則只需在約束中稍加改變，取消原先A結點凈流出量等于1，增加作為新起始點的凈流出量等于1即可。如起始點改變為M點(Y仍為終點)，則在約束中設置I2:I13=0、I15:I25=0、I14=1，由此求出的關鍵路線為M-T-S-X-W-Y，總長度26。如果同時改變關鍵路線的始點和終點，只需重新設置對有關結點凈流出量的約束，即始點、終點和其他結點的凈流出量要分別等于1、-1和0即可。如以結點C作始點、結點R作終點，改變相應約束后的計算結果即從結點C到結點R的關鍵路線為C-H-O-N-M-R，總長度19。

實際上，還可以將上面討論的內容綜合考慮。如既改變始點、終點，又要規定某幾條路徑必須包括、某幾條路徑不包括在內，可以按照上面的修改約束方式進行設置后即可進行求解。如求始點為B、終點為V、不能包括路徑RV、必須包括EF，修改約束設置后規劃求解的結果為B-E-F-G-L-M-T-S-V，總長度32。

通過以上分析可以看出，Excel規劃求解用于關鍵路線的確定是成功的，而且具有原理易懂、操作方便、快捷易行、結果可靠、擴展性強等特點。

主要參考文獻

[1] 李德，錢頌迪. 運籌學[M]. 北京:清華大學出版社，1982:328-349.

[2] 閻樹田，張潔，等. 利用關鍵路徑法對產品并行開發過程模型進行分析與優化[J]. 現代制造工程，2008(11):47-49.

[3] 羅實. 關鍵路徑法在項目管理中的應用[J]. 中小企業管理與科技，2007(6):67.

[4] 賈宗璞，高鐵梁，等. 基于p2p思想和關鍵路徑的網格資源調度[J]. 計算機測量與控制，2008，16(3):376-378.