Excel規(guī)劃求解在關(guān)鍵路線確定中的應(yīng)用

[摘 要] 本文基于關(guān)鍵路線法的基本原理，構(gòu)建了利用Excel規(guī)劃求解完成相應(yīng)功能的數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)了規(guī)劃求解的計算和模型應(yīng)用的拓展分析，表明將Excel規(guī)劃求解用于關(guān)鍵路線確定是可行、可靠、可信的。

[關(guān)鍵詞] Excel;規(guī)劃求解;關(guān)鍵路線

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

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

1引言

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

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

關(guān)鍵路線法實際上有兩重意義:一是確定關(guān)鍵路線，這是關(guān)鍵路線法的基礎(chǔ)和核心;二是項目優(yōu)化。本文專門討論利用Excel規(guī)劃求解方法進(jìn)行關(guān)鍵路線的確定。

2Excel規(guī)劃求解數(shù)據(jù)結(jié)構(gòu)及計算

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

按照規(guī)劃求解的要求構(gòu)造所需要的Excel工作表，如圖2所示。

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

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

3規(guī)劃求解用于關(guān)鍵路線確定的應(yīng)用拓展

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

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

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

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

通過以上分析可以看出，Excel規(guī)劃求解用于關(guān)鍵路線的確定是成功的，而且具有原理易懂、操作方便、快捷易行、結(jié)果可靠、擴(kuò)展性強(qiáng)等特點(diǎn)。

主要參考文獻(xiàn)

[1] 李德，錢頌迪. 運(yùn)籌學(xué)[M]. 北京:清華大學(xué)出版社，1982:328-349.

[2] 閻樹田，張潔，等. 利用關(guān)鍵路徑法對產(chǎn)品并行開發(fā)過程模型進(jìn)行分析與優(yōu)化[J]. 現(xiàn)代制造工程，2008(11):47-49.

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

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