網(wǎng)絡(luò)優(yōu)化建模

1、 網(wǎng)絡(luò)計劃圖的繪制網(wǎng)絡(luò)計劃圖的繪制 時間參數(shù)計算與關(guān)鍵路線確定時間參數(shù)計算與關(guān)鍵路線確定 網(wǎng)絡(luò)圖的調(diào)整及優(yōu)化網(wǎng)絡(luò)圖的調(diào)整及優(yōu)化 網(wǎng)絡(luò)計劃（工程計劃問題）網(wǎng)絡(luò)計劃（工程計劃問題）1.問題的一般題法：問題的一般題法： 設(shè)有一項工程，可分為若干道工序，已知各工序間設(shè)有一項工程，可分為若干道工序，已知各工序間的先后關(guān)系以及各工序所需時間的先后關(guān)系以及各工序所需時間t。問：（1）工程完工期T？（2）工程的關(guān)鍵工序有哪些？（3）若工序時間T具有隨機性，則期望完工期TE=? 完工期為某天的可能性多大？（4）費用優(yōu)化和資源平衡。 例例 甲、乙兩工程師從早上六時起床到上甲、乙兩工程師從早上六時起床到上班前有一系

2、列活動要做。對于同樣的活班前有一系列活動要做。對于同樣的活動過程，有人忙亂不堪，甚至遲到，有動過程，有人忙亂不堪，甚至遲到，有人則又快又好，關(guān)鍵在于一個科學的活人則又快又好，關(guān)鍵在于一個科學的活動實施計劃。動實施計劃。甲出門上班穿衣刷牙洗臉做稀飯熱饅頭吃早飯收拾房間整理出門上班穿衣洗臉刷牙收拾房間整理吃早飯做稀飯熱饅頭乙 例例2 2 大型工程實施（三峽工程、南水北調(diào)工程、大型工程實施（三峽工程、南水北調(diào)工程、人造衛(wèi)星工程、宇航工程等）有如下活動：人造衛(wèi)星工程、宇航工程等）有如下活動：1 1 產(chǎn)品設(shè)計、仿真、試制、中試產(chǎn)品設(shè)計、仿真、試制、中試2 2 原材料設(shè)備定貨、采購、運輸、入庫原材料設(shè)備定

3、貨、采購、運輸、入庫3 3 廠房、設(shè)備施工建筑、安裝廠房、設(shè)備施工建筑、安裝4 4 產(chǎn)品計劃、生產(chǎn)、銷售、安裝、調(diào)試、維產(chǎn)品計劃、生產(chǎn)、銷售、安裝、調(diào)試、維護護參與單位涉及國家各部門、各行業(yè)、事業(yè)單位，參與單位涉及國家各部門、各行業(yè)、事業(yè)單位，為高速度、低成本、高質(zhì)量，并在規(guī)定期限內(nèi)為高速度、低成本、高質(zhì)量，并在規(guī)定期限內(nèi)完成該工程項目，其關(guān)鍵在：完成該工程項目，其關(guān)鍵在：1 1 抓好科學技術(shù)抓好科學技術(shù)2 2 抓好項目管理，組織協(xié)調(diào)好各單位、各任抓好項目管理，組織協(xié)調(diào)好各單位、各任務(wù)、各工序的完成。務(wù)、各工序的完成。 例例3 3 三軍聯(lián)合作戰(zhàn)演習三軍聯(lián)合作戰(zhàn)演習u空軍奪取制空權(quán)，對敵實施地面

4、攻擊，運送空降兵空軍奪取制空權(quán)，對敵實施地面攻擊，運送空降兵u海軍艦艇護衛(wèi)，運送陸軍、海軍陸戰(zhàn)隊登陸奪取灘海軍艦艇護衛(wèi)，運送陸軍、海軍陸戰(zhàn)隊登陸奪取灘頭陣地頭陣地u登陸完成后的鞏固陣地與縱深發(fā)展登陸完成后的鞏固陣地與縱深發(fā)展u電子對抗部隊實施情報收集分析與電子對抗電子對抗部隊實施情報收集分析與電子對抗 參與兵種：海軍航空兵、海軍陸戰(zhàn)隊、水面艦艇參與兵種：海軍航空兵、海軍陸戰(zhàn)隊、水面艦艇部隊、空軍殲擊機、攻擊機、轟炸機、電子對抗部隊、空軍殲擊機、攻擊機、轟炸機、電子對抗機各團、大隊，坦克、炮兵、步兵、防化兵、通機各團、大隊，坦克、炮兵、步兵、防化兵、通訊兵、偵察兵、導彈部隊等。訊兵、偵察兵、導彈

5、部隊等。 需迅速訂好科學的作戰(zhàn)演習計劃，以便對作戰(zhàn)演需迅速訂好科學的作戰(zhàn)演習計劃，以便對作戰(zhàn)演習過程演習過程進行有效的管理與控制。習過程演習過程進行有效的管理與控制。2.解法解法關(guān)鍵路徑法（CPM方法）計劃評審法（PERT方法）l相同點：l不同點：PERT法：注重于對工程安排的評價與審查。CPM方法：注重于時間、成本和資源的優(yōu)化；均是用網(wǎng)絡(luò)表示工程項目，以確定關(guān)鍵路線。 計劃評審方法計劃評審方法（Program Evaluation and Review Technique, 簡寫為簡寫為PERT）和）和關(guān)鍵路線法關(guān)鍵路線法（Critial PathMethod, 簡寫為簡寫為CPM）是網(wǎng)絡(luò)分

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

7、劃評審方法.由于由于PERT與與CPM即有著相同的目標應(yīng)用，又有很多相同的術(shù)語，這兩即有著相同的目標應(yīng)用，又有很多相同的術(shù)語，這兩種方法已合并為一種方法，在國外稱為種方法已合并為一種方法，在國外稱為PERT/CPM，在國內(nèi)稱為統(tǒng)籌方法在國內(nèi)稱為統(tǒng)籌方法(Scheduling Method).2.1 計劃網(wǎng)絡(luò)圖的繪計劃網(wǎng)絡(luò)圖的繪制制1. 計劃網(wǎng)絡(luò)圖的概念計劃網(wǎng)絡(luò)圖的概念 定義定義1 稱任何消耗時間或資源的行動為作稱任何消耗時間或資源的行動為作業(yè)業(yè).稱作業(yè)的開始或結(jié)束為事件，事件本身不消耗稱作業(yè)的開始或結(jié)束為事件，事件本身不消耗資源資源. 在計劃網(wǎng)絡(luò)圖中通常用圓圈表示事件，用箭在計劃網(wǎng)絡(luò)圖中通常用

8、圓圈表示事件，用箭線表示事件，如圖線表示事件，如圖7-12所示，所示，1, 2, 3表示事件，表示事件，A, B表示作業(yè)表示作業(yè).由這種方法畫出的網(wǎng)絡(luò)圖稱為計劃由這種方法畫出的網(wǎng)絡(luò)圖稱為計劃網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖.定義定義2 在計劃網(wǎng)絡(luò)圖中，稱從是初始事在計劃網(wǎng)絡(luò)圖中，稱從是初始事件到最終事件的由各項作業(yè)連貫組成的一條路為件到最終事件的由各項作業(yè)連貫組成的一條路為路線。具有累計作業(yè)時間最長的路線稱為關(guān)鍵路路線。具有累計作業(yè)時間最長的路線稱為關(guān)鍵路線。線。由此看來，一般網(wǎng)絡(luò)圖是求相應(yīng)的圖中的關(guān)由此看來，一般網(wǎng)絡(luò)圖是求相應(yīng)的圖中的關(guān)鍵路線。鍵路線。2. 建立計劃網(wǎng)絡(luò)圖應(yīng)注意的問題建立計劃網(wǎng)絡(luò)圖應(yīng)注意的問題(

9、1) 任何作業(yè)在網(wǎng)絡(luò)中用唯一的箭線表示，任何作業(yè)任何作業(yè)在網(wǎng)絡(luò)中用唯一的箭線表示，任何作業(yè)其終點事件的編號必須大于其起點事件其終點事件的編號必須大于其起點事件.1221 (2) 兩個事件之間只能畫一條箭線，表示一兩個事件之間只能畫一條箭線，表示一項作業(yè)項作業(yè).對于具有相同開始和結(jié)束事件的兩項以上對于具有相同開始和結(jié)束事件的兩項以上作業(yè)，要引進虛事件和虛作業(yè)作業(yè)，要引進虛事件和虛作業(yè). (4) 計劃網(wǎng)絡(luò)圖不允許出現(xiàn)回路計劃網(wǎng)絡(luò)圖不允許出現(xiàn)回路12ab46a12b46回路回路123ac40b6123a/222b6a/2 (3) 任何計劃網(wǎng)絡(luò)圖應(yīng)有唯一的最初事件和任何計劃網(wǎng)絡(luò)圖應(yīng)有唯一的最初事件和唯

10、一的最終事件唯一的最終事件. (5) 計劃網(wǎng)絡(luò)圖的畫法一般是從左到右，從計劃網(wǎng)絡(luò)圖的畫法一般是從左到右，從上到下，盡量作到清晰美觀，避免箭頭交上到下，盡量作到清晰美觀，避免箭頭交叉叉. 例1 某公司研制新產(chǎn)品的部分工序明細表如下，試畫出統(tǒng)籌圖。（反向搜索法）（反向搜索法）工序代號 工序名稱（或內(nèi)容）工序長度緊前工序a產(chǎn)品設(shè)計與工藝設(shè)計60-b外購配套零件15ac外購生產(chǎn)原料13ad自制主件38ce主配件可靠性試驗8b, d12453abced601513388分支時候盡量向一起努力分支時候盡量向一起努力 例5 某工程項目作業(yè)明細表如下 ，（1）繪制計劃網(wǎng)絡(luò)圖 ；（2）求關(guān)鍵路線與路長；（3）求

11、關(guān)鍵工序序號序號工序代號工序代號所需時間所需時間緊前工序緊前工序1a60-2b15a3c13a4d38c5e8b、d6f10d7g16d8h5e、f、g 解：若已知緊后工序之作業(yè)明細表，故用正象（順向）搜索法，已知緊前工序之作業(yè)明細表，故可采用反向搜索法。 （f g h）1253476abedghfc1254376abedghfc860151338810165例3 某工廠進行技術(shù)改造的工作表如下：工序代號工序名稱緊前工序工作時間（周）A拆遷/2B工程設(shè)計/3C土建工程設(shè)計B2.5D采購設(shè)備B6E廠房土建C，A20F設(shè)備安裝D，E4G設(shè)備調(diào)試F21A(2)3B(3)2C（2.5）4D（6）E（2

12、0）5F（4）6G（2）2.2 建立相應(yīng)的規(guī)劃建立相應(yīng)的規(guī)劃問題方法問題方法1 例例 某項目工程由某項目工程由11項作業(yè)組成（分別用代號項作業(yè)組成（分別用代號A, B, , J, K表示），其計劃完成時間及作業(yè)間相互表示），其計劃完成時間及作業(yè)間相互關(guān)系如表關(guān)系如表7-8所示，求完成該項目的最短時間所示，求完成該項目的最短時間.2. 寫出相應(yīng)的規(guī)劃問題寫出相應(yīng)的規(guī)劃問題 設(shè)是事件的開始時間，設(shè)是事件的開始時間， 為最初事件，為為最初事件，為最終事件最終事件.希望總的工期最短，即極小化希望總的工期最短，即極小化 .設(shè)設(shè)是作業(yè)是作業(yè) 的計劃時間，因此，對于事件的計劃時間，因此，對于事件 與事件與事

13、件 有不等式：有不等式： ixi11nxxijt( , )i jijjiijxxt由此得到相應(yīng)的數(shù)學規(guī)劃問由此得到相應(yīng)的數(shù)學規(guī)劃問題題 Min= x8 - x1 2) x2 - x1 = 5 3) x3 - x1 = 10 4) x4 - x1 = 11 5) x5 - x2 = 4 6) x4 - x3 = 4 7) x5 - x3 = 0 8) x6 - x4 = 15 9) x6 - x5 = 21 10) x7 - x5 = 25 11) x8 - x5 = 35 12) x7 - x6 = 0 13) x8 - x6 = 20 14) x8 - x7 = 15Objective va

14、lue: 51.00000 Infeasibilities: 0.000000 Total solver iterations: 1 Variable Value Reduced Cost X8 51.00000 0.000000 X1 0.000000 0.000000 X2 5.000000 0.000000 X3 10.00000 0.000000 X4 14.00000 0.000000 X5 10.00000 0.000000 X6 31.00000 0.000000 X7 35.00000 0.000000 計算結(jié)果給出了各個項目的開工時間，如計算結(jié)果給出了各個項目的開工時間，如

15、, 則則作業(yè)作業(yè)A、B、C的開工時間均是第的開工時間均是第0天天; 作業(yè)作業(yè)E的開的開工時間是第工時間是第5天天; 則作業(yè)則作業(yè)D的開工時間是第的開工時間是第10天天; 等等等等.每個作業(yè)只要按規(guī)定的時間開工，整個項每個作業(yè)只要按規(guī)定的時間開工，整個項目的最短工期為目的最短工期為51天天.10 x 25,x 310,x 盡管上述盡管上述LINgo程序給出相應(yīng)的開工時間和整個程序給出相應(yīng)的開工時間和整個項目的最短工期，但統(tǒng)籌方法中許多有用的信息并沒項目的最短工期，但統(tǒng)籌方法中許多有用的信息并沒有得到，如項目的關(guān)鍵路徑、每個作業(yè)的最早開工時有得到，如項目的關(guān)鍵路徑、每個作業(yè)的最早開工時間、最遲開工

16、時間等間、最遲開工時間等.因此，我們希望將程序編寫的因此，我們希望將程序編寫的稍微復(fù)雜一些，為我們提供更多的信息稍微復(fù)雜一些，為我們提供更多的信息.編寫相應(yīng)的編寫相應(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 5 /: s, t; 6endsets 7data: 8 t = 5 10 11 4 4 0 15 21 35 25 0 15 20; 9en

17、ddata 10min=sum(events : x); 11for(operate(i,j): s(i,j)=x(j)-x(i)-t(i,j); END計算得到（只列出非零解）計算得到（只列出非零解）: 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 0.000000 X( 6) 31.00000 0.000000 X( 7) 35.00000 0.000000 X( 8) 51.00000 0.000000 S

18、( 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è)的最早開工時間和最遲由此，可以得到所有作業(yè)的最早開工時間和最遲開工時間，如表開工時間，如表7-9所示，方括號中第所示，方括號中第1個數(shù)字是最早個數(shù)字是最早開工時間，第開工時間，第2個數(shù)字是最遲開工時間個數(shù)字是最遲開工時間. 從上述表可以看出，當最早開工時間

19、與最遲開從上述表可以看出，當最早開工時間與最遲開工時間相同時，對應(yīng)的作業(yè)在關(guān)鍵路線上，因此可工時間相同時，對應(yīng)的作業(yè)在關(guān)鍵路線上，因此可以畫出計劃網(wǎng)絡(luò)圖中的關(guān)鍵路線，如圖以畫出計劃網(wǎng)絡(luò)圖中的關(guān)鍵路線，如圖7-14粗線所粗線所示示.關(guān)鍵路線為關(guān)鍵路線為 13568.2.3 建立相應(yīng)的規(guī)劃建立相應(yīng)的規(guī)劃問題方法問題方法2將關(guān)鍵路線看成最長路將關(guān)鍵路線看成最長路 如果將關(guān)鍵路線看成最長路，則可以按照求最短如果將關(guān)鍵路線看成最長路，則可以按照求最短路的方法（將求極小改為求極大）求出關(guān)鍵路線路的方法（將求極小改為求極大）求出關(guān)鍵路線 .設(shè)為設(shè)為 變量，當作業(yè)變量，當作業(yè) 位于關(guān)鍵路線上取位于關(guān)鍵路線上取1;否否則取則取0. 數(shù)學規(guī)劃問題寫成數(shù)學規(guī)劃問題寫成:ijx0 1( , )i j例例 用最長路的方法求用最長路的方法求jie. 解：解： 按數(shù)學規(guī)劃按數(shù)學規(guī)劃(7.40)-(7.42)寫出相應(yīng)的寫出相應(yīng)的INGO程序，程序名：程序，程序名：exam0722.lg4.MODEL: 1sets: 2 events/1.8/: d; 3 operate(events, events)/ 4 1,2 1,3 1,4 3,4 2,