網(wǎng)絡計劃中構建對偶網(wǎng)絡模型的理論和方法

蘇志雄 李星梅 乞建勛

（華北電力大學 經(jīng)濟與管理學院，北京 102206）

網(wǎng)絡計劃中構建對偶網(wǎng)絡模型的理論和方法

蘇志雄 李星梅 乞建勛

（華北電力大學 經(jīng)濟與管理學院，北京 102206）

針對現(xiàn)有的網(wǎng)絡計劃模型重點體現(xiàn)的不是其核心機動時間和路差，而是具體的時間和路長，進而使得該模型在運用時往往會遇到阻礙的問題，利用對偶原理，構建網(wǎng)絡計劃模型的對偶模型.首先，通過分析機動時間和路長之間的關系，推導出路差定理;其次，在路差定理的基礎上，利用對偶原理構建對偶網(wǎng)絡模型，并分析其性質;然后利用該模型揭示網(wǎng)絡計劃的對偶等價性;最后，通過例子進行驗證和說明.該對偶網(wǎng)絡模型重點體現(xiàn)了機動時間和路差，使得網(wǎng)絡計劃更具針對性和有效性.

運籌學;對偶理論;網(wǎng)絡計劃;時差

網(wǎng)絡計劃［1］產生于20世紀50年代，是目前最常用的處理項目計劃的圖形技術.機動時間（也稱時差）和時間參數(shù)是其核心，對它們的研究伴隨著網(wǎng)絡計劃的誕生而起步.在時間參數(shù)上，文獻［2－3］修正了原有計算方法，使得同一工序系統(tǒng)即使對應不同的網(wǎng)絡圖也能得到唯一正確的時間參數(shù).在機動時間上，國際當前通用的有總時差、安全時差、自由時差、節(jié)點時差和干擾時差［1，4］.文獻［5］針對同一工序系統(tǒng)的不同網(wǎng)絡圖表示，對各時差計算方法進行了修正.針對其特性，國內外學者已經(jīng)做了很多研究［6－10］，其成果已廣泛應用于實踐和求解各類經(jīng)典問題.

網(wǎng)絡計劃是優(yōu)化模型，用于求解優(yōu)化問題，因此可以設想能否將優(yōu)化理論運用到網(wǎng)絡計劃中.對偶理論是優(yōu)化理論的基礎，能夠簡化問題的求解，當前主要應用于多目標規(guī)劃理論［11－12］.因而，可嘗試運用對偶原理對網(wǎng)絡計劃模型進行研究，以達到模型改進的目的.網(wǎng)絡計劃模型需要改進的原因主要在于:首先，直接使用該模型往往不易順利有效地解決相關問題，很多問題雖然求解目標與工期和路長相關，但求解過程中真正需要考慮的卻是時差和路差.例如，文獻［5，13］在等效化簡時間-費用權衡問題時，需要考慮的僅僅是總時差和節(jié)點時差;文獻［5，14］在求解k階次關鍵路線問題時，也只需要分析自由時差和路差即可.其次，網(wǎng)絡計劃模型的根本價值在于時差，而非工期和路長，因此其特性主要是時差的特性.文獻［5，15］分析了時差的動態(tài)特性;特別地，文獻［5］分析了時差的靜態(tài)特性，包括時差與路長的關系等，只與路差有關.但現(xiàn)有網(wǎng)絡計劃模型卻重點反映工期和路長，進而在應用上，工期、路長等非實質因素常具干擾性，而時差、路差等實質因素的作用卻被消弱，使得問題在求解上效果不佳.因此，需要構建重點反映時差和路差的新網(wǎng)絡計劃模型.

經(jīng)上述分析，如果能構建新模型，使其既與網(wǎng)絡計劃模型之間滿足對偶關系，又能充分體現(xiàn)時差和路差的關鍵作用，那么無疑更具優(yōu)越性.在網(wǎng)絡計劃模型的改進上，人們長期主要針對應用范圍對其進行拓廣，從傳統(tǒng)網(wǎng)絡計劃，如關鍵路線法和計劃評審技術，拓廣為隨機網(wǎng)絡計劃［16］、模糊網(wǎng)絡計劃［17］、一般優(yōu)先關系網(wǎng)絡計劃［18］、搭接網(wǎng)絡計劃［19］、流水網(wǎng)絡計劃［19］等，努力使得各類問題都能夠用相應類型的網(wǎng)絡計劃表示.但是針對網(wǎng)絡計劃模型自身的轉變，如初始-對偶轉變，目前還缺乏相關研究.

本文通過分析時差、路差和路長的關系，運用對偶原理和最短路線法，構建網(wǎng)絡計劃模型的對偶網(wǎng)絡模型，并分析該模型的性質.

1 網(wǎng)絡計劃的節(jié)點參數(shù)計算

任意網(wǎng)絡計劃圖中，設Dij表示工序（i，j）的工期（duration），和分別表示節(jié)點（i）的最早時間參數(shù)（the earliest time）和最遲時間參數(shù)（the latest time），則和的計算方法如下.

1）從源點（1）開始:

若（j）是虛出節(jié)點（緊后工序都是虛工序），（k）是（j）的緊后節(jié)點，則

2）從匯點（n）開始:

3）從源點（1）開始，若（j）是虛入節(jié)點（緊前工序都是虛工序），（i）是（）j的緊前節(jié)點，則

2 基本概念

總時差（total float）.工序i，（j）的總時差是指在不影響工程總工期的條件下，該工序可以使用的機動時間的最大值，用表示，即

安全時差（safety float）.工序i，（j）的安全時差是指該工序的緊前工序在最遲結束時間結束時，該工序仍可以使用而不影響工程總工期的機動時間的最大值，用表示，即

自由時差（free float）.工序i，（j）的自由時差是指在不影響緊后工序最早開始的前提下，該工序可以使用的機動時間的最大值，用表示，即

干擾時差（interference float）.如果工序的干擾時差為正，表示當該工序的緊后工序能夠最早開始，并且緊前工序能夠最遲結束的情況下，它工期可以延長的最大時間;如果該時差為負，其絕對值表示當該工序的緊后工序能夠最早開始，并且緊前工序能夠最遲結束的情況下，它的工期需要縮短的最小時間.工序i，（）j的干擾時差用表示，即

節(jié)點時差（node float）.節(jié)點（i）的時差是指該節(jié)點的最遲時間與最早時間的差值，記為，即

路差.從源點到匯點的路線μ的路差表示該路線與關鍵路線μ▽的路長之差，記為，即

3 路差定理

網(wǎng)絡計劃圖中任意路線μ的路差可用該路線上工序和節(jié)點的時差表示，表現(xiàn)為以下公式:

證明 設網(wǎng)絡計劃圖中任意路線μ為

對于任意工序 （i，j），根據(jù)式（5）～式（8）:

1）根據(jù)路長的概念和式（15）:

根據(jù)式（10）:

式（11）成立.

2）同理可證式（12）成立.

3）根據(jù)路長的概念和式（15），以及前面式（11）和式（12）的推導過程:

根據(jù)式（1）、式（2），源匯點時差為零，所以

根據(jù)式（10）:

式（13）成立.

4）同理可證式（14）成立. 證畢

4 對偶網(wǎng)絡模型及構建方法

4.1 對偶網(wǎng)絡模型的概念和構建原理

根據(jù)對偶的含義，對于一個網(wǎng)絡計劃模型，記為A，如果基于A能夠生成另一個網(wǎng)絡模型，記為B，使其具有與A相同的結構和性質，但表示方法卻與A相反.例如，根據(jù)文獻［5］，A中參數(shù)反映的是最長路的情況，那么B中參數(shù)反映的就是最短路的情況，并且這2種路線表示的是相同的路線，那么就稱B是A的對偶網(wǎng)絡模型.

根據(jù)路差的概念，如果路線的路長越大，那么它的路差就越小，反之亦然.這樣，任意路線的路長和路差就具有了對偶關系，可以在路差的基礎上構建網(wǎng)絡計劃模型的對偶網(wǎng)絡模型.

根據(jù)路差定理，任意路線的路差可由不同時差用不同的4種方式組成，因此可以利用這4種方式構建4類網(wǎng)絡模型.首先，將每個時差的正值或負值都作為模型中對應工序的工期，使模型中任意路線的路長都等于原網(wǎng)絡計劃中對應路線的路差;然后，用最短路線法計算各節(jié)點的參數(shù)，使得任意節(jié)點參數(shù)對應的最短路就是原網(wǎng)絡計劃中相應節(jié)點參數(shù)對應的最長路.在這里，找最短路等同于在原網(wǎng)絡計劃中找最長路，這樣就可以構建出原網(wǎng)絡計劃模型的對偶模型.

通過上述分析，由一個網(wǎng)絡計劃模型可以構建出4個不同的對偶網(wǎng)絡模型，它們綜合反映同一個網(wǎng)絡計劃模型的各種性質，相互具有互補性.因此，可稱它們?yōu)榛パa對偶網(wǎng)絡模型.

4.2 對偶網(wǎng)絡模型的構建方法

4.2.1 最短路網(wǎng)絡模型

文獻［20］給出了最短路網(wǎng)絡模型中節(jié)點參數(shù)的計算方法:

1）先從源點（1）開始

2）再從匯點（n）開始

若（j）是虛出節(jié)點，（k）是（j）的緊后節(jié)點，則

3）再從源點（1）開始，若（j）是虛入節(jié)點，（i）是（j）的緊前節(jié)點，則

4.2.2 第一類對偶網(wǎng)絡模型的構建方法及性質

第一類對偶網(wǎng)絡模型是基于式（11）構建的，其構建方法如下:

1）計算工序的自由時差;

2）用工序的自由時差代替工期，并用式（16）～式（19）計算節(jié)點參數(shù).

根據(jù)最短路模型和文獻［5］自由時差特性，該類對偶模型的基本性質是:

1）所有節(jié)點的參數(shù)TE'=0，TL'≤0;

2）源點到任意節(jié)點的最短路長度為零;

3）最短路線上所有節(jié)點的參數(shù)TL'=0.

4.2.3 第二類對偶網(wǎng)絡模型的構建方法及性質

第二類對偶網(wǎng)絡模型是基于式（12）構建的，其構建方法如下:

1）計算工序的安全時差;

2）用工序的安全時差代替工期，并用式（16）～式（19）計算節(jié)點參數(shù).

根據(jù)最短路模型和文獻［5］安全時差特性理論，該類對偶模型的基本性質是:

1）所有節(jié)點的參數(shù)TE'≥0，TL'=0;

2）任意節(jié)點到匯點的最短路長度為零;

3）最短路線上所有節(jié)點的參數(shù)TE'=0.

4.2.4 第三類對偶網(wǎng)絡模型的構建方法及性質

第三類對偶網(wǎng)絡模型是基于式（13）構建的.由于需要將節(jié)點時差表示為該類對偶網(wǎng)絡模型中路長的一部分，故在構建該類對偶網(wǎng)絡模型時需將節(jié)點表示成工序的形式，即（i）表示成i，（i'），該工序稱為輔助工序.

該類對偶網(wǎng)絡模型的構建方法如下:

1）計算工序的總時差，并代替各自工期;

2）計算節(jié)點的節(jié)點時差;

3）將除源點和匯點以外的各節(jié)點（i）都表示成輔助工序i，（i'），其工期設為－;

4）用式（16）～式（19）計算節(jié)點參數(shù).

根據(jù)最短路模型，該類模型的基本性質是:最短路長度為零，其上所有節(jié)點參數(shù)為零.

4.2.5 第四類對偶網(wǎng)絡模型的構建方法及性質

第四類對偶網(wǎng)絡模型是基于式（14）構建的.與4.2.4同理，在構建該類對偶網(wǎng)絡模型時需將除源點和匯點以外的節(jié)點表示成輔助工序.

該類對偶網(wǎng)絡模型的構建方法如下:

1）計算工序干擾時差，并代替各自工期;2）計算節(jié)點的節(jié)點時差;

3）將除源點和匯點以外的各節(jié)點（i）都表示為輔助工序i，（i'），其工期設為;

4）用式（16）～式（19）計算節(jié)點參數(shù).

第四類與第三類對偶模型的基本性質相同.

4.3 對偶等價性

接下來分析不同網(wǎng)絡計劃圖的對偶網(wǎng)絡模型之間的關系.這里所說的不同網(wǎng)絡計劃圖指的是相互之間工序工期以及總工期不同，但要求網(wǎng)絡的結構相同，即工序的數(shù)量和相互之間的邏輯關系相同，否則，不同結構的網(wǎng)絡計劃圖對應的對偶網(wǎng)絡的結構也必然不同，從而沒有可比性.

根據(jù)文獻［5］可知，網(wǎng)絡計劃中的各類時差都可以用路差表示.不同的網(wǎng)絡計劃之間，雖然工期不同，對應的路線長度也不同，但對應的不同路線的路長之差卻有可能相同，就如同“8≠5，4≠1，但8－5=4－1”一樣.因此，如果不同網(wǎng)絡之間對應的路差相同，則網(wǎng)絡中對應的工序和節(jié)點的時差也相同，那么根據(jù)對偶網(wǎng)絡模型的構建方法，它們的對偶網(wǎng)絡模型也相同.簡單地說就是，不同的網(wǎng)絡計劃可能有相同的時差和對偶網(wǎng)絡，一個對偶網(wǎng)絡的原網(wǎng)絡計劃有無窮多個.

但是反過來說，對于同類型的不同對偶網(wǎng)絡，說明各自的原網(wǎng)絡計劃之間對應的時差不同，即路差也不同，那么對應的路長必有不同，就如同“若 a－b≠c－d，那么必然有 a≠c或b≠d”一樣，進而對應工序的工期必然也有不同，則對應的網(wǎng)絡計劃也必然不同.因此，同類型的不同對偶網(wǎng)絡對應的原網(wǎng)絡計劃必然不同.

通過上述分析可知，對偶網(wǎng)絡模型具有原網(wǎng)絡計劃模型所不具備的特性，能夠反映不同網(wǎng)絡計劃之間的關系.從這個意義上說，具有相同對偶網(wǎng)絡的所有網(wǎng)絡計劃之間具有某種等價性，可稱之為對偶等價性.該性質表明，通過研究一類或幾類互補對偶網(wǎng)絡，就能夠獲得與這些對偶網(wǎng)絡相對應的無窮多個原網(wǎng)絡計劃的共同特性.

5 應用舉例

構建如圖1所示的網(wǎng)絡計劃模型的對偶網(wǎng)絡模型.

圖1 網(wǎng)絡計劃圖

分別構建該模型的4類對偶網(wǎng)絡模型.

1）構建第一類對偶網(wǎng)絡模型.①計算各工序的自由時差;②用各工序的自由時差代替工期，并用式（16）～式（19）計算節(jié)點參數(shù)，得圖2.

圖2是圖1的第一類對偶網(wǎng)絡模型.

圖2 第一類對偶網(wǎng)絡模型

2）構建第二類對偶網(wǎng)絡模型.①計算各工序的安全時差;②用工序的安全時差代替工期，并用式（16）～式（19）計算節(jié)點參數(shù)，得圖3.

圖3是圖1的第二類對偶網(wǎng)絡模型.

圖3 第二類對偶網(wǎng)絡模型

3）構建第三類對偶網(wǎng)絡模型.①計算各工序總時差，并代替各自工期;②計算各節(jié)點的節(jié)點時差;③將除源點（1）和匯點（10）以外的各節(jié)點（i）都表示成輔助工序（i，i'），其工期設為－;④用式（16）～式（19）計算參數(shù)，得圖4.

圖4是圖1的第三類對偶網(wǎng)絡模型.

4）構建第四類對偶網(wǎng)絡模型.①計算工序干擾時差，并代替各自工期;②計算各節(jié)點的節(jié)點時差;③將除源點（1）和匯點（10）以外各節(jié)點（i）都表示成輔助工序i，（i'），其工期設為;④用式（16）～式（19）計算參數(shù)，得圖5.

圖5是圖1的第四類對偶網(wǎng)絡模型.

可以驗證，圖2～圖5中的各類最短路均表示圖1中的各類最長路，由節(jié)點參數(shù)TE'=TL'=0的節(jié)點連接而成的路線就是最短路線，其長度均為零，都對應于圖1中的最長路線，即關鍵路線.

圖4 第三類對偶網(wǎng)絡模型

圖5 第四類對偶網(wǎng)絡模型

6 結論

本文通過分析路長與時差之間的關系，構建出網(wǎng)絡計劃模型的對偶網(wǎng)絡模型.該模型既滿足了與原網(wǎng)絡計劃模型之間對偶關系，又充分體現(xiàn)了時差和路差的關鍵性作用，與網(wǎng)絡計劃模型相比更具優(yōu)越性.兩模型之間的關系是，一個網(wǎng)絡計劃模型對應有4類對偶網(wǎng)絡模型，而一個對偶網(wǎng)絡模型對應有無窮多個網(wǎng)絡計劃模型.此外，利用該模型，還揭示了網(wǎng)絡計劃模型的對偶等價性，通過研究一個對偶網(wǎng)絡模型就能夠得到與其對應的無窮多個網(wǎng)絡計劃模型的共同性質，為網(wǎng)絡計劃優(yōu)化的進一步深入提供了思想和依據(jù).

（References）

［1］Demeulemeester E L，Herrlelen W S.Project scheduling［M］.Boston:Kluwer Academic Publishers，2002:17－48

［2］Michael D J，Kamburowski J，Stallman M.On minimum dummy arc problem［J］.Operations Research，1993，27（2）:153－168

［3］Elmaghraby S E，Kamburowski J.On project representationand activity floats［J］.Arabian Journal of Science and Engineering，1990，15:627－637

［4］Elmaghraby S E.Activity nets:a guided tour through some recent developments［J］.European Journal of Operational Research，1995，82:383－408

［5］王強，李星梅，乞建勛.雙代號網(wǎng)絡圖中虛工序對時差計算公式的影響與修正［J］.系統(tǒng)工程理論與實踐，2008（6）:106－114

Wang Qiang，Li Xingmei，Qi Jianxun.A research on the influence of dummy activity on float in an AOA networkand its amendments［J］.Systems Engineering-Theory ＆ Practice，2008（6）:106－114（in Chinese）

［6］乞建勛，張立輝，李星梅.網(wǎng)絡計劃管理中的機動時間特性及其應用［M］.北京:科學出版社，2009:22－45

Qi Jianxun，Zhang Lihui，Li Xingmei.Property and application of float in network planning management［M］.Beijing:Science Publisher，2009:22－45（in Chinese）

［7］王佳，李星梅，乞建勛.基于機動時間的平行序鏈順序優(yōu)化算法設計［J］.系統(tǒng)工程學報，2008，23（4）:455－461

Wang Jia，Li Xingmei，Qi Jianxun.Sequencing optimalarithmetic design of parallel procedure chains basedon activity float［J］.Journal of Systems Engineering，2008，23（4）:455－461（in Chinese）

［8］Yakhchali S H，Ghodsypour S H.Computing latest starting times of activities in interval-valued networks with minimal time lags［J］.European Journal of Operational Research，2010，200（3）:874－880

［9］Sirakoulis K K.The effectiveness of resource leveling tools for resource constraint project scheduling problem［J］.International Journal of Project Management，2009，27（5）:493－500

［10］Karaca Z，Onargan T.The application of critical path method（CPM）in workflow schema of marble processing plants［J］.Materials and Manufacturing Processes，2007，22（1）:37－44

［11］Rodder W.A generalized saddlepoint theory:its application to duality theory for linear vector optimum problems［J］.European Journal of Operational Researh，1977，1（1）:55－59

［12］Ivanov E H，Nehse R.Some results on dual vector optimization problems［J］.Optimization，1985，16（4）:505－517

［13］乞建勛，李星梅，王強.等效子網(wǎng)絡的理論與方法［J］.管理科學學報，2010，13（1）:40－44

Qi Jianxun，Li Xingmei，Wang Qiang.Theories and methods of creating equivalent sub-network［J］.Journal of Management Sciences in China，2010，13（1）:40－44（in Chinese）

［14］李星梅，乞建勛，蘇志雄.自由時差定理與k階次關鍵路線的求法［J］.管理科學學報，2009，12（2）:98－104

Li Xingmei，Qi Jianxun，Su Zhixiong.Free float theorem and algorithm of seeking the k-th order critical path［J］.Journal of Management Sciences in China，2009，12（2）:98－104（in Chinese）

［15］李星梅，乞建勛，蘇志雄.雙代號網(wǎng)絡計劃中工序機動時間蔓延性研究［J］.系統(tǒng)工程學報，2009，24（1）:39－45

Li Xingmei，Qi Jianxun，Su Zhixiong.Study of activity float spread property in activity-on-arc network planning［J］.Journal of Systems Engineering，2009，24（1）:39－45（in Chinese）

［16］王眾托，張軍.網(wǎng)絡計劃技術［M］.沈陽:遼寧出版社，1984

Wang Zhongtuo，Zhang Jun.Network planning technology［M］.Shenyang:Liaoning Publisher，1984（in Chinese）

［17］張連營，王亮，呂文學.網(wǎng)絡計劃的模糊分析［J］.天津大學學報，2004，37（2）:175－178

Zhang Lianying，Wang Liang，Lü Wenxue.Calculation and analysis of project network based on fuzzy set［J］.Journal of Tianjin University，2004，37（2）:175－178（in Chinese）

［18］Elmaghraby S E，Kamburowski J.The analysis of activity networks under generalized precedence relations（GPRs）［J］.Management Science，1992，38（9）:1245－1263

［19］楊冰.網(wǎng)絡計劃計算模型的統(tǒng)一［J］.系統(tǒng)工程理論與實踐，2002（3）:51－55

Yang Bing.Unifyingcalculatingmodelsforthe network Planning［J］.Systems Engineering-Theory ＆ Practice，2002（3）:51－55（in Chinese）

［20］蘇志雄，李星梅，乞建勛.基于CPM原理和Dijkstra算法的SPM網(wǎng)絡計劃模型及性質［J］.運籌與管理，2008，17（1）:148－153

Su Zhixiong，Li Xingmei，Qi Jianxun.SPM network planning model and its characteristics based on CPM theory and Dijkstra algorithm［J］.Operations Research and Management Science，2008，17（1）:148－153（in Chinese）

Theory and method of creating dual network model in network planning

Su Zhixiong Li Xingmei Qi Jianxun

（School of Business Administration，North China Electric Power University，Beijing 102206，China）

Aiming at problem that existing network planning model incarnates specific time and path length prominently instead of its core float and path length difference，which makes obstacles common exist when using the model in practice，dual model of network planning model was founded by using dual theory.Firstly，path length theorem was deduced by analyzing relation between float and path length;Secondly，based on path length theorem，dual network model was founded by using dual theory，and its properties were analyzed;Thirdly，dual equivalence property of network planning was revealed by using the model;Finally，the model was validated and illuminated by illustration.The dual network model incarnates float and path length difference prominently，which makes network planning have more prominent pertinence and validity.

operational research;dual theory;network planning;float

TB 114.1

A

1001-5965（2012）02-0257-06

2010-11-19;< class="emphasis_bold">網(wǎng)絡出版時間:

時間:2012-02-21 11:46;

CNKI:11-2625/V.20120221.1146.013

www.cnki.net/kcms/detail/11.2625.V.20120221.1146.013.html

國家自然科學基金資助項目（70671040）;華北電力大學博士研究生創(chuàng)新基金資助項目

蘇志雄（1983－），男，山西朔州人，博士生，suzhixiongbaner@126.com.

（編 輯:文麗芳）