醫(yī)療行業(yè)模型決策法分析

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

2、標(biāo)函數(shù)：MAX 50 x1+100 x2 （3）約束條件：subject to (s.t.): x1+x2 300 2x1+x2 400 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

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

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

5、816問題：如何安排生產(chǎn)計劃，使公司獲利最大？規(guī)劃與決策規(guī)劃與決策分析：設(shè) xi 公司加工甲、乙、丙三種產(chǎn)品數(shù)量，i=1,2,3。x4、x5由外協(xié)鑄造后再由本公司機加工和裝配的甲、 乙兩種產(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ī)劃與決策規(guī)劃與決策約束條件： 5 x1+10

6、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ī)劃與決策規(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點時， 達(dá)到最大；Step 4. 最優(yōu)解為B=(50,250), z最大=27500。規(guī)劃與決策規(guī)劃與決策 0 100 200 300

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

8、工。每一部件的平均周需求量、當(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 0.5 1.0 1.5時序規(guī)劃問題時序規(guī)劃問題 1最緊迫的優(yōu)先最緊迫的優(yōu)先23數(shù)據(jù)數(shù)據(jù)4項目ABCDEF5當(dāng)前存貨7221489228236平均需求1042634737存貨用完的時間7,205,251,852,714,007,6789經(jīng)整理的數(shù)據(jù)經(jīng)整理的數(shù)據(jù)10存貨用完的時間1,852,714,005,257,207,6711項目CDEB

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

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

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

12、6,023,031,02,07,010,012,016,023,031,034,00,00,02,00,02,03,01,00,0時序規(guī)劃問題時序規(guī)劃問題(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時序規(guī)劃問題時序規(guī)劃問題(4) 延誤的工作項目最少延誤的工作項目最少第1步：運用先到期者優(yōu)先的原則排出工作的初始次序。如果已

13、經(jīng)沒有工作被延誤，這便是最優(yōu)解，否則，則進(jìn)行第2步。第2步：在安排的時序中找到1項延誤的工作。第3步：找出第2步所找工作之前（包括這一工作本身）加工時間最長的工作。第4步：將這一工作從時序安排中抽出來，并更新相應(yīng)的時間。如果仍然有被延誤的工作，再轉(zhuǎn)向第2步，否則轉(zhuǎn)向第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 30 14 20 2 36時序規(guī)劃問題時序規(guī)劃問題第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在內(nèi)，加工時間最長的工作是B，加工時間為5。時序規(guī)劃問題時序規(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

15、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ī)劃問題時序規(guī)劃問題(5) Johnsons rule(約翰遜原則約翰遜原則)步驟1：列出各項工作及它們在每臺機器上的

16、加工時間。步驟2：找出下一個在各臺機器上加工時間最短的工作。步驟3：如果這是在機器1上，盡量將這一工作安排在前面；如果這是在機器2上，盡量將這一工作安排在后面。在重復(fù)做這些的時候，總是從時序的兩端向內(nèi)進(jìn)行，新安排的工作離時序的中間更近。步驟4：不必再考慮這一工作，回到步驟2。如果再找不到這樣的任務(wù)，這就是最優(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ī)劃問題時序規(guī)劃問題 ABCDEFGH1

17、約翰遜原則約翰遜原則23工作ABCDEFG4在機器1上的時間2510741295在機器2上的時優(yōu)時序AEBDGFC8在機器1上開始的時間026111928409在機器1上完成的時間26111928405010 在機器2上開始的時間216212838445011 在機器2上完成的時間16212838445053時序規(guī)劃問題時序規(guī)劃問題 23工作ABCDEFG4在機器1上的時間2510741295在機器2上的時優(yōu)時序AEBDGFC8在機器1上開始的時間026111928409在機器1上完成的時間26111928405010 在機器2上開始的時間216212838445011 在機器2上完成的時間16212838445053分派問題分派問題如何以總成本最低為目標(biāo)將操作員分派到各臺機器上。原則：每個操作員只能分派給一項任務(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)ji最短路問題最短路問題最短路問題G(V,E) 為 連通圖，邊（vi,vj)的權(quán)為lij，求一條道路，使它從vs到vt的總權(quán)最少？方法：1 動態(tài)規(guī)劃法 2 Dijkst