第六章 模型決策法

1、第六章 模型決策法模型決策法優(yōu)化模型max (min) 目標(biāo)函數(shù)目標(biāo)函數(shù) s. t. 約束條件約束條件線性規(guī)劃模型的建立線性規(guī)劃模型的建立實(shí)例 1 兩種產(chǎn)品的生產(chǎn)。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，資源限制及市場(chǎng)價(jià)格如下表： 資源限制設(shè)備11300臺(tái)時(shí)原材料A21400千克原材料B01250千克市場(chǎng)價(jià)格50100問(wèn)題：如何安排生產(chǎn)，才能使工廠獲利最多？規(guī)劃與決策規(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.): x1+x2 300 2x1+x2 40

2、0 x2 250 x1,x2 0 規(guī)劃與決策規(guī)劃與決策線性規(guī)劃模型： max 50 x1+100 x2 s.t. x1+x2 300 2x1+x2 400 x2 250 x1,x2 0規(guī)劃與決策規(guī)劃與決策線性規(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ī)劃與決策線性規(guī)劃應(yīng)用領(lǐng)域：線性規(guī)劃應(yīng)用領(lǐng)域： 合理利用板、線材問(wèn)題； 配料問(wèn)題；

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

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

5、x4、x5由外協(xié)鑄造后再由本公司機(jī)加工和裝配的甲、 乙兩種產(chǎn)品數(shù)量；目標(biāo)函數(shù)： 每件產(chǎn)品利潤(rùn)分別是：每件x1產(chǎn)品利潤(rùn): 23-（3+2+3） =15元每件x2產(chǎn)品利潤(rùn): 18-（5+1+2） =10元每件x3產(chǎn)品利潤(rùn): 16-（4+3+2） =7元每件x4產(chǎn)品利潤(rùn): 23-（5+2+3） =13元每件x5產(chǎn)品利潤(rùn): 18-（6+1+2） =9元目標(biāo)函數(shù)為： max 15 x1+10 x2+7 x3+13 x4+9 x5規(guī)劃與決策規(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

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

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

8、求量 10 4 26 34 7 3 當(dāng)前存貨量 72 21 48 92 28 23 加工時(shí)間 2.0 1.5 0.5 0.5 1.0 1.5時(shí)序規(guī)劃問(wèn)題時(shí)序規(guī)劃問(wèn)題 1最緊迫的優(yōu)先最緊迫的優(yōu)先23數(shù)據(jù)數(shù)據(jù)4項(xiàng)目ABCDEF5當(dāng)前存貨7221489228236平均需求1042634737存貨用完的時(shí)間7,205,251,852,714,007,6789經(jīng)整理的數(shù)據(jù)經(jīng)整理的數(shù)據(jù)10存貨用完的時(shí)間1,852,714,005,257,207,6711項(xiàng)目CDEBAF12當(dāng)前存貨48922821722313平均需求2634741031415生產(chǎn)時(shí)間0,50,51,01,52,01,516開(kāi)始生產(chǎn)時(shí)間0,

9、00,51,02,03,55,517完成生產(chǎn)時(shí)間0,51,02,03,55,57,018容余時(shí)間1,41,72,01,81,70,7時(shí)序規(guī)劃問(wèn)題時(shí)序規(guī)劃問(wèn)題 23數(shù)據(jù)數(shù)據(jù)4項(xiàng)目ABCDEF5當(dāng)前存貨7221489228236平均需求1042634737存貨用完的時(shí)間7,205,251,852,714,007,6789經(jīng)整理的數(shù)據(jù)經(jīng)整理的數(shù)據(jù)10存貨用完的時(shí)間1,852,714,005,257,207,6711項(xiàng)目CDEBAF12當(dāng)前存貨48922821722313平均需求2634741031415生產(chǎn)時(shí)間0,50,51,01,52,01,516開(kāi)始生產(chǎn)時(shí)間0,00,51,02,03,55,51

10、7完成生產(chǎn)時(shí)間0,51,02,03,55,57,018容余時(shí)間1,351,7121,751,70,67時(shí)序規(guī)劃問(wèn)題時(shí)序規(guī)劃問(wèn)題 ABCDEFGHI1加工時(shí)間最短者優(yōu)先加工時(shí)間最短者優(yōu)先23數(shù)據(jù)數(shù)據(jù)4工作ABCDEFGH5加工時(shí)間2538472367整理后數(shù)據(jù)整理后數(shù)據(jù)8工作AGCHEBFD9加工時(shí)間223345781011 開(kāi)始加工時(shí)間0,02,04,07,010,014,019,026,012 完成加工時(shí)間2,04,07,010,014,019,026,034,0以“加工時(shí)間最短者優(yōu)先”為原則時(shí)序規(guī)劃問(wèn)題時(shí)序規(guī)劃問(wèn)題 23數(shù)據(jù)數(shù)據(jù)4工作ABCDEFGH5加工時(shí)間2538472367整理后數(shù)據(jù)

11、整理后數(shù)據(jù)8工作AGCHEBFD9加工時(shí)間223345781011 開(kāi)始加工時(shí)間0,02,04,07,010,014,019,026,012 完成加工時(shí)間2,04,07,010,014,019,026,034,0以“加工時(shí)間最短者優(yōu)先”為原則時(shí)序規(guī)劃問(wèn)題時(shí)序規(guī)劃問(wèn)題(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時(shí)序規(guī)劃問(wèn)題

12、時(shí)序規(guī)劃問(wèn)題(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時(shí)序規(guī)劃問(wèn)題時(shí)序規(guī)劃問(wèn)題(4) 延誤的工作項(xiàng)目最少延誤的工作項(xiàng)目最少第1步：運(yùn)用先到期者優(yōu)先的原則排出工作的初始次序。如果已經(jīng)沒(méi)有工作被延誤，這便是最優(yōu)解，否則，則進(jìn)行第2步。第2步：在安排的時(shí)序中找到1項(xiàng)延誤的工作。第3步：找出第2步所找工作之前（包括這一工作本身

13、）加工時(shí)間最長(zhǎng)的工作。第4步：將這一工作從時(shí)序安排中抽出來(lái)，并更新相應(yīng)的時(shí)間。如果仍然有被延誤的工作，再轉(zhuǎn)向第2步，否則轉(zhuǎn)向第5步。第5步：將第4步抽出的工作放到時(shí)序的末尾。實(shí)例實(shí)例 3：沿用上述實(shí)例的8項(xiàng)工作，求解工作延誤項(xiàng)數(shù)最少的時(shí)序。 為此我們采用上述五個(gè)步驟。 工 作 A B C D E F G H 加工時(shí)間 2 5 3 8 4 7 2 3 到期時(shí)間 13 7 8 30 14 20 2 36時(shí)序規(guī)劃問(wèn)題時(shí)序規(guī)劃問(wèn)題第1步：將工作按到期時(shí)間排序。 工 作 G B C A E F D H 到期時(shí)間 2 7 8 13 14 20 30 36 開(kāi)始加工時(shí)間 0 2 7 10 12 16 23

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

15、 G C A E F D H B 到期時(shí)間 2 8 13 14 20 30 36 7 開(kāi)始加工時(shí)間 0 2 5 7 11 18 26 29 加工時(shí)間 2 3 2 4 7 8 3 5 完成加工時(shí)間 2 5 7 11 18 26 29 34 現(xiàn)在只有一項(xiàng)工作被延誤，平均排隊(duì)時(shí)間為98/8=12.25，平均延誤時(shí)間為27/8=3.375天。時(shí)序規(guī)劃問(wèn)題時(shí)序規(guī)劃問(wèn)題(5) Johnsons rule(約翰遜原則約翰遜原則)步驟1：列出各項(xiàng)工作及它們?cè)诿颗_(tái)機(jī)器上的加工時(shí)間。步驟2：找出下一個(gè)在各臺(tái)機(jī)器上加工時(shí)間最短的工作。步驟3：如果這是在機(jī)器1上，盡量將這一工作安排在前面；如果這是在機(jī)器2上，盡量將這

16、一工作安排在后面。在重復(fù)做這些的時(shí)候，總是從時(shí)序的兩端向內(nèi)進(jìn)行，新安排的工作離時(shí)序的中間更近。步驟4：不必再考慮這一工作，回到步驟2。如果再找不到這樣的任務(wù)，這就是最優(yōu)解。 實(shí)例 4： 有7項(xiàng)工作要順序經(jīng)過(guò)機(jī)器1和機(jī)器2加工。每項(xiàng)工作在每臺(tái)機(jī)器上所需的加工時(shí)間如下，如何安排時(shí)序才能使機(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時(shí)序規(guī)劃問(wèn)題時(shí)序規(guī)劃問(wèn)題 ABCDEFGH1約翰遜原則約翰遜原則23工作ABCDEFG4在機(jī)器1上的時(shí)間2510741295在機(jī)器2上的時(shí)優(yōu)時(shí)序AEBDGFC8

17、在機(jī)器1上開(kāi)始的時(shí)間026111928409在機(jī)器1上完成的時(shí)間26111928405010 在機(jī)器2上開(kāi)始的時(shí)間216212838445011 在機(jī)器2上完成的時(shí)間16212838445053時(shí)序規(guī)劃問(wèn)題時(shí)序規(guī)劃問(wèn)題 23工作ABCDEFG4在機(jī)器1上的時(shí)間2510741295在機(jī)器2上的時(shí)優(yōu)時(shí)序AEBDGFC8在機(jī)器1上開(kāi)始的時(shí)間026111928409在機(jī)器1上完成的時(shí)間26111928405010 在機(jī)器2上開(kāi)始的時(shí)間216212838445011 在機(jī)器2上完成的時(shí)間16212838445053分派問(wèn)題分派問(wèn)題如何以總成本最低為目標(biāo)將操作員分派到各臺(tái)機(jī)器上。原則：每個(gè)操作員只能分派給一項(xiàng)任務(wù)，每項(xiàng)任務(wù)只能由一人完成。 Cij 第i個(gè)操作員完成第j項(xiàng)任務(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)ji最短路問(wèn)題最短路問(wèn)題