1、第六章 模型決策法,線性規(guī)劃等 時序與路徑規(guī)劃 分派問題 最短路問題 最大流問題,模型決策法,優(yōu)化模型 max (min) 目標(biāo)函數(shù) s. t. 約束條件,線性規(guī)劃模型的建立,實例 1 兩種產(chǎn)品的生產(chǎn)。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原材料的消耗，資源限制及市場價格如下表： 資源限制 設(shè)備11300臺時 原材料A21400千克 原材料B01250千克 市場價格50100 問題：如何安排生產(chǎn)，才能使工廠獲利最多？,規(guī)劃與決策,分析： （1）設(shè) x1 生產(chǎn)產(chǎn)品的數(shù)量； x2 生產(chǎn)產(chǎn)品的數(shù)量。 （2）目標(biāo)函數(shù)：MAX 50 x1+100 x2 （3）約束條件：subject to (s.t

2、.): x1+x2 300 2x1+x2 400 x2 250 x1,x2 0,規(guī)劃與決策,線性規(guī)劃模型： max 50 x1+100 x2 s.t. x1+x2 300 2x1+x2 400 x2 250 x1,x2 0,規(guī)劃與決策,線性規(guī)劃模型的一般形式 max c1x1+c2x2+ + cn xn s. t. a11x1 + + a1nx n (,=) b1 a21x1 + + a2nx n (,=) b2 am1x1 + + amnx n (,=) bm xij 0 i = 1, ,n, j =1, ,m,規(guī)劃與決策,線性規(guī)劃應(yīng)用領(lǐng)域： 合理利用板、線材問題； 配料問題； 投資問題；

3、生產(chǎn)計劃問題、勞動力安排問題； 運(yùn)輸問題、電子商務(wù)配送問題； 企業(yè)決策問題；企業(yè)或商業(yè)競爭對策問題等。,規(guī)劃與決策,一般線性規(guī)劃建模過程 Step 1. 理解及分析實際問題，資源狀況，解決問題實現(xiàn)的目標(biāo)； Step 2. 確定決策變量（x1, ，xn） 解決問題的具體方案（量化方案）； Step 3. 確定目標(biāo)函數(shù)及約束條件； Step 4. 應(yīng)用線性規(guī)劃軟件求解； Step 5. 檢驗所求得的解決方案是否可行：如可行，則開始具體實施；否則，轉(zhuǎn)Step 1 或 Step2 修改模型。,規(guī)劃與決策,案例2：（生產(chǎn)計劃問題）某公司面臨一個外協(xié)加工還是自行生產(chǎn)問題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，這三

4、種產(chǎn)品都需要經(jīng)過鑄造、機(jī)加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄造可以外協(xié)加工，亦可以自行生產(chǎn)。但丙產(chǎn)品的鑄造必須自行生產(chǎn)才能保證質(zhì)量。有關(guān)數(shù)據(jù)見下表：,規(guī)劃與決策,工時與成本甲乙丙總工時 每件鑄造工時（小時）51078000 每件機(jī)加工工時（小時）64812000 每件裝配工時（小時）32210000 自產(chǎn)鑄件每件成本（元）354 外協(xié)鑄件每件成本（元）56- 機(jī)加工每件成本（元）213 裝配每件成本（元）322 每件產(chǎn)品售價（元）231816 問題：如何安排生產(chǎn)計劃，使公司獲利最大？,規(guī)劃與決策,分析：設(shè) xi 公司加工甲、乙、丙三種產(chǎn)品數(shù)量，i=1,2,3。x4、x5由外協(xié)鑄造后再由本公司

5、機(jī)加工和裝配的甲、 乙兩種產(chǎn)品數(shù)量； 目標(biāo)函數(shù)： 每件產(chǎn)品利潤分別是： 每件x1產(chǎn)品利潤: 23-（3+2+3） =15元 每件x2產(chǎn)品利潤: 18-（5+1+2） =10元 每件x3產(chǎn)品利潤: 16-（4+3+2） =7元 每件x4產(chǎn)品利潤: 23-（5+2+3） =13元 每件x5產(chǎn)品利潤: 18-（6+1+2） =9元 目標(biāo)函數(shù)為： max 15 x1+10 x2+7 x3+13 x4+9 x5,規(guī)劃與決策,約束條件： 5 x1+10 x2+7 x3 8000 6 x1+4 x2+8 x3+6 x4+4 x5 12000 3 x1+2 x2+2 x3+3 x4+2 x5 10000 xi

6、 0 i=1,5,規(guī)劃與決策,圖解法: Step 1. 確定可行域 D = x | x 滿足上述約束條件如下圖2-1： Step 2. 確定直線 50 x1+100 x2=0如下圖2-2： Step 3. 向上移動直線 50 x1+100 x2=0如圖2-2，z=50 x1+100 x2 的值不斷地增加，達(dá)到B點(diǎn)時， 達(dá)到最大； Step 4. 最優(yōu)解為B=(50,250), z最大=27500。,規(guī)劃與決策,0 100 200 300,300,200,100,D,圖 2-1,規(guī)劃與決策,0 100 200 300,300,200,100,D,B(50,250),Z= 50 x1+100 x2

7、,圖 2-2,時序與路徑規(guī)劃,討論各種時序規(guī)劃問題 介紹時序規(guī)劃原則 分派問題 運(yùn)輸問題 網(wǎng)絡(luò)的最短路徑 網(wǎng)絡(luò)的最大流,時序規(guī)劃問題,A,B,E,F,D,C,機(jī)器,機(jī)器,D,E,F,C,A,B,等待處理的一批工作,按最優(yōu)次序排隊,一臺機(jī)器工作的時序規(guī)劃,時序規(guī)劃問題,原則： (1) 最緊迫的優(yōu)先 實例 1： 6種部件作為一批等待一臺機(jī)器加工。每一部件的平均周需求量、當(dāng)前的存貨水平以及加工一批所需時間如下表，你將如何安排各種部件的生產(chǎn)次序？ 部 件 A B C D E F 平均需求量 10 4 26 34 7 3 當(dāng)前存貨量 72 21 48 92 28 23 加工時間 2.0 1.5 0.5

8、0.5 1.0 1.5,時序規(guī)劃問題,時序規(guī)劃問題,時序規(guī)劃問題,以“加工時間最短者優(yōu)先”為原則,時序規(guī)劃問題,以“加工時間最短者優(yōu)先”為原則,時序規(guī)劃問題,(3) 到期日最近者原則,時序規(guī)劃問題,(3) 到期日最近者原則,時序規(guī)劃問題,(4) 延誤的工作項目最少 第1步：運(yùn)用先到期者優(yōu)先的原則排出工作的初始次序。如果已經(jīng)沒有工作被延誤，這便是最優(yōu)解，否則，則進(jìn)行第2步。 第2步：在安排的時序中找到1項延誤的工作。 第3步：找出第2步所找工作之前（包括這一工作本身）加工時間最長的工作。 第4步：將這一工作從時序安排中抽出來，并更新相應(yīng)的時間。如果仍然有被延誤的工作，再轉(zhuǎn)向第2步，否則轉(zhuǎn)向第5步

9、。 第5步：將第4步抽出的工作放到時序的末尾。 實例 3：沿用上述實例的8項工作，求解工作延誤項數(shù)最少的時序。 為此我們采用上述五個步驟。 工 作 A B C D E F G H 加工時間 2 5 3 8 4 7 2 3 到期時間 13 7 8 30 14 20 2 36,時序規(guī)劃問題,第1步：將工作按到期時間排序。 工 作 G B C A E F D H 到期時間 2 7 8 13 14 20 30 36 開始加工時間 0 2 7 10 12 16 23 31 加工時間 2 5 3 2 4 7 8 3 完成加工時間 2 7 10 12 16 23 31 34 延誤工作 * * * * 第2步

10、：在上述時序中，第1項被延誤的工作是C。 第3步：到C之前，包括C在內(nèi)，加工時間最長的工作是B，加工時間為5。,時序規(guī)劃問題,第4步：抽出工作B，更新相關(guān)的時間： 工 作 G C A E F D H 到期時間 2 8 13 14 20 30 36 開始加工時間 0 2 5 7 11 18 26 加工時間 2 3 2 4 7 8 3 完成加工時間 2 5 7 11 18 26 29 第5步：現(xiàn)在已經(jīng)沒有工作被延誤了，所以我們將工作B加到時序的最后。 工 作 G C A E F D H B 到期時間 2 8 13 14 20 30 36 7 開始加工時間 0 2 5 7 11 18 26 29 加

11、工時間 2 3 2 4 7 8 3 5 完成加工時間 2 5 7 11 18 26 29 34 現(xiàn)在只有一項工作被延誤，平均排隊時間為98/8=12.25，平均延誤時間為27/8=3.375天。,時序規(guī)劃問題,(5) Johnsons rule(約翰遜原則) 步驟1：列出各項工作及它們在每臺機(jī)器上的加工時間。 步驟2：找出下一個在各臺機(jī)器上加工時間最短的工作。 步驟3：如果這是在機(jī)器1上，盡量將這一工作安排在前面；如果這是在機(jī)器2上，盡量將這一工作安排在后面。在重復(fù)做這些的時候，總是從時序的兩端向內(nèi)進(jìn)行，新安排的工作離時序的中間更近。 步驟4：不必再考慮這一工作，回到步驟2。如果再找不到這樣的

12、任務(wù)，這就是最優(yōu)解。 實例 4： 有7項工作要順序經(jīng)過機(jī)器1和機(jī)器2加工。每項工作在每臺機(jī)器上所需的加工時間如下，如何安排時序才能使機(jī)器利用率最高。 工作 A B C D E F G 機(jī)器1 2 5 10 8 4 12 9 機(jī)器2 14 7 3 10 5 6 6,時序規(guī)劃問題,時序規(guī)劃問題,分派問題,如何以總成本最低為目標(biāo)將操作員分派到各臺機(jī)器上。 原則：每個操作員只能分派給一項任務(wù)，每項任務(wù)只能由一人完成。 Cij 第i個操作員完成第j項任務(wù)的成本 Xij min CijXij Xij=1 Xij=1 Xij=0,1 i=1,n, j=1,m,=1 (分派操作員i完成任務(wù)j) =0 (不分派操作員i完成任務(wù)j),j,i,最短路問題,最短路問題 G(V,E) 為 連通圖，邊（vi,vj)的權(quán)為lij，求一條道路，使它從vs到vt的總權(quán)最少？ 方法：1 動態(tài)規(guī)劃法 2 Dijkstra算法 引例：某一配送中心要給一個快餐店送快餐原料，應(yīng)按什么路線送貨才能使送貨時間最短？,V2 16 v4 7 v6,4 6,V1 12 2 8 v7,18 5,V3 6 v5,（配送中心）,（快