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

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

—企業(yè)加工甲、乙、丙三種產(chǎn)品數(shù)量，i=1,2,3。x4、x5—由外協(xié)鑄造后再由本企業(yè)機加工和裝配甲、乙兩種產(chǎn)品數(shù)量；目標函數(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元目標函數(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值不停地增加，到達B點時，到達最大；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頁時序與路徑規(guī)劃討論各種時序規(guī)劃問題介紹時序規(guī)劃標準分配問題運輸問題網(wǎng)絡最短路徑網(wǎng)絡最大流醫(yī)療行業(yè)模型決策法分析第16頁時序規(guī)劃問題

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

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

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

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

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

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

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

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

第i個操作員完成第j項任務成本Xij

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