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

2、2 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ī)劃應用領域：合理利用板、線材問題；配料問題；投資問題；生產(chǎn)計劃問題、勞動力安排問題；運輸問題、電子商務配送問題

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

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

5、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元目標函數(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 0 i=1,5規(guī)劃與決策圖解法:Step 1. 確定可行域 D = x | x 滿足上述約束條件如下圖2-1：Step

6、2. 確定直線 50 x1+100 x2=0如下圖2-2：Step 3. 向上移動直線 50 x1+100 x2=0如圖2-2，z=50 x1+100 x2 的值不斷地增加，達到B點時， 達到最大；Step 4. 最優(yōu)解為B=(50,250), z最大=27500。規(guī)劃與決策 0 100 200 300300200100D圖 2-1規(guī)劃與決策 0 100 200 300300200100DB(50,250)Z= 50 x1+100 x2圖 2-2時序與路徑規(guī)劃討論各種時序規(guī)劃問題介紹時序規(guī)劃原則分派問題運輸問題網(wǎng)絡的最短路徑網(wǎng)絡的最大流時序規(guī)劃問題 ABEFDC機器機器DEFCAB等待處理的一

7、批工作按最優(yōu)次序排隊一臺機器工作的時序規(guī)劃時序規(guī)劃問題原則：(1) 最緊迫的優(yōu)先實例 1： 6種部件作為一批等待一臺機器加工。每一部件的平均周需求量、當前的存貨水平以及加工一批所需時間如下表，你將如何安排各種部件的生產(chǎn)次序？ 部 件 A B C D E F 平均需求量 10 4 26 34 7 3 當前存貨量 72 21 48 92 28 23 加工時間 2.0 1.5 0.5 0.5 1.0 1.5時序規(guī)劃問題 時序規(guī)劃問題 時序規(guī)劃問題 以“加工時間最短者優(yōu)先”為原則時序規(guī)劃問題 以“加工時間最短者優(yōu)先”為原則時序規(guī)劃問題(3) 到期日最近者原則時序規(guī)劃問題(3) 到期日最近者原則時序規(guī)劃

8、問題(4) 延誤的工作項目最少第1步：運用先到期者優(yōu)先的原則排出工作的初始次序。如果已經(jīng)沒有工作被延誤，這便是最優(yōu)解，否則，則進行第2步。第2步：在安排的時序中找到1項延誤的工作。第3步：找出第2步所找工作之前（包括這一工作本身）加工時間最長的工作。第4步：將這一工作從時序安排中抽出來，并更新相應的時間。如果仍然有被延誤的工作，再轉向第2步，否則轉向第5步。第5步：將第4步抽出的工作放到時序的末尾。實例 3：沿用上述實例的8項工作，求解工作延誤項數(shù)最少的時序。 為此我們采用上述五個步驟。 工 作 A B C D E F G H 加工時間 2 5 3 8 4 7 2 3 到期時間 13 7 8

9、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步：在上述時序中，第1項被延誤的工作是C。第3步：到C之前，包括C在內(nèi)，加工時間最長的工作是B，加工時間為5。時序規(guī)劃問題第4步：抽出工作B，更新相關的時間： 工 作 G C A E F D H 到期時間 2 8 13 14 20 30 36 開始加工

10、時間 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 加工時間 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(約翰遜原則)步驟

11、1：列出各項工作及它們在每臺機器上的加工時間。步驟2：找出下一個在各臺機器上加工時間最短的工作。步驟3：如果這是在機器1上，盡量將這一工作安排在前面；如果這是在機器2上，盡量將這一工作安排在后面。在重復做這些的時候，總是從時序的兩端向內(nèi)進行，新安排的工作離時序的中間更近。步驟4：不必再考慮這一工作，回到步驟2。如果再找不到這樣的任務，這就是最優(yōu)解。 實例 4： 有7項工作要順序經(jīng)過機器1和機器2加工。每項工作在每臺機器上所需的加工時間如下，如何安排時序才能使機器利用率最高。 工作 A B C D E F G 機器1 2 5 10 8 4 12 9 機器2 14 7 3 10 5 6 6時序規(guī)劃

12、問題 時序規(guī)劃問題 分派問題如何以總成本最低為目標將操作員分派到各臺機器上。原則：每個操作員只能分派給一項任務，每項任務只能由一人完成。 Cij 第i個操作員完成第j項任務的成本 Xij min CijXij Xij=1 Xij=1 Xij=0,1 i=1,n, j=1,m=1 (分派操作員i完成任務j)=0 (不分派操作員i完成任務j)ji最短路問題最短路問題G(V,E) 為 連通圖，邊（vi,vj)的權為lij，求一條道路，使它從vs到vt的總權最少？方法：1 動態(tài)規(guī)劃法 2 Dijkstra算法引例：某一配送中心要給一個快餐店送快餐原料，應按什么路線送貨才能使送貨時間最短？V2 16 v4 7 v64 6V1 12 2 8 v718 5V3 6 v5（配送中