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

第六章模型決議法線性規(guī)劃等時(shí)序與路徑規(guī)劃分配問題最短路問題最大流問題醫(yī)療行業(yè)模型決策法分析第1頁模型決議法優(yōu)化模型max(min)目標(biāo)函數(shù)s.t.約束條件醫(yī)療行業(yè)模型決策法分析第2頁線性規(guī)劃模型建立實(shí)例1兩種產(chǎn)品生產(chǎn)。已知生產(chǎn)單位產(chǎn)品所需設(shè)備臺時(shí)及A、B兩種原材料消耗，資源限制及市場價(jià)格以下表： Ⅰ Ⅱ 資源限制 設(shè)備 1 1 300臺時(shí) 原材料A 2 1 400千克 原材料B 0 1 250千克 市場價(jià)格 50 100 問題：怎樣安排生產(chǎn)，才能使工廠贏利最多？醫(yī)療行業(yè)模型決策法分析第3頁規(guī)劃與決議分析：（1）設(shè)x1—生產(chǎn)產(chǎn)品Ⅰ數(shù)量；

x2—生產(chǎn)產(chǎn)品Ⅱ數(shù)量。（2）目標(biāo)函數(shù)：MAX50x1+100x2（3）約束條件：subjectto(s.t.):

x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0醫(yī)療行業(yè)模型決策法分析第4頁規(guī)劃與決議線性規(guī)劃模型：

max50x1+100x2

s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0醫(yī)療行業(yè)模型決策法分析第5頁規(guī)劃與決議線性規(guī)劃模型普通形式

maxc1x1+c2x2+…+cnxn

s.t.a11x1+…+a1nxn≤(≥,=)b1a21x1+…+a2nxn≤(≥,=)b2

…am1x1+…+amnxn≤(≥,=)bm

xij≥0i=1,…,n,j=1,…,m醫(yī)療行業(yè)模型決策法分析第6頁規(guī)劃與決議線性規(guī)劃應(yīng)用領(lǐng)域：合理利用板、線材問題；配料問題；投資問題；生產(chǎn)計(jì)劃問題、勞動力安排問題；運(yùn)輸問題、電子商務(wù)配送問題；企業(yè)決議問題；企業(yè)或商業(yè)競爭對策問題等。醫(yī)療行業(yè)模型決策法分析第7頁規(guī)劃與決議一般線性規(guī)劃建模過程Step1.了解及分析實(shí)際問題，資源情況，處理問題實(shí)現(xiàn)目標(biāo)；Step2.確定決議變量（x1,…，xn）—處理問題詳細(xì)方案（量化方案）；Step3.確定目標(biāo)函數(shù)及約束條件；Step4.應(yīng)用線性規(guī)劃軟件求解；Step5.檢驗(yàn)所求得處理方案是否可行：如可行，則開始詳細(xì)實(shí)施；不然，轉(zhuǎn)Step1或Step2修改模型。醫(yī)療行業(yè)模型決策法分析第8頁規(guī)劃與決議案例2：（生產(chǎn)計(jì)劃問題）某企業(yè)面臨一個外協(xié)加工還是自行生產(chǎn)問題。該企業(yè)生產(chǎn)甲、乙、丙三種產(chǎn)品，這三種產(chǎn)品都需要經(jīng)過鑄造、機(jī)加工和裝配三個車間。甲、乙兩種產(chǎn)品鑄造能夠外協(xié)加工，亦能夠自行生產(chǎn)。但丙產(chǎn)品鑄造必須自行生產(chǎn)才能確保質(zhì)量。相關(guān)數(shù)據(jù)見下表：醫(yī)療行業(yè)模型決策法分析第9頁規(guī)劃與決議工時(shí)與成本 甲 乙 丙 總工時(shí) 每件鑄造工時(shí)（小時(shí)） 5 10 7 8000 每件機(jī)加工工時(shí)（小時(shí)） 6 4 8 1 每件裝配工時(shí)（小時(shí)） 3 2 2 10000 自產(chǎn)鑄件每件成本（元） 3 5 4 外協(xié)鑄件每件成本（元） 5 6 - 機(jī)加工每件成本（元） 2 1 3 裝配每件成本（元） 3 2 2 每件產(chǎn)品售價(jià)（元） 23 18 16 問題：怎樣安排生產(chǎn)計(jì)劃，使企業(yè)贏利最大？醫(yī)療行業(yè)模型決策法分析第10頁規(guī)劃與決議分析：設(shè)xi

—企業(yè)加工甲、乙、丙三種產(chǎn)品數(shù)量，i=1,2,3。x4、x5—由外協(xié)鑄造后再由本企業(yè)機(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ù)為：max15x1+10x2+7x3+13x4+9x5醫(yī)療行業(yè)模型決策法分析第11頁規(guī)劃與決議約束條件：5x1+10x2+7x3

≤80006x1+4x2+8x3+6x4+4x5

≤13x1+2x2+2x3+3x4+2x5

≤10000xi

≥0i=1,…,5醫(yī)療行業(yè)模型決策法分析第12頁規(guī)劃與決議圖解法:Step1.確定可行域D={x|x滿足上述約束條件}以下列圖2-1：Step2.確定直線50x1+100x2=0以下列圖2-2：Step3.向上移動直線50x1+100x2=0如圖2-2，z=50x1+100x2值不停地增加，到達(dá)B點(diǎn)時(shí)，到達(dá)最大；Step4.最優(yōu)解為B=(50,250),z最大=27500。醫(yī)療行業(yè)模型決策法分析第13頁規(guī)劃與決議

0100200300300200100D圖2-1醫(yī)療行業(yè)模型決策法分析第14頁規(guī)劃與決議

0100200300300200100DB(50,250)Z=50x1+100x2圖2-2醫(yī)療行業(yè)模型決策法分析第15頁時(shí)序與路徑規(guī)劃討論各種時(shí)序規(guī)劃問題介紹時(shí)序規(guī)劃標(biāo)準(zhǔn)分配問題運(yùn)輸問題網(wǎng)絡(luò)最短路徑網(wǎng)絡(luò)最大流醫(yī)療行業(yè)模型決策法分析第16頁時(shí)序規(guī)劃問題

ABEFDC機(jī)器機(jī)器DEFCAB等候處理一批工作按最優(yōu)次序排隊(duì)一臺機(jī)器工作時(shí)序規(guī)劃醫(yī)療行業(yè)模型決策法分析第17頁時(shí)序規(guī)劃問題標(biāo)準(zhǔn)：(1)最緊迫優(yōu)先實(shí)例1：6種部件作為一批等候一臺機(jī)器加工。每一部件平均周需求量、當(dāng)前存貨水平以及加工一批所需時(shí)間以下表，你將怎樣安排各種部件生產(chǎn)次序？部件ABCDEF平均需求量104263473當(dāng)前存貨量722148922823加工時(shí)間2.01.50.50.51.01.5醫(yī)療行業(yè)模型決策法分析第18頁時(shí)序規(guī)劃問題

醫(yī)療行業(yè)模型決策法分析第19頁時(shí)序規(guī)劃問題

醫(yī)療行業(yè)模型決策法分析第20頁時(shí)序規(guī)劃問題

以“加工時(shí)間最短者優(yōu)先”為標(biāo)準(zhǔn)醫(yī)療行業(yè)模型決策法分析第21頁時(shí)序規(guī)劃問題

以“加工時(shí)間最短者優(yōu)先”為標(biāo)準(zhǔn)醫(yī)療行業(yè)模型決策法分析第22頁時(shí)序規(guī)劃問題(3)到期日最近者標(biāo)準(zhǔn)醫(yī)療行業(yè)模型決策法分析第23頁時(shí)序規(guī)劃問題(3)到期日最近者標(biāo)準(zhǔn)醫(yī)療行業(yè)模型決策法分析第24頁時(shí)序規(guī)劃問題(4)延誤工作項(xiàng)目最少第1步：利用先到期者優(yōu)先標(biāo)準(zhǔn)排出工作初始次序。假如已經(jīng)沒有工作被延誤，這便是最優(yōu)解，不然，則進(jìn)行第2步。第2步：在安排時(shí)序中找到1項(xiàng)延誤工作。第3步：找出第2步所找工作之前（包含這一工作本身）加工時(shí)間最長工作。第4步：將這一工作從時(shí)序安排中抽出來，并更新對應(yīng)時(shí)間。假如依然有被延誤工作，再轉(zhuǎn)向第2步，不然轉(zhuǎn)向第5步。第5步：將第4步抽出工作放到時(shí)序末尾。實(shí)例3：沿用上述實(shí)例8項(xiàng)工作，求解工作延誤項(xiàng)數(shù)最少時(shí)序。為此我們采取上述五個步驟。工作ABCDEFGH加工時(shí)間25384723到期時(shí)間1378301420236醫(yī)療行業(yè)模型決策法分析第25頁時(shí)序規(guī)劃問題第1步：將工作按到期時(shí)間排序。工作GBCAEFDH到期時(shí)間2781314203036開始加工時(shí)間0271012162331加工時(shí)間25324783完成加工時(shí)間27101216233134延誤工作****第2步：在上述時(shí)序中，第1項(xiàng)被延誤工作是C。第3步：到C之前，包含C在內(nèi)，加工時(shí)間最長工作是B，加工時(shí)間為5。醫(yī)療行業(yè)模型決策法分析第26頁時(shí)序規(guī)劃問題第4步：抽出工作B，更新相關(guān)時(shí)間：工作GCAEFDH到期時(shí)間281314203036開始加工時(shí)間0257111826加工時(shí)間2324783完成加工時(shí)間25711182629第5步：現(xiàn)在已經(jīng)沒有工作被延誤了，所以我們將工作B加到時(shí)序最終。工作GCAEFDHB到期時(shí)間2813142030367開始加工時(shí)間025711182629加工時(shí)間23247835完成加工時(shí)間2571118262934現(xiàn)在只有一項(xiàng)工作被延誤，平均排隊(duì)時(shí)間為98/8=12.25，平均延誤時(shí)間為27/8=3.375天。醫(yī)療行業(yè)模型決策法分析第27頁時(shí)序規(guī)劃問題(5)Johnson’srule(約翰遜標(biāo)準(zhǔn))步驟1：列出各項(xiàng)工作及它們在每臺機(jī)器上加工時(shí)間。步驟2：找出下一個在各臺機(jī)器上加工時(shí)間最短工作。步驟3：假如這是在機(jī)器1上，盡可能將這一工作安排在前面；假如這是在機(jī)器2上，盡可能將這一工作安排在后面。在重復(fù)做這些時(shí)候，總是從時(shí)序兩端向內(nèi)進(jìn)行，新安排工作離時(shí)序中間更近。步驟4：無須再考慮這一工作，回到步驟2。假如再找不到這么任務(wù)，這就是最優(yōu)解。

實(shí)例4：有7項(xiàng)工作要次序經(jīng)過機(jī)器1和機(jī)器2加工。每項(xiàng)工作在每臺機(jī)器上所需加工時(shí)間以下，怎樣安排時(shí)序才能使機(jī)器利用率最高。工作ABCDEFG機(jī)器1251084129機(jī)器2147310566醫(yī)療行業(yè)模型決策法分析第28頁時(shí)序規(guī)劃問題

醫(yī)療行業(yè)模型決策法分析第29頁時(shí)序規(guī)劃問題

醫(yī)療行業(yè)模型決策法分析第30頁分配問題怎樣以總成本最低為目標(biāo)將操作員分配到各臺機(jī)器上。標(biāo)準(zhǔn)：每個操作員只能分配給一項(xiàng)任務(wù)，每項(xiàng)任務(wù)只能由一人完成。Cij

第i個操作員完成第j項(xiàng)任務(wù)成本Xij

minΣΣCijXijΣXij=1ΣXij=1Xij=0,1i=1,…,n,j=1,…,m=1(分配操作員i完成任務(wù)j)=0(不分配操作員i完成任務(wù)j)ji醫(yī)療行業(yè)模型決策法分析第31頁最短路問題最短路問題G(V,E)為連通圖，邊（vi,vj)權(quán)為lij，求一條道路，使它從vs到vt總權(quán)最少？方法：1動態(tài)規(guī)劃法2Dijkstra算法引例：某一配送中心要給一個快餐店送快餐原料，應(yīng)按什么路線送貨才能使送貨時(shí)間最短？醫(yī)療行業(yè)模型決策法分析第32頁V216v47v64