計(jì)劃評(píng)審方法和關(guān)鍵路線法

1、優(yōu)優(yōu) 化化 建建 模模7.4 7.4 計(jì)劃評(píng)審方法和關(guān)鍵路線法計(jì)劃評(píng)審方法和關(guā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)鍵路線與計(jì)劃網(wǎng)絡(luò)圖優(yōu)化關(guā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)鍵路線法（）和關(guān)鍵路線法（critial path method, 簡(jiǎn)寫(xiě)為簡(jiǎn)寫(xiě)為cpm）是

2、網(wǎng)絡(luò)分析的重要組成部分，）是網(wǎng)絡(luò)分析的重要組成部分，它廣泛用系統(tǒng)分析和項(xiàng)目管理它廣泛用系統(tǒng)分析和項(xiàng)目管理.計(jì)劃評(píng)審與關(guān)鍵路線方計(jì)劃評(píng)審與關(guā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)鍵路線法了關(guā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è)

3、計(jì)了計(jì)劃評(píng)審方法.由由于于pert與與cpm即有著相同的目標(biāo)應(yīng)用，又有很多相同即有著相同的目標(biāo)應(yīng)用，又有很多相同的術(shù)語(yǔ)，這兩種方法已合并為一種方法，在國(guó)外稱為的術(shù)語(yǔ)，這兩種方法已合并為一種方法，在國(guó)外稱為pert/cpm，在國(guó)內(nèi)稱為統(tǒng)籌方法，在國(guó)內(nèi)稱為統(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í)所示，求完成

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

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

6、編號(hào)必須大于其起點(diǎn)事件.優(yōu)優(yōu) 化化 建建 模模 (2) 兩個(gè)事件之間只能畫(huà)一條箭線，表示一兩個(gè)事件之間只能畫(huà)一條箭線，表示一項(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à)法一般是從左到右，從上到下，盡量作到清晰美觀，避免箭頭交叉到下，盡量作到清晰美觀，避免箭頭交叉.優(yōu)優(yōu) 化化 建建

7、模模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è)設(shè)是作業(yè)是作業(yè) 的計(jì)劃時(shí)間，因此，對(duì)于事件的計(jì)劃時(shí)間，因此，對(duì)于事件 與事

8、件與事件 有不等式：有不等式： ixi11nxxijt( , )i jijjiijxxt由此得到相應(yīng)的數(shù)學(xué)規(guī)劃問(wèn)由此得到相應(yīng)的數(shù)學(xué)規(guī)劃問(wèn)題題優(yōu)優(yōu) 化化 建建 模模 3. 問(wèn)題求解問(wèn)題求解 例例7.20(繼例繼例7.19) 用用lindo軟件求解例軟件求解例7.19 解：解： 按照數(shù)學(xué)規(guī)劃問(wèn)題（按照數(shù)學(xué)規(guī)劃問(wèn)題（7.37）-（7.39）編寫(xiě)）編寫(xiě)indo程序，程序名：程序，程序名：exam0720.ltxmin x8 - x1subject to2) x2 - x1 = 53) x3 - x1 = 104) x4 - x1 = 115) x5 - x2 = 4優(yōu)優(yōu) 化化 建建 模模6) x4 -

9、 x3 = 47) x5 - x3 = 08) x6 - x4 = 159) x6 - x5 = 2110) x7 - x5 = 2511) x8 - x5 = 3512) x7 - x6 = 013) x8 - x6 = 2014) x8 - x7 = 15end優(yōu)優(yōu) 化化 建建 模模lindo軟件的計(jì)算結(jié)果如下：軟件的計(jì)算結(jié)果如下：lp optimum found at step 9 objective function value 1) 51.00000 variable value reduced cost x8 51.000000 0.000000 x1 0.000000 0.000

10、000 x2 5.000000 0.000000 x3 10.000000 0.000000 x4 14.000000 0.000000 x5 10.000000 0.000000 x6 31.000000 0.000000 x7 36.000000 0.000000優(yōu)優(yōu) 化化 建建 模模row slack or surplus dual prices 2) 0.000000 0.000000 3) 0.000000 -1.000000 4) 3.000000 0.000000 5) 1.000000 0.000000 6) 0.000000 0.000000 7) 0.000000 -1.0

11、00000 8) 2.000000 0.000000 9) 0.000000 -1.000000 10) 1.000000 0.000000 11) 6.000000 0.000000 12) 5.000000 0.000000 13) 0.000000 -1.000000 14) 0.000000 0.000000 no. iterations= 9優(yōu)優(yōu) 化化 建建 模模 計(jì)算結(jié)果給出了各個(gè)項(xiàng)目的開(kāi)工時(shí)間，如計(jì)算結(jié)果給出了各個(gè)項(xiàng)目的開(kāi)工時(shí)間，如 , 則則作業(yè)作業(yè)a、b、c的開(kāi)工時(shí)間均是第的開(kāi)工時(shí)間均是第0天天; 作業(yè)作業(yè)e的開(kāi)的開(kāi)工時(shí)間是第工時(shí)間是第5天天; 則作業(yè)則作業(yè)d的開(kāi)工時(shí)間是第的開(kāi)

12、工時(shí)間是第10天天; 等等等等.每個(gè)作業(yè)只要按規(guī)定的時(shí)間開(kāi)工，整個(gè)項(xiàng)每個(gè)作業(yè)只要按規(guī)定的時(shí)間開(kāi)工，整個(gè)項(xiàng)目的最短工期為目的最短工期為51天天.10 x 25,x 310,x 盡管上述盡管上述lindo程序給出相應(yīng)的開(kāi)工時(shí)間和整個(gè)程序給出相應(yīng)的開(kāi)工時(shí)間和整個(gè)項(xiàng)目的最短工期，但統(tǒng)籌方法中許多有用的信息并沒(méi)項(xiàng)目的最短工期，但統(tǒng)籌方法中許多有用的信息并沒(méi)有得到，如項(xiàng)目的關(guān)鍵路徑、每個(gè)作業(yè)的最早開(kāi)工時(shí)有得到，如項(xiàng)目的關(guān)鍵路徑、每個(gè)作業(yè)的最早開(kāi)工時(shí)間、最遲開(kāi)工時(shí)間等間、最遲開(kāi)工時(shí)間等.因此，我們希望將程序編寫(xiě)的因此，我們希望將程序編寫(xiě)的稍微復(fù)雜一些，為我們提供更多的信息稍微復(fù)雜一些，為我們提供更多的信息.

13、優(yōu)優(yōu) 化化 建建 模模下面利用下面利用lingo軟件完成此項(xiàng)工作軟件完成此項(xiàng)工作.例例7.21 用用lingo軟件求解例軟件求解例7.19. 解：解： 按按 照數(shù)照數(shù) 學(xué)規(guī)學(xué)規(guī) 劃問(wèn)題劃問(wèn)題(7.37)-(7.39) 編編 寫(xiě)寫(xiě)lingo程序只有得到整程序只有得到整 優(yōu)優(yōu) 化化 建建 模模編寫(xiě)相應(yīng)的編寫(xiě)相應(yīng)的lingo程序，程序名：程序，程序名： exam0721.lg4model: 1sets: 2 events/1.8/: x; 3 operate(events, events)/ 4 1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8

14、5 /: s, t; 6endsets 7data: 8 t = 5 10 11 4 4 0 15 21 35 25 0 15 20; 9enddata 10min=sum(events : x); 11for(operate(i,j): s(i,j)=x(j)-x(i)-t(i,j); end優(yōu)優(yōu) 化化 建建 模模計(jì)算得到（只列出非零解）計(jì)算得到（只列出非零解）: variable value reduced cost x( 2) 5.000000 0.000000 x( 3) 10.00000 0.000000 x( 4) 14.00000 0.000000 x( 5) 10.00000

15、0.000000 x( 6) 31.00000 0.000000 x( 7) 35.00000 0.000000 x( 8) 51.00000 0.000000 s( 1, 4) 3.000000 0.000000 s( 2, 5) 1.000000 0.000000 s( 4, 6) 2.000000 0.000000 s( 5, 8) 6.000000 0.000000 s( 6, 7) 4.000000 0.000000 s( 7, 8) 1.000000 0.000000優(yōu)優(yōu) 化化 建建 模模 由此，可以得到所有作業(yè)的最早開(kāi)工時(shí)間和最遲由此，可以得到所有作業(yè)的最早開(kāi)工時(shí)間和最遲開(kāi)工時(shí)間

16、，如表開(kāi)工時(shí)間，如表7-9所示，方括號(hào)中第所示，方括號(hào)中第1個(gè)數(shù)字是最早個(gè)數(shù)字是最早開(kāi)工時(shí)間，第開(kāi)工時(shí)間，第2個(gè)數(shù)字是最遲開(kāi)工時(shí)間個(gè)數(shù)字是最遲開(kāi)工時(shí)間.優(yōu)優(yōu) 化化 建建 模模優(yōu)優(yōu) 化化 建建 模模 從上述表可以看出，當(dāng)最早開(kāi)工時(shí)間與最遲開(kāi)從上述表可以看出，當(dāng)最早開(kāi)工時(shí)間與最遲開(kāi)工時(shí)間相同時(shí)，對(duì)應(yīng)的作業(yè)在關(guān)鍵路線上，因此可工時(shí)間相同時(shí)，對(duì)應(yīng)的作業(yè)在關(guān)鍵路線上，因此可以畫(huà)出計(jì)劃網(wǎng)絡(luò)圖中的關(guān)鍵路線，如圖以畫(huà)出計(jì)劃網(wǎng)絡(luò)圖中的關(guān)鍵路線，如圖7-14粗線所粗線所示示.關(guān)鍵路線為關(guān)鍵路線為 13568.優(yōu)優(yōu) 化化 建建 模模4 將關(guān)鍵路線看成最長(zhǎng)路將關(guān)鍵路線看成最長(zhǎng)路 如果將關(guān)鍵路線看成最長(zhǎng)路，則可以按照求

17、最短如果將關(guān)鍵路線看成最長(zhǎng)路，則可以按照求最短路的方法（將求極小改為求極大）求出關(guān)鍵路線路的方法（將求極小改為求極大）求出關(guān)鍵路線 .設(shè)為設(shè)為 變量，當(dāng)作業(yè)變量，當(dāng)作業(yè) 位于關(guān)鍵路線上取位于關(guān)鍵路線上取1;否否則取則取0. 數(shù)學(xué)規(guī)劃問(wèn)題寫(xiě)成數(shù)學(xué)規(guī)劃問(wèn)題寫(xiě)成:ijx0 1( , )i j優(yōu)優(yōu) 化化 建建 模模例例7.22 用最長(zhǎng)路的方法求解例用最長(zhǎng)路的方法求解例7.19. 解：解： 按數(shù)學(xué)規(guī)劃按數(shù)學(xué)規(guī)劃(7.40)-(7.42)寫(xiě)出相應(yīng)的寫(xiě)出相應(yīng)的ingo程序，程序名：程序，程序名：exam0722.lg4.model: 1sets: 2 events/1.8/: d; 3 operate(ev

18、ents, events)/ 4 1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8 5 /: t, x; 6endsets 7data:優(yōu)優(yōu) 化化 建建 模模 8 t = 5 10 11 4 4 0 15 21 35 25 0 15 20; 9 d = 1 0 0 0 0 0 0 -1; 10enddata 11max=sum(operate : t*x); 12for(events(i): 13 sum(operate(i,j): x(i,j) - sum(operate(j,i): x(j,i) 14 =d(i); 15); end優(yōu)優(yōu)

19、 化化 建建 模模計(jì)算得到（只列出非零解計(jì)算得到（只列出非零解):objective value: 51.00000 variable value reduced cost x( 1, 3) 1.000000 0.000000 x( 3, 5) 1.000000 0.000000 x( 5, 6) 1.000000 0.000000 x( 6, 8) 1.000000 0.000000 即工期需要即工期需要51天，關(guān)鍵路線為天，關(guān)鍵路線為13568. 從上述計(jì)算過(guò)程可以看到，在兩種從上述計(jì)算過(guò)程可以看到，在兩種lingo程序中，第二程序中，第二個(gè)程序計(jì)算在計(jì)算最短工期、關(guān)鍵路線均比第一個(gè)程序方

20、便，個(gè)程序計(jì)算在計(jì)算最短工期、關(guān)鍵路線均比第一個(gè)程序方便，但在某些情況下，例如，需要優(yōu)化計(jì)劃網(wǎng)絡(luò)時(shí)，第一種程序但在某些情況下，例如，需要優(yōu)化計(jì)劃網(wǎng)絡(luò)時(shí)，第一種程序的編寫(xiě)方法可以更好地發(fā)揮出其優(yōu)點(diǎn)的編寫(xiě)方法可以更好地發(fā)揮出其優(yōu)點(diǎn).優(yōu)優(yōu) 化化 建建 模模7.4.3 關(guān)鍵路線與計(jì)劃網(wǎng)絡(luò)的優(yōu)化關(guān)鍵路線與計(jì)劃網(wǎng)絡(luò)的優(yōu)化 例例7.23 （關(guān)鍵路線與計(jì)劃網(wǎng)絡(luò)的優(yōu)化）假設(shè)例（關(guān)鍵路線與計(jì)劃網(wǎng)絡(luò)的優(yōu)化）假設(shè)例7.19中所列的工程要求在中所列的工程要求在49天內(nèi)完成天內(nèi)完成.為提前完成工為提前完成工期，有些作業(yè)需要加快進(jìn)度、縮短工期，而加快進(jìn)期，有些作業(yè)需要加快進(jìn)度、縮短工期，而加快進(jìn)度需要額外增加費(fèi)用度需要額外

21、增加費(fèi)用.表表7-10列出例列出例7-19中可縮短工中可縮短工期的所有作業(yè)和縮短一天額外增加的費(fèi)用期的所有作業(yè)和縮短一天額外增加的費(fèi)用.現(xiàn)在的問(wèn)現(xiàn)在的問(wèn)題是，如何安排作業(yè)才能使額外增加的總費(fèi)用最少題是，如何安排作業(yè)才能使額外增加的總費(fèi)用最少.返回導(dǎo)航優(yōu)優(yōu) 化化 建建 模模 例例7.23所涉及的問(wèn)題就是計(jì)劃網(wǎng)絡(luò)的優(yōu)化問(wèn)題，所涉及的問(wèn)題就是計(jì)劃網(wǎng)絡(luò)的優(yōu)化問(wèn)題，這時(shí)需要壓縮關(guān)鍵路徑來(lái)減少最短工期這時(shí)需要壓縮關(guān)鍵路徑來(lái)減少最短工期.優(yōu)優(yōu) 化化 建建 模模1. 計(jì)劃網(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)表達(dá)式計(jì)劃網(wǎng)絡(luò)優(yōu)化的數(shù)學(xué)表達(dá)式 設(shè)設(shè) 是事件是事件 的開(kāi)始時(shí)間，的開(kāi)始時(shí)間， 是作業(yè)是作業(yè) 的計(jì)劃時(shí)的計(jì)劃時(shí)間間, 是完成作業(yè)

22、是完成作業(yè) 的最短時(shí)間，的最短時(shí)間， 是作業(yè)是作業(yè) 可可能減少的時(shí)間，因此有能減少的時(shí)間，因此有ixiijt( , )i j( , )i j( , )i jijmijy0jiijijijijijx xt yytm且 設(shè)設(shè) 是要求完成的天數(shù)，是要求完成的天數(shù)， 為最初事件，為最初事件， 為最為最 終事件終事件,所以有所以有 而問(wèn)題的總目標(biāo)是使額外增而問(wèn)題的總目標(biāo)是使額外增加的費(fèi)用最小，即目標(biāo)函數(shù)為加的費(fèi)用最小，即目標(biāo)函數(shù)為 . 由此得到相應(yīng)由此得到相應(yīng)的數(shù)學(xué)規(guī)劃問(wèn)題的數(shù)學(xué)規(guī)劃問(wèn)題1,nxxd( , ).ijiji jac yd1n優(yōu)優(yōu) 化化 建建 模模2. 計(jì)劃網(wǎng)絡(luò)優(yōu)化的求解計(jì)劃網(wǎng)絡(luò)優(yōu)化的求解

23、例例7.24 用用lindo軟件求解例軟件求解例7.23 解：解：按照數(shù)學(xué)規(guī)劃問(wèn)題按照數(shù)學(xué)規(guī)劃問(wèn)題(7.43)-(7.47)編寫(xiě)編寫(xiě)lindo程序，程序名：程序，程序名：exam0724.ltx.優(yōu)優(yōu) 化化 建建 模模min 700 y13 + 400 y14 + 450 y25 + 600 y56 + 300 y57 + 500 y58 + 500 y68 + 400 y78 subject to2) x2 - x1 = 53) x3 - x1 + y13 = 104) x4 - x1 + y14 = 115) x5 - x2 + y25 = 46) x4 - x3 = 47) x5 - x

24、3 = 08) x6 - x4 = 159) x6 - x5 + y56 = 2110) x7 - x5 + y57 = 2511) x8 - x5 + y58 = 35優(yōu)優(yōu) 化化 建建 模模12) x7 - x6 = 013) x8 - x6 + y68 = 2014) x8 - x7 + y78 = 1515) x8 - x1 = 49endsub y13 2sub y14 3 sub y25 1sub y56 5sub y57 3sub y58 5sub y68 4sub y78 3優(yōu)優(yōu) 化化 建建 模模lindo軟件的計(jì)算結(jié)果如下：軟件的計(jì)算結(jié)果如下：lp optimum found

25、at step 23 objective function value 1) 1200.000 variable value reduced cost y13 1.000000 0.000000 y14 0.000000 400.000000 y25 0.000000 450.000000 y56 0.000000 100.000000 y57 0.000000 100.000000 y58 0.000000 500.000000 y68 1.000000 0.000000 y78 0.000000 200.000000優(yōu)優(yōu) 化化 建建 模模 x2 5.000000 0.000000 x1 0

26、.000000 0.000000 x3 9.000000 0.000000 x4 13.000000 0.000000 x5 9.000000 0.000000 x6 30.000000 0.000000 x7 34.000000 0.000000 x8 49.000000 0.000000 row slack or surplus dual prices 2) 0.000000 0.000000 3) 0.000000 -700.000000 4) 2.000000 0.000000 5) 0.000000 0.000000優(yōu)優(yōu) 化化 建建 模模 6) 0.000000 0.000000 7

27、) 0.000000 -700.000000 8) 2.000000 0.000000 9) 0.000000 -500.000000 10) 0.000000 -200.000000 11) 5.000000 0.000000 12) 4.000000 0.000000 13) 0.000000 -500.000000 14) 0.000000 -200.000000 15) 0.000000 700.000000 no. iterations= 23優(yōu)優(yōu) 化化 建建 模模 作業(yè)作業(yè)(1,3)(b)壓縮一天的工期，作業(yè)壓縮一天的工期，作業(yè)(6,8)(k)壓壓縮一天工期，這樣可以在縮一天工期，

28、這樣可以在49天完工，需要多花費(fèi)天完工，需要多花費(fèi)1200元元. 如果需要知道壓縮工期后的關(guān)鍵路徑，則需要如果需要知道壓縮工期后的關(guān)鍵路徑，則需要稍復(fù)雜一點(diǎn)的計(jì)算稍復(fù)雜一點(diǎn)的計(jì)算. 例例7.25 用用lingo軟件求解例軟件求解例7.23, 并求出相應(yīng)并求出相應(yīng)的關(guān)鍵路徑、各作業(yè)的最早開(kāi)工時(shí)間和最遲開(kāi)工時(shí)的關(guān)鍵路徑、各作業(yè)的最早開(kāi)工時(shí)間和最遲開(kāi)工時(shí)間間. 解：解： 為了得到作業(yè)的最早開(kāi)工時(shí)間，仍在目標(biāo)為了得到作業(yè)的最早開(kāi)工時(shí)間，仍在目標(biāo)函數(shù)中加入函數(shù)中加入 , 其他處理方法與前面相同其他處理方法與前面相同.iivx優(yōu)優(yōu) 化化 建建 模模寫(xiě)出相應(yīng)的寫(xiě)出相應(yīng)的lingo程序，程序名：程序，程序名：

29、 exam0725.lg4. model: 1sets: 2 events/1.8/: x; 3 operate(events, events)/ 4 ! a b c d e 0 f g h i 0 j k; 5 1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8 6 /: s, t, m, c, y; 7endsets 8data: 9 t = 5 10 11 4 4 0 15 21 35 25 0 15 20;優(yōu)優(yōu) 化化 建建 模模 10 m = 5 8 8 4 3 0 15 16 30 22 0 12 16; 11 c = 0 700

30、400 0 450 0 0 600 500 300 0 400 500; 12 d = 49; 13enddata 14min=mincost+sumx; 15mincost=sum(operate:c*y); 16sumx=sum(events: x); 17for(operate(i,j): s(i,j)=x(j)-x(i)+y(i,j)-t(i,j); 18n=size(events); 19x(n)-x(1)=d; 20for(operate:bnd(0,y,t-m); end優(yōu)優(yōu) 化化 建建 模模計(jì)算結(jié)果得到（只列出非零解）計(jì)算結(jié)果得到（只列出非零解）:variable value

31、reduced cost mincost 1200.000 0.000000 sumx 149.0000 0.000000 x( 2) 5.000000 0.000000 x( 3) 9.000000 0.000000 x( 4) 13.00000 0.000000 x( 5) 9.000000 0.000000 x( 6) 30.00000 0.000000 x( 7) 34.00000 0.000000 x( 8) 49.00000 0.000000 s( 1, 4) 2.000000 0.000000優(yōu)優(yōu) 化化 建建 模模 s( 4, 6) 2.000000 0.000000 s( 5,

32、 8) 5.000000 0.000000 s( 6, 7) 4.000000 0.000000 y( 1, 3) 1.000000 0.000000 y( 6, 8) 1.000000 0.000000計(jì)算結(jié)果與計(jì)算結(jié)果與lindo相同相同.作業(yè)作業(yè)(1,3)（b）減少一天）減少一天,作作業(yè)業(yè)(6,8)(k)減少一天，最小增加費(fèi)用為減少一天，最小增加費(fèi)用為1200元元. 按照前面的方法，計(jì)算出所有作業(yè)的最早開(kāi)工按照前面的方法，計(jì)算出所有作業(yè)的最早開(kāi)工時(shí)間和最遲開(kāi)工時(shí)間，見(jiàn)表時(shí)間和最遲開(kāi)工時(shí)間，見(jiàn)表7-11所示所示.優(yōu)優(yōu) 化化 建建 模模優(yōu)優(yōu) 化化 建建 模模 當(dāng)最早開(kāi)工時(shí)間與最遲開(kāi)工時(shí)間相同

33、時(shí)，對(duì)應(yīng)當(dāng)最早開(kāi)工時(shí)間與最遲開(kāi)工時(shí)間相同時(shí)，對(duì)應(yīng)的作業(yè)就在關(guān)鍵路線上，圖的作業(yè)就在關(guān)鍵路線上，圖7-15中的粗線表示優(yōu)化中的粗線表示優(yōu)化后的關(guān)鍵路線后的關(guān)鍵路線.從圖從圖7-15可能看到，關(guān)鍵路線不只一可能看到，關(guān)鍵路線不只一條條.優(yōu)優(yōu) 化化 建建 模模7.4.4 完成作業(yè)期望和實(shí)現(xiàn)事件的概率完成作業(yè)期望和實(shí)現(xiàn)事件的概率 在例在例7.19中，每項(xiàng)作業(yè)完成的時(shí)間均看成固定的中，每項(xiàng)作業(yè)完成的時(shí)間均看成固定的,但在實(shí)際應(yīng)用中，每一作業(yè)的完成會(huì)受到一些意外但在實(shí)際應(yīng)用中，每一作業(yè)的完成會(huì)受到一些意外因素的干擾，一般不可能是完全確定的，往往只能因素的干擾，一般不可能是完全確定的，往往只能憑借經(jīng)驗(yàn)過(guò)去完

34、成類似工作需要的時(shí)間來(lái)進(jìn)行估計(jì)憑借經(jīng)驗(yàn)過(guò)去完成類似工作需要的時(shí)間來(lái)進(jìn)行估計(jì).通常情況下，對(duì)完成一項(xiàng)作業(yè)可以給出三個(gè)時(shí)間上通常情況下，對(duì)完成一項(xiàng)作業(yè)可以給出三個(gè)時(shí)間上的估計(jì)值：最樂(lè)觀的估計(jì)值（的估計(jì)值：最樂(lè)觀的估計(jì)值（a），最悲觀的估計(jì)值），最悲觀的估計(jì)值(b)和最可能的估計(jì)值（和最可能的估計(jì)值（m）. 設(shè)設(shè) 完成作業(yè)完成作業(yè) 的實(shí)際時(shí)間（是一隨機(jī)變量），的實(shí)際時(shí)間（是一隨機(jī)變量），通常用下面的方法計(jì)算相應(yīng)的數(shù)學(xué)期望與方差通常用下面的方法計(jì)算相應(yīng)的數(shù)學(xué)期望與方差.ijt( , )i j返回導(dǎo)航優(yōu)優(yōu) 化化 建建 模模24(), (48)6()var(). (49)36ijijijijijijija

35、mbe tbat設(shè)設(shè)t為最短工期，即為最短工期，即:( , ). (50)iji jtt關(guān)鍵路線優(yōu)優(yōu) 化化 建建 模模由中心極限定理，可以假設(shè)由中心極限定理，可以假設(shè)t服從正態(tài)分布，并服從正態(tài)分布，并且期望值與方差滿足且期望值與方差滿足( , )2( , )( )( ) ( )var( ). (52).iji jiji jte te tsvar tt關(guān)鍵路線關(guān)鍵路線，51) 設(shè)規(guī)定的工期為設(shè)規(guī)定的工期為d, 則在規(guī)定的工期內(nèi)完成整則在規(guī)定的工期內(nèi)完成整個(gè)項(xiàng)目的概率為個(gè)項(xiàng)目的概率為:(). (53)dtp tds 優(yōu)優(yōu) 化化 建建 模模 psn(x)是是lingo軟件提供了標(biāo)準(zhǔn)正態(tài)分布軟件提供了

36、標(biāo)準(zhǔn)正態(tài)分布函數(shù)（見(jiàn)第三章的函數(shù)（見(jiàn)第三章的3.3.7節(jié)），即節(jié)），即:2/21( )( ). (54)2xtpsn xxedt 例例7.26 已知例已知例7.16中各項(xiàng)作業(yè)完成的三個(gè)估計(jì)中各項(xiàng)作業(yè)完成的三個(gè)估計(jì)時(shí)間，由表時(shí)間，由表7-12所示所示.如果規(guī)定時(shí)間為如果規(guī)定時(shí)間為52天，求在天，求在規(guī)定時(shí)間內(nèi)完成全部作業(yè)的概率規(guī)定時(shí)間內(nèi)完成全部作業(yè)的概率.進(jìn)一步，如果完進(jìn)一步，如果完成全部作業(yè)的概率大于等于成全部作業(yè)的概率大于等于95%，那么工期至少需，那么工期至少需要多少天？要多少天？?jī)?yōu)優(yōu) 化化 建建 模模 解：解：對(duì)于這個(gè)問(wèn)題采用最長(zhǎng)路的編寫(xiě)方法較為方對(duì)于這個(gè)問(wèn)題采用最長(zhǎng)路的編寫(xiě)方法較為方便

37、便.優(yōu)優(yōu) 化化 建建 模模 公式（公式（7.48)和公式和公式(7.49)計(jì)算出各作業(yè)的期望計(jì)算出各作業(yè)的期望值與方差，再由期望時(shí)間計(jì)算出關(guān)鍵路線值與方差，再由期望時(shí)間計(jì)算出關(guān)鍵路線.從而由公從而由公式式(7.51)和公式和公式(7.52)得到關(guān)鍵路線的期望與方差的得到關(guān)鍵路線的期望與方差的估計(jì)值，再利用分布函數(shù)估計(jì)值，再利用分布函數(shù) ,計(jì)算出完成作業(yè)計(jì)算出完成作業(yè)的概率與完成整個(gè)項(xiàng)目的時(shí)間的概率與完成整個(gè)項(xiàng)目的時(shí)間. 寫(xiě)出相應(yīng)的寫(xiě)出相應(yīng)的lingo程序，程序名：程序，程序名：xam0726.lg4.( )psn xmodel: 1sets: 2 events/1.8/: d; 3 opera

38、te(events, events)/ 4 ! a b c d e 0 f g h i 0 j k;優(yōu)優(yōu) 化化 建建 模模 5 1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8 6 /: a, m, b, et, dt, x; 7endsets 8data: 9 a = 3 8 8 2 3 0 8 18 26 18 0 12 11; 10 m = 5 9 11 4 4 0 16 20 33 25 0 15 21; 11 b = 7 16 14 6 5 0 18 28 52 32 0 18 25; 12 d = 1 0 0 0 0 0 0 -

39、1; 13 limit = 52; 14enddata 15for(operate: 16 et = (a+4*m+b)/6; 17 dt = (b-a)2/36;優(yōu)優(yōu) 化化 建建 模模 18); 19max = tbar; 20tbar = sum(operate: et*x); 21for(events(i): 22 sum(operate(i,j): x(i,j) - sum(operate(j,i): x(j,i) 23 = d(i); 24); 25s2 = sum(operate: dt*x); 26p = psn(limit-tbar)/s); 27psn(days-tbar)/

40、s) = 0.95; end優(yōu)優(yōu) 化化 建建 模模 程序的第程序的第20行計(jì)算關(guān)鍵路徑的時(shí)間數(shù)學(xué)期行計(jì)算關(guān)鍵路徑的時(shí)間數(shù)學(xué)期 第第25行計(jì)行計(jì)算關(guān)鍵路徑的時(shí)間方差算關(guān)鍵路徑的時(shí)間方差 , 第第26行計(jì)算在規(guī)定時(shí)間內(nèi)完行計(jì)算在規(guī)定時(shí)間內(nèi)完成全部作業(yè)的概率成全部作業(yè)的概率 ,第第 27行計(jì)算在行計(jì)算在95%概率完成全部作概率完成全部作業(yè)的時(shí)間業(yè)的時(shí)間(days).( ),t2()s( )p lingo軟件的計(jì)算結(jié)果（只列出非零解）如下：軟件的計(jì)算結(jié)果（只列出非零解）如下：variable value reduced cost tbar 51.00000 0.000000 s 3.162276 0.

41、000000 p 0.6240861 0.000000 days 56.20148 0.000000 即關(guān)鍵路線的期望時(shí)間為即關(guān)鍵路線的期望時(shí)間為51天，標(biāo)準(zhǔn)差為天，標(biāo)準(zhǔn)差為3.16，在，在52天天完全部作業(yè)的概率為完全部作業(yè)的概率為62.4%，如果在規(guī)定的工期內(nèi)，完成全，如果在規(guī)定的工期內(nèi)，完成全部作業(yè)的概率大于等于部作業(yè)的概率大于等于95%，那么工期至少需要，那么工期至少需要56.2天天.優(yōu)優(yōu) 化化 建建 模模習(xí)題習(xí)題 七七本節(jié)內(nèi)容導(dǎo)航本節(jié)內(nèi)容導(dǎo)航 習(xí)題習(xí)題:7.1 習(xí)題習(xí)題:7.2 習(xí)題習(xí)題:7.3 習(xí)題習(xí)題:7.4 習(xí)題習(xí)題:7.5 習(xí)題習(xí)題:7.6習(xí)題習(xí)題:7.7 習(xí)題習(xí)題:7.8

42、習(xí)題習(xí)題:7.9 習(xí)題習(xí)題:7.10優(yōu)優(yōu) 化化 建建 模模 7.1 有兩個(gè)煤廠有兩個(gè)煤廠a、b, 每月分別進(jìn)煤不小于每月分別進(jìn)煤不小于60噸、噸、100噸噸, 它們擔(dān)負(fù)供應(yīng)三個(gè)居民區(qū)用煤任務(wù)它們擔(dān)負(fù)供應(yīng)三個(gè)居民區(qū)用煤任務(wù), 這這三個(gè)居民區(qū)每月需用煤分別為三個(gè)居民區(qū)每月需用煤分別為45噸、噸、75噸和噸和40噸噸, a廠離這三居民區(qū)分別是廠離這三居民區(qū)分別是10公里、公里、5公里和公里和6公里公里, b廠離這三居民區(qū)分別為廠離這三居民區(qū)分別為4公里、公里、8公里和公里和15公里公里, 問(wèn)問(wèn)這兩煤廠如何分配供煤這兩煤廠如何分配供煤, 才使運(yùn)量最小才使運(yùn)量最小? 返回導(dǎo)航優(yōu)優(yōu) 化化 建建 模模 7.2 已知有已知有6個(gè)人（個(gè)人（1，2，3，4，5，6），可以做），可以做6項(xiàng)項(xiàng)工作工作 ，每個(gè)人做每項(xiàng)工作的效率表，每個(gè)人做每項(xiàng)工作的效率表7-13所示所示.問(wèn)：應(yīng)如何安排每個(gè)人的工作，使總工作效率最大？問(wèn)：應(yīng)如何安排每個(gè)人的工作，使總工作效率最大？(1 , 2 , 3 , 4 , 5 , 6 )返回導(dǎo)航優(yōu)優(yōu) 化化 建建 模模 7.3 在圖在圖7-16中，中，a、b為發(fā)點(diǎn)，分別有為發(fā)點(diǎn)，分別有50和和40單位物資單位物資往外運(yùn)，往外運(yùn)，d、e為收點(diǎn)，分別需要物資為收點(diǎn)，分別需要物資30和和60單位，單位， c為中為中轉(zhuǎn)點(diǎn)，圖中括號(hào)的第一個(gè)數(shù)字為弧的容量，第二個(gè)