韋利春 高紅慧 王艷娟 王慧 高紅彬

摘要：計劃評審方法（PERT）和關(guān)鍵路線法（CPM）是網(wǎng)絡(luò)分析的重要組成部分，它廣泛地用于系統(tǒng)分析和項目管理。文章基于圖的鄰接矩陣，利用最短路算法，求得關(guān)鍵路線。該關(guān)鍵路線的算法容易理解、掌握，并便于使用Matlab實現(xiàn)。

關(guān)鍵詞：鄰接矩陣；Floyd算法；關(guān)鍵路線；Matlab

中圖分類號：TM744 文獻標(biāo)識碼：A 文章編號：1009-2374（2012）06-0046-02

一、概述

計劃評審方法（PERT）和關(guān)鍵路線法（CPM）是網(wǎng)絡(luò)分析的重要組成部分，它廣泛地用于系統(tǒng)分析和項目管理。計劃評審與關(guān)鍵路線方法是在20世紀(jì)50年代提出并發(fā)展起來的，1956年，美國杜邦公司為了協(xié)調(diào)企業(yè)不同業(yè)務(wù)部門的系統(tǒng)規(guī)劃，提出了關(guān)鍵路線法。1958年，美國海軍武裝部在研制“北極星”導(dǎo)彈計劃時，由于導(dǎo)彈的研制系統(tǒng)過于龐大、復(fù)雜，為找到一種有效的管理方法，設(shè)計了計劃評審方法。由于PERT與CPM既有著相同的目標(biāo)應(yīng)用，又有很多相同的術(shù)語，這兩種方法已合并為一種方法，在國外稱為PERT/CPM，在國內(nèi)稱為統(tǒng)籌方法（Scheduling Method）。

通常的關(guān)鍵路線法較復(fù)雜，較難上機實現(xiàn)。本文提出一種基于最短路算法的關(guān)鍵路線求法，該方法易理解掌握，并易于使用圖的鄰接矩陣上機實現(xiàn)。

二、算法設(shè)計

如果把關(guān)鍵路徑看成是網(wǎng)絡(luò)中從起點到終點的最長路，并且把網(wǎng)絡(luò)看成是一個有向圖，其中是頂點集合，是弧的集合，為鄰接矩陣，這里，，，為弧的權(quán)重。我們就可以利用圖的最短路算法，以求得關(guān)鍵路線。

為了把最長路徑問題轉(zhuǎn)化為最短路徑問題，首先把有向圖轉(zhuǎn)化為另一個有向圖，其中滿足

，，。

這樣我們就可以把中求最長路徑的問題，轉(zhuǎn)化為中求最短路的算法。求最短路的算法有很多，例如有廣度優(yōu)先搜索算法、寬度優(yōu)先搜索算法、Dijkstra標(biāo)號算法和Floyd算法等。由于廣度優(yōu)先搜索算法和寬度優(yōu)先搜索算法較難實現(xiàn)，Dijkstra標(biāo)號算法不適用于負(fù)權(quán)的圖，這樣最佳算法就是使用Floyd算法求中的最短路徑。

Floyd算法是求圖中所有頂點對之間最短路徑的算法。Floyd算法具體如下，對于賦權(quán)圖，記。

Floyd算法是遞推產(chǎn)生一個矩陣序列，其中矩陣的第行第列元素表示從頂點到頂點的路徑上所經(jīng)過的頂點序號不大于的最短路徑長度。

計算時用迭代公式，是迭代次數(shù)，。

最后，當(dāng)時，即是各頂點之間的最短通路值。

三、計算實例

某項目工程由11項作業(yè)組成（分別用代號表示），其計劃完成時間及作業(yè)間相互關(guān)系如表1所示，求作業(yè)的關(guān)鍵路徑。

圖1中的計劃網(wǎng)絡(luò)圖就是一個有向圖，其中頂點集合，為弧的集合，鄰接矩陣。

關(guān)鍵路徑實際上是求從到的最長路徑，為了把最長路徑問題轉(zhuǎn)化為最短路徑問題，為此我們構(gòu)造賦權(quán)有向圖，鄰接矩陣，

其中：

。

這樣我們只要求得賦權(quán)有向圖從到的最短路徑，就等價地得到有向圖中的關(guān)鍵路徑。

利用最短路的Floyd算法，使用Matlab軟件，可以求得關(guān)鍵路徑為1→3→5→6→8，關(guān)鍵路徑的長度為51。

四、結(jié)論

本文提出了利用有向圖鄰接矩陣的最短路算法，來計算網(wǎng)絡(luò)的關(guān)鍵路徑，把最短路算法和關(guān)鍵路徑算法有機地結(jié)合起來，該算法的思路十分自然，容易理解，并且便于用Matlab軟件實現(xiàn)。

參考文獻

[1]司守奎，孫璽菁．?dāng)?shù)學(xué)建模算法與應(yīng)用[M]．北京：國防工業(yè)出版社，2011．

[2]謝金星，薛毅．優(yōu)化建模與LINDO/LINGO軟件[M]．北京：清華大學(xué)出版社，2005．

作者簡介：韋利春（1985-），男，山東德州人，煙臺南山學(xué)院高級技師，研究方向：實訓(xùn)教學(xué)；高紅慧（1985-），女，吉林白城人，煙臺南山學(xué)院助教，研究方向：自動化控制；王艷娟（1981-），女，吉林白城人，煙臺南山學(xué)院助教，研究方向：實訓(xùn)教學(xué)；王慧（1986-），女，山東臨沂人，煙臺南山學(xué)院教師，碩士，研究方向：實訓(xùn)教學(xué)；高紅彬（1988-），男，山東高密人，供職于誠海電子有限公司，研究方向：電子技術(shù)。

（責(zé)任編輯：周加轉(zhuǎn)）