第07章-圖論與網(wǎng)絡(luò)模型

1、優(yōu)優(yōu) 化化 建建 模模 歡迎各位同學(xué)學(xué)習(xí)第七章歡迎各位同學(xué)學(xué)習(xí)第七章 內(nèi)容導(dǎo)航內(nèi)容導(dǎo)航 概述概述 7.1運(yùn)輸問(wèn)題與轉(zhuǎn)運(yùn)問(wèn)題運(yùn)輸問(wèn)題與轉(zhuǎn)運(yùn)問(wèn)題 7.2最短路問(wèn)題和最大流問(wèn)題最短路問(wèn)題和最大流問(wèn)題 7.3最優(yōu)連線(xiàn)問(wèn)題與旅行商問(wèn)題最優(yōu)連線(xiàn)問(wèn)題與旅行商問(wèn)題 7.4計(jì)劃評(píng)審方法和關(guān)鍵路線(xiàn)法計(jì)劃評(píng)審方法和關(guān)鍵路線(xiàn)法 習(xí)題習(xí)題 七七 第第 7 7 章章 圖論與網(wǎng)絡(luò)模型圖論與網(wǎng)絡(luò)模型 優(yōu)優(yōu) 化化 建建 模模 本章內(nèi)容概述本章內(nèi)容概述 本章介紹圖論與網(wǎng)絡(luò)本章介紹圖論與網(wǎng)絡(luò)(Graph Theory and Network)的的 有關(guān)優(yōu)化問(wèn)題模型。在這里，我們并不打算全面系統(tǒng)介紹有關(guān)優(yōu)化問(wèn)題模型。在這里，我們并不

2、打算全面系統(tǒng)介紹 圖論與網(wǎng)絡(luò)的知識(shí)，而著重介紹與圖論與網(wǎng)絡(luò)的知識(shí)，而著重介紹與LINDO、LINGO軟件有軟件有 關(guān)的組合優(yōu)化模型和相應(yīng)的求解過(guò)程。如果讀者打算深入關(guān)的組合優(yōu)化模型和相應(yīng)的求解過(guò)程。如果讀者打算深入 地了解圖論與網(wǎng)絡(luò)的更全面的知識(shí)，請(qǐng)參閱圖論或運(yùn)籌學(xué)地了解圖論與網(wǎng)絡(luò)的更全面的知識(shí)，請(qǐng)參閱圖論或運(yùn)籌學(xué) 中的有關(guān)書(shū)籍中的有關(guān)書(shū)籍. LINDO軟件和軟件和LINGO軟件可以求解一些著名的組合優(yōu)軟件可以求解一些著名的組合優(yōu) 化問(wèn)題，這包括最短路問(wèn)題、最大流問(wèn)題、運(yùn)輸和轉(zhuǎn)運(yùn)問(wèn)化問(wèn)題，這包括最短路問(wèn)題、最大流問(wèn)題、運(yùn)輸和轉(zhuǎn)運(yùn)問(wèn) 題、最優(yōu)匹配和最優(yōu)指派問(wèn)題、最優(yōu)連線(xiàn)或最小生成樹(shù)問(wèn)題、最優(yōu)匹配

3、和最優(yōu)指派問(wèn)題、最優(yōu)連線(xiàn)或最小生成樹(shù)問(wèn) 題、旅行商問(wèn)題、關(guān)鍵路線(xiàn)法與計(jì)劃評(píng)審方法等。題、旅行商問(wèn)題、關(guān)鍵路線(xiàn)法與計(jì)劃評(píng)審方法等。 優(yōu)優(yōu) 化化 建建 模模 7.17.1運(yùn)輸問(wèn)題與轉(zhuǎn)運(yùn)問(wèn)題運(yùn)輸問(wèn)題與轉(zhuǎn)運(yùn)問(wèn)題 本節(jié)內(nèi)容導(dǎo)航本節(jié)內(nèi)容導(dǎo)航 7.1.1運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 7.1.2指派問(wèn)題指派問(wèn)題 7.1.3轉(zhuǎn)運(yùn)問(wèn)題轉(zhuǎn)運(yùn)問(wèn)題 優(yōu)優(yōu) 化化 建建 模模 7.1.1運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題(Transportation Problem)是圖論與是圖論與 網(wǎng)絡(luò)中的一個(gè)重要問(wèn)題，也是一個(gè)典型的線(xiàn)性網(wǎng)絡(luò)中的一個(gè)重要問(wèn)題，也是一個(gè)典型的線(xiàn)性 規(guī)劃問(wèn)題規(guī)劃問(wèn)題. 例例7.1 （運(yùn)輸問(wèn)題）（運(yùn)輸問(wèn)題） 返 回 導(dǎo)

4、航 優(yōu)優(yōu) 化化 建建 模模 例例7.1 就是典型的運(yùn)輸問(wèn)題，圖就是典型的運(yùn)輸問(wèn)題，圖7-1給出了給出了 個(gè)產(chǎn)地，個(gè)產(chǎn)地， 個(gè)銷(xiāo)地運(yùn)輸問(wèn)題的圖形個(gè)銷(xiāo)地運(yùn)輸問(wèn)題的圖形.關(guān)于它的求關(guān)于它的求 解方法有兩類(lèi)，一類(lèi)是按照?qǐng)D論的方法求解，解方法有兩類(lèi)，一類(lèi)是按照?qǐng)D論的方法求解， 另一類(lèi)是化成線(xiàn)性規(guī)劃問(wèn)題另一類(lèi)是化成線(xiàn)性規(guī)劃問(wèn)題.這里介紹第二類(lèi)方這里介紹第二類(lèi)方 法，即用法，即用LINDO或或LINGO軟件求解運(yùn)輸問(wèn)題軟件求解運(yùn)輸問(wèn)題. 但為便于后面的敘述，先給出圖論中有關(guān)圖的但為便于后面的敘述，先給出圖論中有關(guān)圖的 部分定義部分定義. m n 圖7-1: 個(gè)產(chǎn)地, 個(gè)銷(xiāo)售地運(yùn)輸問(wèn)題的圖形mn 優(yōu)優(yōu) 化化

5、建建 模模 1. 圖的基本定義圖的基本定義 從直觀上看, 所謂圖是由點(diǎn)和邊組成的圖形, 如 圖7-1所示.下面我們給出圖的定義. 優(yōu)優(yōu) 化化 建建 模模 注：注：通常有向圖的邊稱(chēng)為弧，由弧構(gòu)成的集記為通常有向圖的邊稱(chēng)為弧，由弧構(gòu)成的集記為 因此，有向圖記為因此，有向圖記為, 而無(wú)向圖記為而無(wú)向圖記為. 為為 方便起見(jiàn)，在后面的論述中，有時(shí)也用表示有方便起見(jiàn)，在后面的論述中，有時(shí)也用表示有 向圖向圖. 在無(wú)向圖中在無(wú)向圖中, 每條至多有一條邊的圖稱(chēng)為簡(jiǎn)單圖每條至多有一條邊的圖稱(chēng)為簡(jiǎn)單圖 (Simple Graph). 若每一對(duì)不同的頂點(diǎn)都有一條邊相若每一對(duì)不同的頂點(diǎn)都有一條邊相 連的簡(jiǎn)單圖稱(chēng)為完

6、全圖連的簡(jiǎn)單圖稱(chēng)為完全圖(Complete Graph). 若一個(gè)圖若一個(gè)圖 中的頂點(diǎn)集可以分解為兩個(gè)子集和中的頂點(diǎn)集可以分解為兩個(gè)子集和, 使得任何一使得任何一 條邊都有一個(gè)端點(diǎn)在中條邊都有一個(gè)端點(diǎn)在中, 另一個(gè)端點(diǎn)在中另一個(gè)端點(diǎn)在中, 這種圖這種圖 稱(chēng)為二部圖或偶圖稱(chēng)為二部圖或偶圖(Bipartite Graph). 運(yùn)輸問(wèn)題所構(gòu)成運(yùn)輸問(wèn)題所構(gòu)成 的圖的圖7-1是偶圖是偶圖. , A),(EVG ),(AVG ),(EVG 1 V 2 V 1 V 2 V 優(yōu)優(yōu) 化化 建建 模模 2. 運(yùn)輸問(wèn)題的數(shù)學(xué)表達(dá)式運(yùn)輸問(wèn)題的數(shù)學(xué)表達(dá)式 . 11 m i n j ijij xc 第個(gè)產(chǎn)地的運(yùn)出量應(yīng)小于

7、或等于該地的生產(chǎn)量，即：第個(gè)產(chǎn)地的運(yùn)出量應(yīng)小于或等于該地的生產(chǎn)量，即：i . 1 n j iij ax 第個(gè)銷(xiāo)地的運(yùn)入量應(yīng)等于該地的需求量，即：第個(gè)銷(xiāo)地的運(yùn)入量應(yīng)等于該地的需求量，即：j . 1 m i jij bx 優(yōu)優(yōu) 化化 建建 模模 因此，運(yùn)輸問(wèn)題的數(shù)學(xué)表達(dá)式為因此，運(yùn)輸問(wèn)題的數(shù)學(xué)表達(dá)式為: 稱(chēng)具有形如式稱(chēng)具有形如式的線(xiàn)性規(guī)劃問(wèn)題為運(yùn)輸問(wèn)題的線(xiàn)性規(guī)劃問(wèn)題為運(yùn)輸問(wèn)題.)4()1( 優(yōu)優(yōu) 化化 建建 模模 3. 運(yùn)輸問(wèn)題的求解過(guò)程運(yùn)輸問(wèn)題的求解過(guò)程 為了便于討論，以一個(gè)運(yùn)輸問(wèn)題實(shí)例的求解過(guò)為了便于討論，以一個(gè)運(yùn)輸問(wèn)題實(shí)例的求解過(guò) 程來(lái)介紹如何用程來(lái)介紹如何用LINDO或或LINGO軟件求解

8、運(yùn)輸問(wèn)軟件求解運(yùn)輸問(wèn) 題模型題模型. 例例7.2(繼例繼例7.1) 設(shè)設(shè) 即為有即為有3個(gè)產(chǎn)地和個(gè)產(chǎn)地和 4個(gè)銷(xiāo)地的運(yùn)輸問(wèn)題，其產(chǎn)量、銷(xiāo)量及單位運(yùn)費(fèi)如個(gè)銷(xiāo)地的運(yùn)輸問(wèn)題，其產(chǎn)量、銷(xiāo)量及單位運(yùn)費(fèi)如 表表7-1所示所示.試求總運(yùn)費(fèi)最少的運(yùn)輸方案，以及總試求總運(yùn)費(fèi)最少的運(yùn)輸方案，以及總 運(yùn)費(fèi)運(yùn)費(fèi). 4, 3nm 優(yōu)優(yōu) 化化 建建 模模 解：解：從前面的分析來(lái)看，運(yùn)輸問(wèn)題屬于線(xiàn)性規(guī)劃問(wèn)從前面的分析來(lái)看，運(yùn)輸問(wèn)題屬于線(xiàn)性規(guī)劃問(wèn) 題，因此，不論是題，因此，不論是LINDO軟件或軟件或LINGO軟件都可以對(duì)軟件都可以對(duì) 該問(wèn)題求解該問(wèn)題求解.為了便于比較兩種軟件的優(yōu)缺點(diǎn)，以及各為了便于比較兩種軟件的優(yōu)缺點(diǎn)，以

9、及各 自的特點(diǎn)，我們用兩種軟件分別求解該運(yùn)輸問(wèn)題自的特點(diǎn)，我們用兩種軟件分別求解該運(yùn)輸問(wèn)題. 首先寫(xiě)出首先寫(xiě)出LINDO軟件的模型（程序），程序名：軟件的模型（程序），程序名： exam0702.ltx. ! 3 Warehouse, 4 Customer Transportation Problem ! The objective min 6x11 + 2x12 + 6x13 + 7x14 + 4x21 + 9x22 + 5x23 + 3x24 + 8x31 + 8x32 + x33 + 5x34 subject to 優(yōu)優(yōu) 化化 建建 模模 ! The supply constraints

10、 2) x11 + x12 + x13 + x14 = 30 3) x21 + x22 + x23 + x24 = 25 4) x31 + x32 + x33 + x34 = 21 ! The demand constraints 5) x11 + x21 + x31 = 15 6) x12 + x22 + x32 = 17 7) x13 + x23 + x33 = 22 8) x14 + x24 + x34 = 12 end 優(yōu)優(yōu) 化化 建建 模模 LINDO軟件的計(jì)算結(jié)果如下：軟件的計(jì)算結(jié)果如下： LP OPTIMUM FOUND AT STEP 6 OBJECTIVE FUNCTION

11、VALUE 1) 161.0000 VARIABLE VALUE REDUCED COST X11 2.000000 0.000000 X12 17.000000 0.000000 X13 1.000000 0.000000 X14 0.000000 2.000000 X21 13.000000 0.000000 X22 0.000000 9.000000 X23 0.000000 1.000000 優(yōu)優(yōu) 化化 建建 模模 X24 12.000000 0.000000 X31 0.000000 7.000000 X32 0.000000 11.000000 X33 21.000000 0.00

12、0000 X34 0.000000 5.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 10.000000 0.000000 3) 0.000000 2.000000 4) 0.000000 5.000000 5) 0.000000 -6.000000 6) 0.000000 -2.000000 7) 0.000000 -6.000000 8) 0.000000 -5.000000 NO. ITERATIONS= 6 優(yōu)優(yōu) 化化 建建 模模 事實(shí)上，我們關(guān)心更多的是那些非零變量，因此事實(shí)上，我們關(guān)心更多的是那些非零變量，因此, 可選擇可選擇LINDO中的命

13、令（具體方法見(jiàn)第二章的中的命令（具體方法見(jiàn)第二章的2.3節(jié)節(jié)), 只列出非零變量只列出非零變量. OBJECTIVE FUNCTION VALUE 1) 161.0000 VARIABLE VALUE REDUCED COST X11 2.000000 0.000000 X12 17.000000 0.000000 優(yōu)優(yōu) 化化 建建 模模 X13 1.000000 0.000000 X21 13.000000 0.000000 X24 12.000000 0.000000 X33 21.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 3) 0.

14、000000 2.000000 4) 0.000000 5.000000 5) 0.000000 -6.000000 6) 0.000000 -2.000000 7) 0.000000 -6.000000 8) 0.000000 -5.000000 NO. ITERATIONS= 6 優(yōu)優(yōu) 化化 建建 模模 LINDO軟件雖然給出最優(yōu)解，但上述模型還存在軟件雖然給出最優(yōu)解，但上述模型還存在 著缺點(diǎn)，例如，上述方法不便于推廣的一般情況，特著缺點(diǎn)，例如，上述方法不便于推廣的一般情況，特 別是當(dāng)產(chǎn)地和銷(xiāo)地的個(gè)數(shù)較多時(shí)，情況更為突出別是當(dāng)產(chǎn)地和銷(xiāo)地的個(gè)數(shù)較多時(shí)，情況更為突出. 下面寫(xiě)出求解該問(wèn)題的下面

15、寫(xiě)出求解該問(wèn)題的LINGO程序，并在程序中程序，并在程序中 用到在第三章介紹的集與數(shù)據(jù)段，以及相關(guān)的循環(huán)函用到在第三章介紹的集與數(shù)據(jù)段，以及相關(guān)的循環(huán)函 數(shù)數(shù). 寫(xiě)出相應(yīng)的寫(xiě)出相應(yīng)的LINGO程序，程序名：程序，程序名： exam0702.lg4 MODEL: 1! 3 Warehouse, 4 Customer Transportation Problem; 2sets: 3 Warehouse /1.3/: a; 4 Customer /1.4/: b; 優(yōu)優(yōu) 化化 建建 模模 5 Routes( Warehouse, Customer) : c, x; 6endsets 7! Here

16、are the parameters; 8data: 9 a = 30, 25, 21 10 b = 15, 17, 22, 12; 11 c = 6, 2, 6, 7, 12 4, 9, 5, 3, 13 8, 8, 1, 5; 14enddata 15! The objective; 16OBJ min = sum( Routes: c * x); 優(yōu)優(yōu) 化化 建建 模模 17! The supply constraints; 18for( Warehouse(i): SUP 19 sum( Customer(j): x(i,j) = a(i); 20! The demand constr

17、aints; 21for( Customer(j): DEM 22 sum( Warehouse(i): x(i,j) = b(j); END 在上述程序中，第在上述程序中，第16表示運(yùn)輸問(wèn)題中目標(biāo)函數(shù)表示運(yùn)輸問(wèn)題中目標(biāo)函數(shù) (7.1). 第第18 19行表示約束條件行表示約束條件(7.2), 第第21 22行行 表示約束條件表示約束條件(7.3). 優(yōu)優(yōu) 化化 建建 模模 下面列出下面列出LINGO軟件的求解結(jié)果（僅保留非零變量）軟件的求解結(jié)果（僅保留非零變量） Global optimal solution found at iteration: 6 Objective value: 16

18、1.0000 Variable Value Reduced Cost X( 1, 1) 2.000000 0.000000 X( 1, 2) 17.00000 0.000000 X( 1, 3) 1.000000 0.000000 X( 2, 1) 13.00000 0.000000 X( 2, 4) 12.00000 0.000000 X( 3, 3) 21.00000 0.000000 Row Slack or Surplus Dual Price OBJ 161.0000 -1.000000 SUP( 1) 10.00000 0.000000 優(yōu)優(yōu) 化化 建建 模模 從上述求解過(guò)程來(lái)看，

19、兩種軟件的計(jì)算結(jié)果從上述求解過(guò)程來(lái)看，兩種軟件的計(jì)算結(jié)果 是相同的，但由于是相同的，但由于LINGO軟件中采用集、數(shù)據(jù)段軟件中采用集、數(shù)據(jù)段 和循環(huán)函數(shù)的編寫(xiě)方式，因此更便于程序推廣到和循環(huán)函數(shù)的編寫(xiě)方式，因此更便于程序推廣到 一般形式使用一般形式使用.例如，只需修改運(yùn)輸問(wèn)題中產(chǎn)地例如，只需修改運(yùn)輸問(wèn)題中產(chǎn)地 和銷(xiāo)地的個(gè)數(shù)，以及參數(shù)和銷(xiāo)地的個(gè)數(shù)，以及參數(shù)a,b,c的值，就可以求解的值，就可以求解 任何運(yùn)輸問(wèn)題任何運(yùn)輸問(wèn)題.所以，從程序通用性的角度來(lái)看所以，從程序通用性的角度來(lái)看, 推薦大家采用推薦大家采用LINGO軟件來(lái)求解運(yùn)輸問(wèn)題軟件來(lái)求解運(yùn)輸問(wèn)題. 優(yōu)優(yōu) 化化 建建 模模 7.1.2 指派

20、問(wèn)題指派問(wèn)題 例例7.3（指派問(wèn)題）設(shè)有（指派問(wèn)題）設(shè)有n個(gè)人個(gè)人, 計(jì)劃作計(jì)劃作n項(xiàng)工作項(xiàng)工作, 其其 中中 表示第表示第i個(gè)人做第個(gè)人做第j項(xiàng)工作的收益項(xiàng)工作的收益, 現(xiàn)求一種指派方現(xiàn)求一種指派方 式，使得每個(gè)人完成一項(xiàng)工作，使總收益最大式，使得每個(gè)人完成一項(xiàng)工作，使總收益最大. 例例7.3就是指派問(wèn)題就是指派問(wèn)題(Assignment Problem).指派指派 問(wèn)題也是圖論中的重要問(wèn)題，有相應(yīng)的求解方法，如問(wèn)題也是圖論中的重要問(wèn)題，有相應(yīng)的求解方法，如 匈牙利算法匈牙利算法.從問(wèn)題的形式來(lái)看，指派問(wèn)題是運(yùn)輸問(wèn)從問(wèn)題的形式來(lái)看，指派問(wèn)題是運(yùn)輸問(wèn) 題的特例，也可以看成題的特例，也可以看成0

21、-1規(guī)劃問(wèn)題規(guī)劃問(wèn)題. ij c 返 回 導(dǎo) 航 優(yōu)優(yōu) 化化 建建 模模 1. 指派問(wèn)題的數(shù)學(xué)表達(dá)式指派問(wèn)題的數(shù)學(xué)表達(dá)式 設(shè)變量為設(shè)變量為 ,當(dāng)?shù)诋?dāng)?shù)?個(gè)人作第個(gè)人作第 項(xiàng)工作時(shí)，項(xiàng)工作時(shí)， , 否則否則 . 因此，相應(yīng)的線(xiàn)性規(guī)劃問(wèn)題為因此，相應(yīng)的線(xiàn)性規(guī)劃問(wèn)題為 11 1 1 min 1,1, 2,( 1,1, 2,() 01,1, 2, . mn ijij ij n ij j n ij i ij c x xin xjn xjn ； (5) s.t. ，每 個(gè) 人 做 一 項(xiàng) 工 作 ) (6) 每 項(xiàng) 工 作 有 一 個(gè) 人 去 做 (7) 或 ( 8) ij xij 1 ij x 0 ij

22、 x 優(yōu)優(yōu) 化化 建建 模模 2. 指派問(wèn)題的求解過(guò)程指派問(wèn)題的求解過(guò)程 分別用分別用LINDO軟件和軟件和LINGO軟件求解指派問(wèn)軟件求解指派問(wèn) 題，并對(duì)兩種軟件的求解方法與各自的優(yōu)缺點(diǎn)進(jìn)題，并對(duì)兩種軟件的求解方法與各自的優(yōu)缺點(diǎn)進(jìn) 行比較行比較. 例例7.4（繼例（繼例7.3） 考慮例考慮例7.3中中 的情況的情況,即即 6個(gè)人做個(gè)人做6項(xiàng)工作的最優(yōu)指派問(wèn)題，其收益矩陣如項(xiàng)工作的最優(yōu)指派問(wèn)題，其收益矩陣如 表表7-2所示所示. 6n 優(yōu)優(yōu) 化化 建建 模模 ! Assignment model ! Maximize valve of assignments max 20 x11 + 15x1

23、2 + 16x13 + 5x14 + 4x15 + 7x16 + 17x21 + 15x22 + 33x23 + 12x24 + 8x25 + 6x26 + 9x31 + 12x32 + 18x33 + 16x34 + 30 x35 + 13x36 + 12x41 + 8x42 + 11x43 + 27x44 + 19x45 + 14x46 - 99x51 + 7x52 + 10 x53 + 21x54 + 10 x55 + 32x56 - 99x61 - 99x62 - 99x63 + 6x64 + 11x65 + 13x66 subject to 解：解：與運(yùn)輸問(wèn)題一樣，先用與運(yùn)輸問(wèn)題一樣

24、，先用LINDO軟件求解軟件求解. 給出給出LINGO程序，程序名程序，程序名exam0704.ltx 優(yōu)優(yōu) 化化 建建 模模 ! Each person must be assigned to some job x11 + x12 + x13 + x14 + x15 + x16 = 1 x21 + x22 + x23 + x24 + x25 + x26 = 1 x31 + x32 + x33 + x34 + x35 + x36 = 1 x41 + x42 + x43 + x44 + x45 + x46 = 1 x51 + x52 + x53 + x54 + x55 + x56 = 1 x61

25、 + x62 + x63 + x64 + x65 + x66 = 1 ! Each job must receive an assignment x11 + x21 + x31 + x41 + x51 + x61 = 1 x12 + x22 + x32 + x42 + x52 + x62 = 1 x13 + x23 + x33 + x43 + x53 + x63 = 1 x14 + x24 + x34 + x44 + x54 + x64 = 1 x15 + x25 + x35 + x45 + x55 + x65 = 1 x16 + x26 + x36 + x46 + x56 + x66 = 1

26、 end 優(yōu)優(yōu) 化化 建建 模模 在上述程序中，在上述程序中， x51, x61, x62, x63前的系數(shù)均前的系數(shù)均 為為-99, 這是因?yàn)槟橙藷o(wú)法做某項(xiàng)工作可以某人做該這是因?yàn)槟橙藷o(wú)法做某項(xiàng)工作可以某人做該 項(xiàng)工作的收益是項(xiàng)工作的收益是 , 在計(jì)算中通常取一個(gè)較大的負(fù)在計(jì)算中通常取一個(gè)較大的負(fù) 數(shù)就可以數(shù)就可以. 上述程序也沒(méi)有說(shuō)明決策變量上述程序也沒(méi)有說(shuō)明決策變量 是是0-1型變量型變量, 這是因?yàn)閷?duì)于此類(lèi)問(wèn)題線(xiàn)性規(guī)劃理論已保證了變量這是因?yàn)閷?duì)于此類(lèi)問(wèn)題線(xiàn)性規(guī)劃理論已保證了變量 的取值只可能是的取值只可能是0或或1. x x LINDO軟件給出的計(jì)算結(jié)果如下（只列出非軟件給出的計(jì)算結(jié)果

27、如下（只列出非 零變量）零變量）: 優(yōu)優(yōu) 化化 建建 模模 OBJECTIVE FUNCTION VALUE 1) 135.0000 VARIABLE VALUE REDUCED COST X11 1.000000 0.000000 X23 1.000000 0.000000 X32 1.000000 0.000000 X44 1.000000 0.000000 X56 1.000000 0.000000 X65 1.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 優(yōu)優(yōu) 化化 建建 模模 2) 0.000000 3.000000 3) 0.00

28、0000 15.000000 5) 0.000000 -4.000000 7) 0.000000 -19.000000 8) 0.000000 17.000000 9) 0.000000 12.000000 10) 0.000000 18.000000 11) 0.000000 31.000000 12) 0.000000 30.000000 13) 0.000000 32.000000 NO. ITERATIONS= 20 優(yōu)優(yōu) 化化 建建 模模 即第即第1個(gè)人做第個(gè)人做第1項(xiàng)工作，第項(xiàng)工作，第2個(gè)人做第個(gè)人做第3項(xiàng)工作項(xiàng)工作, 第第3個(gè)人做第個(gè)人做第2項(xiàng)工作，第項(xiàng)工作，第4個(gè)人做第個(gè)人做第

29、4項(xiàng)工作，第項(xiàng)工作，第5 個(gè)人做第個(gè)人做第6項(xiàng)工作，第項(xiàng)工作，第6個(gè)人做第個(gè)人做第5項(xiàng)工作項(xiàng)工作. 總效益值總效益值 為為135. 下面用下面用LINGO程序再求解此問(wèn)題，程序中仍然程序再求解此問(wèn)題，程序中仍然 用到集、數(shù)據(jù)段和循環(huán)函數(shù)用到集、數(shù)據(jù)段和循環(huán)函數(shù). 寫(xiě)出相應(yīng)的寫(xiě)出相應(yīng)的LINGO程序，程序名程序，程序名exam0704.lg4. MODEL: 1! Assignment Problem Model; 2sets: 3 Flight/1.6/; 4 Assign(Flight, Flight): c, x; 優(yōu)優(yōu) 化化 建建 模模 5endsets 6! Here is incom

30、e matrix; 7data: 8 c = 20 15 16 5 4 7 9 17 15 33 12 8 6 10 9 12 18 16 30 13 11 12 8 11 27 19 14 12 -99 7 10 21 10 32 13 -99 -99 -99 6 11 13; 14enddata 15 優(yōu)優(yōu) 化化 建建 模模 16! Maximize valve of assignments; 17max = sum(Assign: c*x); 18for(Flight(i): 19! Each i must be assigned to some j; 20 sum(Flight(j):

31、 x(i,j) = 1; 21! Each I must receive an assignment; 22 sum(Flight(j): x(j,i) = 1; 23); END 優(yōu)優(yōu) 化化 建建 模模 程序中第程序中第12 13行中的行中的-99意義與意義與LINDO程序程序 中的意義相同，當(dāng)某人無(wú)法做某項(xiàng)工作時(shí)，取一個(gè)中的意義相同，當(dāng)某人無(wú)法做某項(xiàng)工作時(shí)，取一個(gè) 數(shù)值較大的負(fù)值數(shù)值較大的負(fù)值. LINGO軟件計(jì)算結(jié)果如下（只列出非零變量）軟件計(jì)算結(jié)果如下（只列出非零變量）: Global optimal solution found at iteration: 0 Objective v

32、alue: 135.0000 Variable Value Reduced Cost X( 1, 1) 1.000000 0.000000 X( 2, 3) 1.000000 0.000000 X( 3, 2) 1.000000 0.000000 X( 4, 4) 1.000000 0.000000 X( 5, 6) 1.000000 0.000000 X( 6, 5) 1.000000 0.000000 優(yōu)優(yōu) 化化 建建 模模 從上述兩個(gè)例子，可以看出從上述兩個(gè)例子，可以看出LINGO軟件在處軟件在處 理問(wèn)題方面要大優(yōu)于理問(wèn)題方面要大優(yōu)于LINDO軟件，而且便于推軟件，而且便于推 廣，只是在

33、編程方面，廣，只是在編程方面，LINGO程序的編寫(xiě)稍復(fù)雜程序的編寫(xiě)稍復(fù)雜 一些一些.在后面的問(wèn)題求解中，絕大多數(shù)的求解方法在后面的問(wèn)題求解中，絕大多數(shù)的求解方法 是采用是采用LINGO軟件計(jì)算軟件計(jì)算. 對(duì)于指派問(wèn)題，也可以考慮人數(shù)不工作數(shù)不對(duì)于指派問(wèn)題，也可以考慮人數(shù)不工作數(shù)不 相等的情況，和考慮支付最小的情況相等的情況，和考慮支付最小的情況.第一章的例第一章的例 1.5“混合泳接力隊(duì)員選拔問(wèn)題混合泳接力隊(duì)員選拔問(wèn)題”就是屬于這一類(lèi)就是屬于這一類(lèi) 情情 況況. 優(yōu)優(yōu) 化化 建建 模模 例例7.5（繼例（繼例1.5）用）用LINGO軟件求解例軟件求解例1.5. 解：解：在第二章的例在第二章的例

34、2.7給出了該問(wèn)題的給出了該問(wèn)題的LINDO軟軟 件求解方法，這里給出件求解方法，這里給出LINGO軟件的求解方法，讀軟件的求解方法，讀 者可根據(jù)問(wèn)題的求解過(guò)程來(lái)考查兩種軟件求解問(wèn)題的者可根據(jù)問(wèn)題的求解過(guò)程來(lái)考查兩種軟件求解問(wèn)題的 方法，以及每種軟件各自的特點(diǎn)方法，以及每種軟件各自的特點(diǎn). 為了便于編寫(xiě)程序，將為了便于編寫(xiě)程序，將5名隊(duì)員的名隊(duì)員的4種泳姿的百米種泳姿的百米 平均成績(jī)重新列在表平均成績(jī)重新列在表7-3中中. 優(yōu)優(yōu) 化化 建建 模模 按第按第1章所列的規(guī)劃問(wèn)題（第章中的式章所列的規(guī)劃問(wèn)題（第章中的式 (1.25) 式式(1.28)）寫(xiě)出相應(yīng)的）寫(xiě)出相應(yīng)的LINGO程序，程序， 程

35、序名：程序名：exam0705.lg4. MODEL: 1! 5 persons and 4 jobs Assignment Problem; 2sets: 3 Person /1.5/; 4 Job /1.4/; 5 Assign( Person, Job) : c, x; 6endsets 7! Here are the parameters; 8data: 優(yōu)優(yōu) 化化 建建 模模 9 c = 66.8, 75.6, 87, 58.6, 10 57.2, 66, 66.4, 53, 11 78, 67.8, 84.6, 59.4, 12 70, 74.2, 69.6, 57.2, 13 6

36、7.4, 71, 83.8, 62.4; 14enddata 15! The objective; 16OBJ min = sum( Assign: c * x); 17! The supply constraints; 18for( Person(i): SUP 19 sum( Job(j): x(i,j) = 1); 20! The demand constraints; 21for( Job(j): DEM 22 sum( Person(i): x(i,j) = 1); END 該程序同樣沒(méi)有限制是該程序同樣沒(méi)有限制是01型變量型變量.ij x 優(yōu)優(yōu) 化化 建建 模模 下面列出下面列出L

37、INGO軟件計(jì)算結(jié)果（僅保留非零變軟件計(jì)算結(jié)果（僅保留非零變 量）量）: Global optimal solution found at iteration: 9 Objective value: 253.2000 Variable Value Reduced Cost X( 1, 4) 1.000000 0.000000 X( 2, 1) 1.000000 0.000000 X( 3, 2) 1.000000 0.000000 X( 4, 3) 1.000000 0.000000 Row Slack or Surplus Dual Price OB J 253.2000 -1.000000

38、 SUP( 5) 1.000000 0.000000 即甲游自由泳，乙游蝶泳，丙游仰泳，丁游蛙泳即甲游自由泳，乙游蝶泳，丙游仰泳，丁游蛙泳,沒(méi)有被選拔沒(méi)有被選拔 上上.平均成績(jī)?yōu)槠骄煽?jī)?yōu)? 4132. 優(yōu)優(yōu) 化化 建建 模模 7.1.3 轉(zhuǎn)運(yùn)問(wèn)題轉(zhuǎn)運(yùn)問(wèn)題 所謂轉(zhuǎn)運(yùn)問(wèn)題所謂轉(zhuǎn)運(yùn)問(wèn)題(Transshipment Problem)實(shí)質(zhì)上實(shí)質(zhì)上 是運(yùn)輸問(wèn)題的一種，其區(qū)別就在于不是將工廠生產(chǎn)是運(yùn)輸問(wèn)題的一種，其區(qū)別就在于不是將工廠生產(chǎn) 出的產(chǎn)品直接送的顧客手中，而是要經(jīng)過(guò)某些中間出的產(chǎn)品直接送的顧客手中，而是要經(jīng)過(guò)某些中間 環(huán)節(jié)，如倉(cāng)庫(kù)、配送中心等環(huán)節(jié)，如倉(cāng)庫(kù)、配送中心等.圖圖7-2表示的是表示的是3

39、水平分水平分 配（即有一個(gè)中間環(huán)節(jié)）的轉(zhuǎn)運(yùn)問(wèn)題配（即有一個(gè)中間環(huán)節(jié)）的轉(zhuǎn)運(yùn)問(wèn)題. 返 回 導(dǎo) 航 優(yōu)優(yōu) 化化 建建 模模 1.轉(zhuǎn)運(yùn)問(wèn)題的數(shù)學(xué)表達(dá)式轉(zhuǎn)運(yùn)問(wèn)題的數(shù)學(xué)表達(dá)式 優(yōu)優(yōu) 化化 建建 模模 122 11 1 1 min ; (9) s.t. , 1,2,() (10) ln ijjkjk jk l iji j i xc x xaim x 運(yùn)出量應(yīng)不大于生產(chǎn)量 12 11 2 1 12 , 1,2, ,() (11) , 1,2,() (12) 0,0. mn jjk ik l jkk j xjl xbkn xx 運(yùn)入量應(yīng)等于運(yùn)出量 運(yùn)入量應(yīng)等于需求量 優(yōu)優(yōu) 化化 建建 模模 1.轉(zhuǎn)運(yùn)問(wèn)題的求

40、解方法轉(zhuǎn)運(yùn)問(wèn)題的求解方法 以一個(gè)例子為例，給出求解轉(zhuǎn)運(yùn)問(wèn)題的兩種以一個(gè)例子為例，給出求解轉(zhuǎn)運(yùn)問(wèn)題的兩種 求解方法求解方法. 例例7.6（轉(zhuǎn)運(yùn)問(wèn)題）設(shè)有兩個(gè)工廠（轉(zhuǎn)運(yùn)問(wèn)題）設(shè)有兩個(gè)工廠A, B, 產(chǎn)量分別產(chǎn)量分別 為為9, 8個(gè)單位個(gè)單位. 四個(gè)顧客四個(gè)顧客1, 2, 3, 4, 需求量分別為需求量分別為3, 5, 4, 5. 和三個(gè)倉(cāng)庫(kù)和三個(gè)倉(cāng)庫(kù)x, y, z. 其中工廠到倉(cāng)庫(kù)、倉(cāng)庫(kù)到顧其中工廠到倉(cāng)庫(kù)、倉(cāng)庫(kù)到顧 客的運(yùn)費(fèi)單價(jià)分別由表客的運(yùn)費(fèi)單價(jià)分別由表7-4所示所示.試求總運(yùn)費(fèi)最少的試求總運(yùn)費(fèi)最少的 運(yùn)輸方案，以及總運(yùn)費(fèi)運(yùn)輸方案，以及總運(yùn)費(fèi). 優(yōu)優(yōu) 化化 建建 模模 AB1234 x15 y2

41、 z 表表7-4 工廠到倉(cāng)庫(kù)工廠到倉(cāng)庫(kù) 、倉(cāng)庫(kù)到顧客的運(yùn)費(fèi)單價(jià)、倉(cāng)庫(kù)到顧客的運(yùn)費(fèi)單價(jià) 說(shuō)明：其中說(shuō)明：其中-表示兩地?zé)o道路通行表示兩地?zé)o道路通行. 解：解：寫(xiě)出相應(yīng)的寫(xiě)出相應(yīng)的LINGO程序，程序名：程序，程序名： exam0706a.lg4. 優(yōu)優(yōu) 化化 建建 模模 MODEL: 1! 2 plants, 3 warehouses and 4 customers 2 Transshipment Problem; 3sets: 4 Plant /A, B/ : produce; 5 Warhouse /x, y, z/; 6 Customer /1.4/ : require; 7 LinkI

42、( Plant, Warhouse) : cI, xI; 8 LinkII ( Warhouse, Customer) : cII, xII; 9endsets 10! Here are the parameters; 11data: 12 produce = 9, 8; 優(yōu)優(yōu) 化化 建建 模模 13 require = 3, 5, 4, 5; 14 cI = 1, 2, 100, 15 3, 1, 2; 16 cII = 5, 7, 100, 100, 17 9, 6, 7, 100, 18 100, 8, 7, 4; 19enddata 20! The objective; 21OBJ m

43、in = sum(LinkI: cI * xI)+sum(LinkII: cII * xII); 22! The supply constraints; 23for( Plant(i): SUP 24 sum( Warhouse(j): xI(i,j) = produce(i); 優(yōu)優(yōu) 化化 建建 模模 25! The warhouse constraints; 26for( Warhouse(j): MID 27 sum( Plant(i): xI(i,j)=sum( Customer(k): xII(j,k); 28! The demand constraints; 29for( Cust

44、omer(k): DEM 30 sum( Warhouse(j): xII(j,k) = require(k); END 在上述程序中，由在上述程序中，由14至至15行定義的行定義的cI是工廠是工廠 到倉(cāng)庫(kù)的運(yùn)費(fèi)，由到倉(cāng)庫(kù)的運(yùn)費(fèi)，由16至至18行定義的行定義的cII是倉(cāng)庫(kù)到顧是倉(cāng)庫(kù)到顧 客的運(yùn)費(fèi)客的運(yùn)費(fèi).我們的目標(biāo)是求最小運(yùn)費(fèi)，因此當(dāng)兩點(diǎn)無(wú)我們的目標(biāo)是求最小運(yùn)費(fèi)，因此當(dāng)兩點(diǎn)無(wú) 道路時(shí)，認(rèn)為是運(yùn)費(fèi)無(wú)窮大道路時(shí)，認(rèn)為是運(yùn)費(fèi)無(wú)窮大.為了便于計(jì)算，只要取為了便于計(jì)算，只要取 較大的數(shù)值就可以了，這里的取值為較大的數(shù)值就可以了，這里的取值為100. 優(yōu)優(yōu) 化化 建建 模模 程序的第程序的第21行表示目標(biāo)

45、函數(shù)（行表示目標(biāo)函數(shù)（7，9）, 第第23, 24 行表示約束條件行表示約束條件(7.10),第第26, 27行表示約束條件行表示約束條件(11) , 第第29, 30行表示約束條件行表示約束條件(7.12). LINGO軟件的計(jì)算結(jié)果（僅保留非零變量）如軟件的計(jì)算結(jié)果（僅保留非零變量）如 下下: Global optimal solution found at iteration: 9 Objective value: 121.0000 Variable Value Reduced Cost XI( A, X) 3.000000 0.000000 XI( A, Y) 6.000000 0.0

46、00000 XI( B, Y) 3.000000 0.000000 優(yōu)優(yōu) 化化 建建 模模 XI( B, Z) 5.000000 0.000000 XII( X, 1) 3.000000 0.000000 XII( Y, 2) 5.000000 0.000000 XII( Y, 3) 4.000000 0.000000 XII( Z, 4) 5.000000 0.000000 即工廠即工廠A向倉(cāng)庫(kù)向倉(cāng)庫(kù)x, y, z分別運(yùn)輸分別運(yùn)輸3, 6, 0個(gè)單個(gè)單 位，工廠位，工廠B向倉(cāng)庫(kù)向倉(cāng)庫(kù)x, y, z分別運(yùn)輸分別運(yùn)輸0, 3, 5個(gè)單位，個(gè)單位， 倉(cāng)庫(kù)倉(cāng)庫(kù)x向顧客向顧客1運(yùn)輸運(yùn)輸3個(gè)單位，倉(cāng)庫(kù)個(gè)

47、單位，倉(cāng)庫(kù)y向顧客向顧客2, 3分分 別運(yùn)輸別運(yùn)輸5, 4個(gè)單位，倉(cāng)庫(kù)個(gè)單位，倉(cāng)庫(kù)z向顧客向顧客4運(yùn)輸運(yùn)輸5個(gè)單位個(gè)單位. 總運(yùn)費(fèi)為總運(yùn)費(fèi)為121個(gè)單位個(gè)單位. 優(yōu)優(yōu) 化化 建建 模模 如果將轉(zhuǎn)運(yùn)問(wèn)題看成運(yùn)輸問(wèn)題，可以得到另一如果將轉(zhuǎn)運(yùn)問(wèn)題看成運(yùn)輸問(wèn)題，可以得到另一 種程序的編寫(xiě)方法，程序名：種程序的編寫(xiě)方法，程序名： exam0706b.lg4. MODEL: 1! 2 plants, 3 warehouses and 4 customers 2 Transshipment Problem; 3sets: 4 Plant /A,B/ : produce; 5 Warhouse /x,y,z/

48、; 6 Customer /1.4/ : require; 7 Link ( Plant, Warhouse, Customer) : poss, cost, x; 8endsets 9! Here are the parameters; 優(yōu)優(yōu) 化化 建建 模模 10data: 11 produce = 9, 8; 12 require = 3, 5, 4, 5; 13 poss = 1, 1, 0, 0, 14 1, 1, 1, 0, 15 0, 0, 0, 0, 16 1, 1, 0, 0, 17 1, 1, 1, 0, 18 0, 1, 1, 1; 19 cost = 6, 8, 0,

49、0, 20 11, 8, 9, 0, 21 0, 0, 0, 0, 22 8,10, 0, 0, 優(yōu)優(yōu) 化化 建建 模模 23 10, 7, 8, 0, 24 0,10, 9, 6; 25enddata 26! The objective; 27OBJ min = sum( Link: poss * cost * x); 28! The supply constraints; 29for(Plant(i): SUP 30 sum(Warhouse(j): 31 sum(Customer(k): poss(i,j,k)*x(i,j,k)=1; 24!For city i, except the

50、base (city 1); 25for(cities(i) | i #gt# 1 : 優(yōu)優(yōu) 化化 建建 模模 26! It must be entered; 27 sum(cities(j)| j #ne# i: x(j,i)=1; 28! level(j)=levle(i)+1, if we link j and i; 29 for(cities(j)| j #gt# 1 #and# j #ne# i : 30 level(j) = level(i) + x(i,j) 31 - (n-2)*(1-x(i,j) + (n-3)*x(j,i); 32 ); 33! The level of c

51、ity is at least 1 but no more n-1, 34 and is 1 if it links to base (city 1); 35 bnd(1,level(i),999999); 36 level(i)= level(i) + x(i,j) 31 - (n-2)*(1-x(i,j) + (n-3)*x(j,i); 32 ); 33); 優(yōu)優(yōu) 化化 建建 模模 34! Make the xs 0/1; 35for(link : bin(x); 36! For the first and last stop; 37for(cities(i) | i #gt# 1 : 3

52、8 level(i)=1+(n-2)*x(i,1); 40); END 水平變量水平變量(level)仍然是用來(lái)保證所選的邊除第仍然是用來(lái)保證所選的邊除第1 點(diǎn)外不構(gòu)成圈的點(diǎn)外不構(gòu)成圈的.計(jì)算結(jié)果如下：計(jì)算結(jié)果如下： 優(yōu)優(yōu) 化化 建建 模模 Global optimal solution found at iteration: 90 Objective value: 73.00000 Variable Value Reduced Cost X( 1, 2) 1.000000 8.000000 X( 2, 6) 1.000000 8.000000 X( 3, 1) 1.000000 5.0000

53、00 X( 4, 3) 1.000000 7.000000 X( 5, 4) 1.000000 3.000000 X( 6, 9) 1.000000 8.000000 X( 7, 10) 1.000000 11.00000 X( 8, 5) 1.000000 6.000000 X( 9, 7) 1.000000 6.000000 X( 10, 8) 1.000000 11.00000 優(yōu)優(yōu) 化化 建建 模模 旅行商經(jīng)過(guò)旅行商經(jīng)過(guò)10 個(gè)城鎮(zhèn)的最短距離為個(gè)城鎮(zhèn)的最短距離為73公里，其連公里，其連 接情況如圖接情況如圖7-11所示所示. 優(yōu)優(yōu) 化化 建建 模模 7.4 7.4 計(jì)劃評(píng)審方法和關(guān)鍵路

54、線(xiàn)法計(jì)劃評(píng)審方法和關(guān)鍵路線(xiàn)法 本節(jié)內(nèi)容導(dǎo)航本節(jié)內(nèi)容導(dǎo)航 本節(jié)概述本節(jié)概述 7.4.1計(jì)劃網(wǎng)絡(luò)圖計(jì)劃網(wǎng)絡(luò)圖 7.4.2計(jì)劃網(wǎng)絡(luò)圖的計(jì)算計(jì)劃網(wǎng)絡(luò)圖的計(jì)算 7.4.3關(guān)鍵路線(xiàn)與計(jì)劃網(wǎng)絡(luò)圖優(yōu)化關(guān)鍵路線(xiàn)與計(jì)劃網(wǎng)絡(luò)圖優(yōu)化 7.4.4 完成作業(yè)期望和實(shí)現(xiàn)事件概率完成作業(yè)期望和實(shí)現(xiàn)事件概率 優(yōu)優(yōu) 化化 建建 模模 本節(jié)內(nèi)容概述本節(jié)內(nèi)容概述 計(jì)劃評(píng)審方法（計(jì)劃評(píng)審方法（Program Evaluation and Review Technique, 簡(jiǎn)寫(xiě)為簡(jiǎn)寫(xiě)為PERT）和關(guān)鍵路線(xiàn)法（）和關(guān)鍵路線(xiàn)法（Critial Path Method, 簡(jiǎn)寫(xiě)為簡(jiǎn)寫(xiě)為CPM）是網(wǎng)絡(luò)分析的重要組成部分，）是網(wǎng)絡(luò)分析的重要組成部

55、分， 它廣泛用系統(tǒng)分析和項(xiàng)目管理它廣泛用系統(tǒng)分析和項(xiàng)目管理.計(jì)劃評(píng)審與關(guān)鍵路線(xiàn)方計(jì)劃評(píng)審與關(guān)鍵路線(xiàn)方 法是在法是在20世紀(jì)世紀(jì)50年代提出并發(fā)展起來(lái)的，年代提出并發(fā)展起來(lái)的，1956年，美國(guó)年，美國(guó) 杜邦公司為了協(xié)調(diào)企業(yè)不同業(yè)務(wù)部門(mén)的系統(tǒng)規(guī)劃，提出杜邦公司為了協(xié)調(diào)企業(yè)不同業(yè)務(wù)部門(mén)的系統(tǒng)規(guī)劃，提出 了關(guān)鍵路線(xiàn)法了關(guān)鍵路線(xiàn)法.1958年，美國(guó)海軍武裝部在研制年，美國(guó)海軍武裝部在研制“北極北極 星星”導(dǎo)彈計(jì)劃時(shí)，由于導(dǎo)彈的研制系統(tǒng)過(guò)于龐大、復(fù)雜，導(dǎo)彈計(jì)劃時(shí)，由于導(dǎo)彈的研制系統(tǒng)過(guò)于龐大、復(fù)雜， 為找到一種有效的管理方法，設(shè)計(jì)了計(jì)劃評(píng)審方法為找到一種有效的管理方法，設(shè)計(jì)了計(jì)劃評(píng)審方法.由由 于于PERT

56、與與CPM即有著相同的目標(biāo)應(yīng)用，又有很多相同即有著相同的目標(biāo)應(yīng)用，又有很多相同 的術(shù)語(yǔ)，這兩種方法已合并為一種方法，在國(guó)外稱(chēng)為的術(shù)語(yǔ)，這兩種方法已合并為一種方法，在國(guó)外稱(chēng)為 PERT/CPM，在國(guó)內(nèi)稱(chēng)為統(tǒng)籌方法，在國(guó)內(nèi)稱(chēng)為統(tǒng)籌方法(Scheduling Method). 返 回 導(dǎo) 航 優(yōu)優(yōu) 化化 建建 模模 7.4.1計(jì)劃網(wǎng)絡(luò)圖計(jì)劃網(wǎng)絡(luò)圖 例例7.19 某項(xiàng)目工程由某項(xiàng)目工程由11項(xiàng)作業(yè)組成（分別用項(xiàng)作業(yè)組成（分別用 代號(hào)代號(hào)A, B, , J, K表示），其計(jì)劃完成時(shí)間及作業(yè)表示），其計(jì)劃完成時(shí)間及作業(yè) 間相互關(guān)系如表間相互關(guān)系如表7-8所示，求完成該項(xiàng)目的最短時(shí)所示，求完成該項(xiàng)目的最短時(shí)

57、 間間. 例例7.19就是計(jì)劃評(píng)審方法或關(guān)鍵路線(xiàn)法需要解決的問(wèn)題就是計(jì)劃評(píng)審方法或關(guān)鍵路線(xiàn)法需要解決的問(wèn)題. 返 回 導(dǎo) 航 優(yōu)優(yōu) 化化 建建 模模 1. 計(jì)劃網(wǎng)絡(luò)圖的概念計(jì)劃網(wǎng)絡(luò)圖的概念 定義定義 7.11 稱(chēng)任何消耗時(shí)間或資源的行動(dòng)為作稱(chēng)任何消耗時(shí)間或資源的行動(dòng)為作 業(yè)業(yè).稱(chēng)作業(yè)的開(kāi)始或結(jié)束為事件，事件本身不消耗稱(chēng)作業(yè)的開(kāi)始或結(jié)束為事件，事件本身不消耗 資源資源. 在計(jì)劃網(wǎng)絡(luò)圖中通常用圓圈表示事件，用箭在計(jì)劃網(wǎng)絡(luò)圖中通常用圓圈表示事件，用箭 線(xiàn)表示事件，如圖線(xiàn)表示事件，如圖7-12所示，所示，1, 2, 3表示事件，表示事件，A, B表示作業(yè)表示作業(yè).由這種方法畫(huà)出的網(wǎng)絡(luò)圖稱(chēng)為計(jì)劃由這種方

58、法畫(huà)出的網(wǎng)絡(luò)圖稱(chēng)為計(jì)劃 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖. 優(yōu)優(yōu) 化化 建建 模模 定義定義7.12 在計(jì)劃網(wǎng)絡(luò)圖中，稱(chēng)從是初始事在計(jì)劃網(wǎng)絡(luò)圖中，稱(chēng)從是初始事 件到最終事件的由各項(xiàng)作業(yè)連貫組成的一條路為件到最終事件的由各項(xiàng)作業(yè)連貫組成的一條路為 路線(xiàn)。具有累計(jì)作業(yè)時(shí)間最長(zhǎng)的路線(xiàn)稱(chēng)為關(guān)鍵路路線(xiàn)。具有累計(jì)作業(yè)時(shí)間最長(zhǎng)的路線(xiàn)稱(chēng)為關(guān)鍵路 線(xiàn)。線(xiàn)。 由此看來(lái)，例由此看來(lái)，例7.19就是求相應(yīng)的計(jì)劃網(wǎng)絡(luò)圖就是求相應(yīng)的計(jì)劃網(wǎng)絡(luò)圖 中的關(guān)鍵路線(xiàn)。中的關(guān)鍵路線(xiàn)。 2. 建立計(jì)劃網(wǎng)絡(luò)圖應(yīng)注意的問(wèn)題建立計(jì)劃網(wǎng)絡(luò)圖應(yīng)注意的問(wèn)題 (1) 任何作業(yè)在網(wǎng)絡(luò)中用唯一的箭線(xiàn)表示，任何作業(yè)任何作業(yè)在網(wǎng)絡(luò)中用唯一的箭線(xiàn)表示，任何作業(yè) 其終點(diǎn)事件的編號(hào)

59、必須大于其起點(diǎn)事件其終點(diǎn)事件的編號(hào)必須大于其起點(diǎn)事件. 優(yōu)優(yōu) 化化 建建 模模 (2) 兩個(gè)事件之間只能畫(huà)一條箭線(xiàn)，表示一兩個(gè)事件之間只能畫(huà)一條箭線(xiàn)，表示一 項(xiàng)作業(yè)項(xiàng)作業(yè).對(duì)于具有相同開(kāi)始和結(jié)束事件的兩項(xiàng)以上對(duì)于具有相同開(kāi)始和結(jié)束事件的兩項(xiàng)以上 作業(yè)，要引進(jìn)虛事件和虛作業(yè)作業(yè)，要引進(jìn)虛事件和虛作業(yè). (3) 任何計(jì)劃網(wǎng)絡(luò)圖應(yīng)有唯一的最初事件和唯任何計(jì)劃網(wǎng)絡(luò)圖應(yīng)有唯一的最初事件和唯 一的最終事件一的最終事件. (4) 計(jì)劃網(wǎng)絡(luò)圖不允許出現(xiàn)回路計(jì)劃網(wǎng)絡(luò)圖不允許出現(xiàn)回路. (5) 計(jì)劃網(wǎng)絡(luò)圖的畫(huà)法一般是從左到右，從上計(jì)劃網(wǎng)絡(luò)圖的畫(huà)法一般是從左到右，從上 到下，盡量作到清晰美觀，避免箭頭交叉到下，盡量

60、作到清晰美觀，避免箭頭交叉. 優(yōu)優(yōu) 化化 建建 模模 7.4.2計(jì)劃網(wǎng)絡(luò)圖的計(jì)算計(jì)劃網(wǎng)絡(luò)圖的計(jì)算 以例以例7-19的求解過(guò)程介紹計(jì)劃網(wǎng)絡(luò)圖的計(jì)算的求解過(guò)程介紹計(jì)劃網(wǎng)絡(luò)圖的計(jì)算 方法方法. 1. 建立計(jì)劃網(wǎng)絡(luò)圖建立計(jì)劃網(wǎng)絡(luò)圖 首先建立計(jì)劃網(wǎng)絡(luò)圖首先建立計(jì)劃網(wǎng)絡(luò)圖.按照上述規(guī)則，建立例按照上述規(guī)則，建立例 7.19的計(jì)劃網(wǎng)絡(luò)圖，如圖的計(jì)劃網(wǎng)絡(luò)圖，如圖7-13所示所示. 返 回 導(dǎo) 航 優(yōu)優(yōu) 化化 建建 模模 2. 寫(xiě)出相應(yīng)的規(guī)劃問(wèn)題寫(xiě)出相應(yīng)的規(guī)劃問(wèn)題 設(shè)是事件的開(kāi)始時(shí)間，設(shè)是事件的開(kāi)始時(shí)間， 為最初事件，為為最初事件，為 最終事件最終事件.希望總的工期最短，即極小化希望總的工期最短，即極小化 .設(shè)