蘇志雄 李星梅 乞建勛

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

網(wǎng)絡(luò)計(jì)劃中構(gòu)建對(duì)偶網(wǎng)絡(luò)模型的理論和方法

蘇志雄 李星梅 乞建勛

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

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

運(yùn)籌學(xué);對(duì)偶理論;網(wǎng)絡(luò)計(jì)劃;時(shí)差

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

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

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

本文通過分析時(shí)差、路差和路長的關(guān)系，運(yùn)用對(duì)偶原理和最短路線法，構(gòu)建網(wǎng)絡(luò)計(jì)劃模型的對(duì)偶網(wǎng)絡(luò)模型，并分析該模型的性質(zhì).

1 網(wǎng)絡(luò)計(jì)劃的節(jié)點(diǎn)參數(shù)計(jì)算

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

1）從源點(diǎn)（1）開始:

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

2）從匯點(diǎn)（n）開始:

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

2 基本概念

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

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

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

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

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

路差.從源點(diǎn)到匯點(diǎn)的路線μ的路差表示該路線與關(guān)鍵路線μ▽的路長之差，記為，即

3 路差定理

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

證明 設(shè)網(wǎng)絡(luò)計(jì)劃圖中任意路線μ為

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

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

根據(jù)式（10）:

式（11）成立.

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

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

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

根據(jù)式（10）:

式（13）成立.

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

4 對(duì)偶網(wǎng)絡(luò)模型及構(gòu)建方法

4.1 對(duì)偶網(wǎng)絡(luò)模型的概念和構(gòu)建原理

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

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

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

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

4.2 對(duì)偶網(wǎng)絡(luò)模型的構(gòu)建方法

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

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

1）先從源點(diǎn)（1）開始

2）再從匯點(diǎn)（n）開始

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

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

4.2.2 第一類對(duì)偶網(wǎng)絡(luò)模型的構(gòu)建方法及性質(zhì)

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

1）計(jì)算工序的自由時(shí)差;

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

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

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

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

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

4.2.3 第二類對(duì)偶網(wǎng)絡(luò)模型的構(gòu)建方法及性質(zhì)

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

1）計(jì)算工序的安全時(shí)差;

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

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

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

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

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

4.2.4 第三類對(duì)偶網(wǎng)絡(luò)模型的構(gòu)建方法及性質(zhì)

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

該類對(duì)偶網(wǎng)絡(luò)模型的構(gòu)建方法如下:

1）計(jì)算工序的總時(shí)差，并代替各自工期;

2）計(jì)算節(jié)點(diǎn)的節(jié)點(diǎn)時(shí)差;

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

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

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

4.2.5 第四類對(duì)偶網(wǎng)絡(luò)模型的構(gòu)建方法及性質(zhì)

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

該類對(duì)偶網(wǎng)絡(luò)模型的構(gòu)建方法如下:

1）計(jì)算工序干擾時(shí)差，并代替各自工期;2）計(jì)算節(jié)點(diǎn)的節(jié)點(diǎn)時(shí)差;

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

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

第四類與第三類對(duì)偶模型的基本性質(zhì)相同.

4.3 對(duì)偶等價(jià)性

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

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

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

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

5 應(yīng)用舉例

構(gòu)建如圖1所示的網(wǎng)絡(luò)計(jì)劃模型的對(duì)偶網(wǎng)絡(luò)模型.

圖1 網(wǎng)絡(luò)計(jì)劃圖

分別構(gòu)建該模型的4類對(duì)偶網(wǎng)絡(luò)模型.

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

本文通過分析路長與時(shí)差之間的關(guān)系，構(gòu)建出網(wǎng)絡(luò)計(jì)劃模型的對(duì)偶網(wǎng)絡(luò)模型.該模型既滿足了與原網(wǎng)絡(luò)計(jì)劃模型之間對(duì)偶關(guān)系，又充分體現(xiàn)了時(shí)差和路差的關(guān)鍵性作用，與網(wǎng)絡(luò)計(jì)劃模型相比更具優(yōu)越性.兩模型之間的關(guān)系是，一個(gè)網(wǎng)絡(luò)計(jì)劃模型對(duì)應(yīng)有4類對(duì)偶網(wǎng)絡(luò)模型，而一個(gè)對(duì)偶網(wǎng)絡(luò)模型對(duì)應(yīng)有無窮多個(gè)網(wǎng)絡(luò)計(jì)劃模型.此外，利用該模型，還揭示了網(wǎng)絡(luò)計(jì)劃模型的對(duì)偶等價(jià)性，通過研究一個(gè)對(duì)偶網(wǎng)絡(luò)模型就能夠得到與其對(duì)應(yīng)的無窮多個(gè)網(wǎng)絡(luò)計(jì)劃模型的共同性質(zhì)，為網(wǎng)絡(luò)計(jì)劃優(yōu)化的進(jìn)一步深入提供了思想和依據(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］王強(qiáng)，李星梅，乞建勛.雙代號(hào)網(wǎng)絡(luò)圖中虛工序?qū)r(shí)差計(jì)算公式的影響與修正［J］.系統(tǒng)工程理論與實(shí)踐，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)絡(luò)計(jì)劃管理中的機(jī)動(dòng)時(shí)間特性及其應(yīng)用［M］.北京:科學(xué)出版社，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］王佳，李星梅，乞建勛.基于機(jī)動(dòng)時(shí)間的平行序鏈順序優(yōu)化算法設(shè)計(jì)［J］.系統(tǒng)工程學(xué)報(bào)，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］乞建勛，李星梅，王強(qiáng).等效子網(wǎng)絡(luò)的理論與方法［J］.管理科學(xué)學(xué)報(bào)，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］李星梅，乞建勛，蘇志雄.自由時(shí)差定理與k階次關(guān)鍵路線的求法［J］.管理科學(xué)學(xué)報(bào)，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］李星梅，乞建勛，蘇志雄.雙代號(hào)網(wǎng)絡(luò)計(jì)劃中工序機(jī)動(dòng)時(shí)間蔓延性研究［J］.系統(tǒng)工程學(xué)報(bào)，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)絡(luò)計(jì)劃技術(shù)［M］.沈陽:遼寧出版社，1984

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

［17］張連營，王亮，呂文學(xué).網(wǎng)絡(luò)計(jì)劃的模糊分析［J］.天津大學(xué)學(xué)報(bào)，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)絡(luò)計(jì)劃計(jì)算模型的統(tǒng)一［J］.系統(tǒng)工程理論與實(shí)踐，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)絡(luò)計(jì)劃模型及性質(zhì)［J］.運(yùn)籌與管理，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)絡(luò)出版時(shí)間:

時(shí)間:2012-02-21 11:46;

CNKI:11-2625/V.20120221.1146.013

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

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

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

（編 輯:文麗芳）