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

2、函數：MAX 50 x1+100 x2 （3）約束條件：subject to (s.t.): x1+x2 300 2x1+x2 400 x2 250 x1,x2 0 規劃與決策規劃與決策線性規劃模型： max 50 x1+100 x2 s.t. x1+x2 300 2x1+x2 400 x2 250 x1,x2 0規劃與決策規劃與決策線性規劃模型的一般形式線性規劃模型的一般形式 max c1x1+c2x2+ + cn xn s. t. a11x1 + + a1nx n (,=) b1 a21x1 + + a2nx n (,=) b2 am1x1 + + amnx n (,=) bm xij 0

3、 i = 1, ,n, j =1, ,m規劃與決策規劃與決策線性規劃應用領域線性規劃應用領域： 合理利用板、線材問題； 配料問題； 投資問題； 生產計劃問題、勞動力安排問題； 運輸問題、電子商務配送問題； 企業決策問題；企業或商業競爭對策問題等。規劃與決策規劃與決策一一般線性規劃建模過程般線性規劃建模過程Step 1. 理解及分析實際問題，資源狀況，解決問題實現的目標；Step 2. 確定決策變量（x1, ，xn） 解決問題的具體方案（量化方案）；Step 3. 確定目標函數及約束條件；Step 4. 應用線性規劃軟件求解；Step 5. 檢驗所求得的解決方案是否可行：如可行，則開始具體實施；

4、否則，轉Step 1 或 Step2 修改模型。規劃與決策規劃與決策案例2：（生產計劃問題）某公司面臨一個外協加工還是自行生產問題。該公司生產甲、乙、丙三種產品，這三種產品都需要經過鑄造、機加工和裝配三個車間。甲、乙兩種產品的鑄造可以外協加工，亦可以自行生產。但丙產品的鑄造必須自行生產才能保證質量。有關數據見下表：規劃與決策規劃與決策工時與成本甲乙丙總工時每件鑄造工時（小時）51078000每件機加工工時（小時）64812000每件裝配工時（小時）32210000自產鑄件每件成本（元）354外協鑄件每件成本（元）56-機加工每件成本（元）213裝配每件成本（元）322每件產品售價（元）2318

5、16問題：如何安排生產計劃，使公司獲利最大？規劃與決策規劃與決策分析：設 xi 公司加工甲、乙、丙三種產品數量，i=1,2,3。x4、x5由外協鑄造后再由本公司機加工和裝配的甲、 乙兩種產品數量；目標函數： 每件產品利潤分別是：每件x1產品利潤: 23-（3+2+3） =15元每件x2產品利潤: 18-（5+1+2） =10元每件x3產品利潤: 16-（4+3+2） =7元每件x4產品利潤: 23-（5+2+3） =13元每件x5產品利潤: 18-（6+1+2） =9元目標函數為： max 15 x1+10 x2+7 x3+13 x4+9 x5規劃與決策規劃與決策約束條件： 5 x1+10 x

6、2+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規劃與決策規劃與決策圖解法: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 的值不斷地增加，達到B點時， 達到最大；Step 4. 最優解為B=(50,250), z最大=27500。規劃與決策規劃與決策 0 100 200 3003

7、00200100D圖 2-1規劃與決策規劃與決策 0 100 200 300300200100DB(50,250)Z= 50 x1+100 x2圖 2-2時序與路徑規劃時序與路徑規劃 討論各種時序規劃問題討論各種時序規劃問題 介紹時序規劃原則介紹時序規劃原則 分派問題分派問題 運輸問題運輸問題 網絡的最短路徑網絡的最短路徑 網絡的最大流網絡的最大流時序規劃問題時序規劃問題 ABEFDC機器機器DEFCAB等待處理的一批工作按最優次序排隊一臺機器工作的時序規劃一臺機器工作的時序規劃時序規劃問題時序規劃問題原則：原則：(1) 最緊迫的優先最緊迫的優先實例實例 1： 6種部件作為一批等待一臺機器加工

8、。每一部件的平均周需求量、當前的存貨水平以及加工一批所需時間如下表，你將如何安排各種部件的生產次序？ 部 件 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時序規劃問題時序規劃問題 1最緊迫的優先最緊迫的優先23數據數據4項目ABCDEF5當前存貨7221489228236平均需求1042634737存貨用完的時間7,205,251,852,714,007,6789經整理的數據經整理的數據10存貨用完的時間1,852,714,005,257,207,6711項目CDEBA

9、F12當前存貨48922821722313平均需求2634741031415生產時間0,50,51,01,52,01,516開始生產時間0,00,51,02,03,55,517完成生產時間0,51,02,03,55,57,018容余時間1,41,72,01,81,70,7時序規劃問題時序規劃問題 23數據數據4項目ABCDEF5當前存貨7221489228236平均需求1042634737存貨用完的時間7,205,251,852,714,007,6789經整理的數據經整理的數據10存貨用完的時間1,852,714,005,257,207,6711項目CDEBAF12當前存貨4892282172

10、2313平均需求2634741031415生產時間0,50,51,01,52,01,516開始生產時間0,00,51,02,03,55,517完成生產時間0,51,02,03,55,57,018容余時間1,351,7121,751,70,67時序規劃問題時序規劃問題 ABCDEFGHI1加工時間最短者優先加工時間最短者優先23數據數據4工作ABCDEFGH5加工時間2538472367整理后數據整理后數據8工作AGCHEBFD9加工時間223345781011 開始加工時間0,02,04,07,010,014,019,026,012 完成加工時間2,04,07,010,014,019,026,

11、034,0以“加工時間最短者優先”為原則時序規劃問題時序規劃問題 23數據數據4工作ABCDEFGH5加工時間2538472367整理后數據整理后數據8工作AGCHEBFD9加工時間223345781011 開始加工時間0,02,04,07,010,014,019,026,012 完成加工時間2,04,07,010,014,019,026,034,0以“加工時間最短者優先”為原則時序規劃問題時序規劃問題(3) 到期日最近者原則到期日最近者原則BCDEFGHIABCDEFGH1378301420236GBCAEFDH2781314203036253247830,02,07,010,012,016

12、,023,031,02,07,010,012,016,023,031,034,00,00,02,00,02,03,01,00,0時序規劃問題時序規劃問題(3) 到期日最近者原則到期日最近者原則BCDEFGHIABCDEFGH1378301420236GBCAEFDH2781314203036253247830,02,07,010,012,016,023,031,02,07,010,012,016,023,031,034,00,00,02,00,02,03,01,00,0時序規劃問題時序規劃問題(4) 延誤的工作項目最少延誤的工作項目最少第1步：運用先到期者優先的原則排出工作的初始次序。如果已經

13、沒有工作被延誤，這便是最優解，否則，則進行第2步。第2步：在安排的時序中找到1項延誤的工作。第3步：找出第2步所找工作之前（包括這一工作本身）加工時間最長的工作。第4步：將這一工作從時序安排中抽出來，并更新相應的時間。如果仍然有被延誤的工作，再轉向第2步，否則轉向第5步。第5步：將第4步抽出的工作放到時序的末尾。實例實例 3：沿用上述實例的8項工作，求解工作延誤項數最少的時序。 為此我們采用上述五個步驟。 工 作 A B C D E F G H 加工時間 2 5 3 8 4 7 2 3 到期時間 13 7 8 30 14 20 2 36時序規劃問題時序規劃問題第1步：將工作按到期時間排序。 工

14、 作 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在內，加工時間最長的工作是B，加工時間為5。時序規劃問題時序規劃問題第4步：抽出工作B，更新相關的時間： 工 作 G C A E F D H 到期時間 2 8 13 14 20 30 36 開始加工時間 0 2 5 7 11 18 26 加工時間 2 3 2

15、 4 7 8 3 完成加工時間 2 5 7 11 18 26 29第5步：現在已經沒有工作被延誤了，所以我們將工作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 現在只有一項工作被延誤，平均排隊時間為98/8=12.25，平均延誤時間為27/8=3.375天。時序規劃問題時序規劃問題(5) Johnsons rule(約翰遜原則約翰遜原則)步驟1：列出各項工作及它們在每臺機器上的加

16、工時間。步驟2：找出下一個在各臺機器上加工時間最短的工作。步驟3：如果這是在機器1上，盡量將這一工作安排在前面；如果這是在機器2上，盡量將這一工作安排在后面。在重復做這些的時候，總是從時序的兩端向內進行，新安排的工作離時序的中間更近。步驟4：不必再考慮這一工作，回到步驟2。如果再找不到這樣的任務，這就是最優解。 實例 4： 有7項工作要順序經過機器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時序規劃問題時序規劃問題 ABCDEFGH1約

17、翰遜原則約翰遜原則23工作ABCDEFG4在機器1上的時間2510741295在機器2上的時優時序AEBDGFC8在機器1上開始的時間026111928409在機器1上完成的時間26111928405010 在機器2上開始的時間216212838445011 在機器2上完成的時間16212838445053時序規劃問題時序規劃問題 23工作ABCDEFG4在機器1上的時間2510741295在機器2上的時優時序AEBDGFC8在機器1上開始的時間026111928409在機器1上完成的時間26111928405010 在機器2上開始的時間216212838445011 在機器2上完成的時間16212838445053分派問題分派問題如何以總成本最低為目標將操作員分派到各臺機器上。原則：每個操作員只能分派給一項任務，每項任務只能由一人完成。 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 動態規劃法 2 Dijkst