授课老师李穗玲副教授EMailsuilingnpitedutw

授課老師:李穗玲副专家E-Mail:suiling@.tw作業研究1第1页第1页課程規劃使用教材:MichaelE.Hanna,1996,IntroductiontoManagementScience-MasteringQuantitativeAnalysis林張群、陳可杰譯(Anderson,Sweeney)作業研究參考教材:李茂興譯，作業研究，揚智圖書HamdyA.Taha,OperationResearchanIntroduction,詹弘康，黃遵鉅譯，五南圖書高孔廉＆張緯良，五南圖書AnIntroductiontoManagementScience:QuantitativeApproachestoDecisionMaking,Anderson,Sweeney,,9th版

成績評定:期中考(30%)、期末考(40%)作業、小考及課堂參與(30%)2第2页第2页課程內容管理科學與作業研究介紹(第1週)線性規劃(第2-3週)圖解敏感度分析(第4-5週)線性規劃之應用與軟體求解(第6週)對偶問題及敏感度分析(第7-10週)運輸模型與指派問題(第11-14週)整數規劃(第15-16週)網路模式(第17-18週)3第3页第3页第一章管理科學介紹簡介管理理論管理科學簡史模型管理科學办法解決問題管理科學與職業生涯管理科學與電腦系統4第4页第4页簡介管理科學是一種科學办法。可於協助經理人於決策過程中做出決策。主要在介紹管理科學解決問題办法，以及如何將這些办法應用至管理領域。應用數學工具與模型以解決問題。

5第5页第5页管理理論古典科學管理(組織)行為學派管理(人)數量办法管理系統方式6第6页第6页管理科學簡史泰勒管理科學原則(1800)甘特計劃工作圖巴柏特存貨模型規劃(1912)哈里斯經濟訂購數量模型(1915)藍契司特應用數量办法預測戰爭厄爾朗用排隊模型研究打電話行為模式(1917)許瓦特利用機率與統計發展控制圖表李昂提夫投入產出線性模型第二次世界大戰廣泛應用於軍事(1945)英格蘭、美國作業研究及管理科學學會成立大學開始有相關學術課程(1960)7第7页第7页模型數學模型(抽象)實體或圖像模型(看得見)類比模型(溫度計)8第8页第8页管理科學解決問題步驟認定問題建立模型並搜集資料應用模型並找尋解答評估解答執行結論監督結果9第9页第9页管理科學與職業生涯美國航空(例子)安排空勤人員收益管理值勤時間市場行銷10第10页第10页管理科學與電腦系統管理資訊系統決策支援系統專家系統11第11页第11页課程中使用電腦軟體介紹LINDOEXCEL(線性規劃)12第12页第12页第二章線性規劃簡介將線性規劃問題公式化最大(小)化問題應用求解線性規劃模型虛變數與剩餘變數13第13页第13页將線性規劃問題公式化目標式限制式14第14页第14页最大(小)化問題應用B＆B電子公司案例(最大化)雙穀玉米片公司案例(最小化)路騎者自行公司例15第15页第15页B＆B電子公司案例(最大化)

產品每單位利潤所需之裝配時間所需之監試時間行動電話＄1541呼喊器＄2022總裝配線工作時間36小時總監試線工作時間24小時16第16页第16页雙穀玉米片公司案例(最小化)組成麥米成本(每盎司)＄0.04＄0.03維他命1(單位/每盎司)21維他命2(單位/每盎司)23每包最低要求20單位維他命124單位維他命217第17页第17页路騎者自行公司例產品比賽用車休閒用車利潤＄80＄70裝配時間(小時)23上漆時間(小時)421.為滿足市場需求至少要生產50輛休閒用自行車但不能多於150輛2.比賽用產量不能多於休閒用車3.每星期裝配工人最多工作時數為360小時4.每星期上漆工人最多工作時數為400小時限制18第18页第18页求解線性規劃模型圖解法等利潤法(等成本法)角隅點法單行法(第五章)19第19页第19页等利潤(等成本)法畫出所有限制式並找出可行區域。選擇一點並找出該點目標函數值，畫出此一目標函數線。將目標函數線儘也许往利潤增长(减少成本)方向平行移動，但目標函數線仍必須維持在可行區域內。最適解為目標函數線與可行區域最後交點，找出此點座標及此點目標函數值。20第20页第20页角隅點法畫出所有限制式並找出可行區域。找出可行區域中所有角隅點。算出在每一個角隅點目標函數值。找出最大利潤或是最小成本角隅點目標函數值，即是最佳解。21第21页第21页虛變數與剩餘變數虛變數(<=)剩餘變數(>=)22第22页第22页第三章圖解敏感度分析與電腦求解簡介敏感度分析B＆B電子公司例之Lindo結果分析目標函數係數改變限制式改變－右邊值改變康瑞奇視聽公司生產CD例增长或消去限制式限制式係數改變23第23页第23页簡介本章要學習瞭解最適解中決策變數數值變化敏感度分析24第24页第24页敏感度分析最適解出現在可行區域角隅點，同時也是基本解。改變目標函數係數對於可行區域或可行角隅點並無影響，只是使不同基本解成為最適解。只有限制式改變，才可能改變可行區域及基本可能解。25第25页第25页

B＆B電子公司例之Lindo結果分析MAX15X1+20X2Subjectto4X1+2X2<=36(總裝配時間)X1+2X2<=24(總監督時間)X2<=11(呼喊器需求)X1+X2<=20(總需求)X1,X2>=0(非負限制式)X1：X2：行動電話生產量呼喊器生產量26第26页第26页目標函數係數改變圖解分析（見投影片）Lindo電腦解答（見投影片）27第27页第27页目標函數係數改變可行角隅解不同样目標函數利潤值(X1,X2)15X,+20X216X,+20X220X,+20X240X,+20X241X,+20X2(0,0)00000(0,11)220220220220220(9,0)135144180360*369*(4,10)260*264*280*360*364(2,11)25025226030030228第28页第28页

目標函數係數同時變動時影響可行角隅解不同样目標函數利潤值原始目標函數改變率140﹪改變率200﹪(X1,X2)15X,+20X212X,+28X240X,+30X2(0,0)000(0,11)220308330(9,0)135108360(4,10)260*328460*(2,11)250332*41029第29页第29页限制式改變－右邊值改變對偶價、影子價及改进指數非束縛限制式右邊值改變束縛限制式右邊值改變右邊值改變範圍30第30页第30页康瑞奇視聽公司生產每一CD所需時間部門隨身聽普及型音響豪華型音響裝配12020150監試20530包裝151520裝配時間250小時，監督時間50小時，包裝時間40小時，隨身聽產量至少在10台以上，其它CD類型則在50台以上，問最佳之CD產量為何？單位:分31第31页第31页MAX25X1+30X2+35X3Subjectto120X1+130X2+150X3<=15,000(裝配時間)20X1+35X2+30X3<=3,000(監督時間)15X1+15X2+20X3<=2,400(包裝時間)X1>=10(隨身聽產量限制)X1+X2>=50(其它產量限制)X1,X2,X3>=0(非負限制式)32第32页第32页增长或消去限制式加入限制式(見投影片)消去限制式加入或消除限制式影響33第33页第33页第四章線性規劃應用簡介媒體選擇財務應用多重期間生產表雇用規劃成份混合(調配)問題運輸問題指派問題34第34页第34页簡介藉由行銷、財務規劃、員工排班、生產規劃等實務課題，構建線性規劃問題，以協助業界問題求解。35第35页第35页媒體選擇－摩爾電器公司

(評估公司所使用四種行銷管道，是否達到最大利潤目標)廣告形式成本可傳播人數最多可登载次數電視＄90010,00012電台2002,60015報紙7005,50025週刊4004,20010在考量每週廣告預算不得超過＄12,000，且登载在報紙與週刊上廣告總數至少要有20則，及表中限制下，如何使得四種觀眾人數達到最大。36第36页第36页MAX10,000X1+2,600X2+5,500X3+4,200X4Subjectto

X1<=12電視廣告限制

X2<=15電台廣告限制

X3<=25報紙廣告限制

X4<=10週刊廣告限制900X1+200X2+700X3+400X4<=12,000總預算X3+X4>=20報紙與週刊廣告限制X1,X2,X3,X4>=0非負限制式X1:電視廣告次數X2:電台廣告次數X3:報紙廣告次數,X4:週刊廣告次數

37第37页第37页財務應用(C＆A投資公司例子)有一客戶发售房地產得$200,000交給C&C投資，該公司將此筆錢投資於四種股票，各項投資工具預期收益及可投資最大額度下列表所列，另外該客戶希望投資石油股票額度不得超過政府債券、投資石油及電腦股票總額度不得超過投資於政府債券及公營事業股票60%，在上述之限制下，該公司如何能達到預期報酬率最大？投資項目收益投資最大額度政府債券0.045130,000石油股票0.060100,000電腦股票0.080100,000公營事業股票0.055120,00038第38页第38页MAX0.045X1+0.06X2+0.08X3+0.055X4Subjectto

X1<=130000X2<=100000

X3<=100000

X4<=10

X2<=X4

X2+X3>=0.6(X1+X4)

X1+X2+X3+X4<=00

X1,X2,X3,X4>=0

X1:投資政府債券額度,X2:投資石油股票額度X3:投資電腦股票額度,,X4:投資公營事業股票額度

39第39页第39页

多重期間生產表(麥克葛藍森製造公司)該公司為生產影印機專用零件，当前生產AV7及AV9兩種型式裝配齒輪供影印機使用，三個月個別需求如表所表示，但工廠每月產能為2200單位只能滿足3、4月需求，必須在較早時間多生產以供應5月需求，另AV7及AV9型之單位成本分別為$30、$35，且單位倉儲成本為生產成本1%。由於過去員工流動比率過高，因此公司決定每月最低生產總量至少要為1900單位，求如何才干使得公司之成本最小化？3月4月5月總需求AV7型800100012003000AV9型900100014003300總需求1700260040第40页第40页上個月存貨+本月產量=本月需求+本月月底存貨KeyRelationFunction定義決策變數Xij:i產品於j月生產數量Iij:i產品於j月存貨數量i=1代表AV7型產品i=2代表AV9型產品j=1代表3月j=2代表4月j=3代表5月41第41页第41页MAX30X11+30X12+30X13+35X21+35X22+35X23+0.3I11+0.3I12+0.3I13+0.35I21+0.35I22+0.35I33SubjecttoX11-I11=800X21-I21=900I11+X12-I12=1000I21+X22-I22=1000I12+X13-I13=1200I22+X23-I23=1400X11+X21<=2200X12+X22<=2200X13+X23<=220042第42页第42页X11+X21>=1900X12+X22>=1900X13+X23>=1900X11,X12,X13,X21,X22,X23,I11,I12,I13,I21,I22,I33>=043第43页第43页雇用規劃(家鄉旅館個案)家鄉旅館經理希望能安排足夠接線生使電話能在最短時間內接聽，同時也不希望請太多接線生，只要確定電話能在某個時間內被接聽就可，試就表中所提供之資料，且每一接線生須值勤8小時，求解該雇用多少接線生才干達到成本最小目標。班次上班下班接線生人數18點12點232121618316203242024165凌晨486481044第44页第44页MinX1+X2+X3+X4+X5+X6SubjecttoX1+X6>=23X1+X2>=18X2+X3>=32

X3+X4>=16

X4+X5>=8

X5+X6>=10X1,X2,X3,X4,X5,X6>=0X1,X2,X3,X4,X5,X6分別代表1-6班次雇用人數45第45页第45页成份混合問題(羅培特燃料例子)該公司生產普級、高級及特級三種汽油，此三種燃料皆由A、B原油混合而成，A、B原油有兩種成份是決定汽油辛烷值，其中A原油成份1佔40%，成份2佔55%。B原油成份1佔52%，成分2佔38%。原油A每加侖成本為$0.42，原油B每加侖成本為$0.47，為達到所要求辛烷值，普級汽油至少要41%成份1、高級汽油至少要44%，特級汽油至少要48%。為滿足顧客需求，該公司必須生產20,000加侖普級油、15,000加侖高級油、10,000加侖特級汽油，試問在符合上述限制下如何決定最小成本來生產此三種燃料？46第46页第46页MIN0.42X11+0.42X12+0.42X13+0.47X21+0.47X22+0.47X23Subjectto0.40X11+0.52X21-0.41(X11+X21)>=00.40X12+0.52X22-0.44(X12+X22)>=00.40X13+0.52X23-0.48(X13+X23)>=0X11+X21>=0X12+X22>=15000X13+X23>=10000X11,X12,X13,X21,X22,X23>=047第47页第47页運輸成本最小問題(凱普特電機公司)Lubbock(100)LakeCharles(180)Mobile(150)Miami(210)Atlanta(100)Dollas(120)來源終點起迄點MiamiDallasAtlantaLubbock$625Mobile384LakeCharles767運輸成本48第48页第48页MIN6X11+2X12+5X13+3X21+8X22+4X23+7X31+6X32+7X33SubjecttoX11+X12+X13<=100X21+X22+X23<=150X31+X32+X33<=180X11+X21+X31=210X12+X22+X32=120X13+X23+X33=100X11,X12,X13,X21,X22,X23,X31,X32,X33>=049第49页第49页轉運運輸、成本及需求(佛洛斯提機械公司)多倫多底特律芝加哥水牛城紐約費城聖路易來源配銷中心供應商$4757$323134600單位500單位450單位350單位300單位若佛洛斯提機械公司希望在不超出工廠產能且能滿足市場需求情況下，該如何尋求最小運輸成本？50第50页第50页X13,X14,X23,X24,X35,X36,X37,X45,X46,X47>=0MIN4X13+7X14+5X23+7X24+3X35+2X36+3X37+X45+3X46

+4X47SubjecttoX13+X14<=600X23+X24<=500X35+X45=450X36+X46=350X37+X47=300X13+X23=X35+X36+X37X14+X24=X45+X46+X4751第51页第51页指派問題(艾里堡建築公司例)艾里堡建築公司有三種機器設備準備下星期開始工作，請根據表中所列各機器於各項工作所需時間資料，提供經理尼克該如何指派那一部機器從事那一工作，才干達到於最短工作天數完毕工作？機器設備工作1工作2工作3A10149B8165C7144各機器設備於各工作所需之工作天數52第52页第52页MIN10X11+14X12+9X13+8X21+16X22+5X23+7X31+14X32

+4X33SubjecttoX11+X12+X13<=1X21+X22+X23<=1X31+X32+X33<=1X11+X21+X31=1X12+X22+X32=1X13+X23+X33=1X11,X12,X13,X21,X22,X23,X31,X32,X33>=053第53页第53页第五章單行法與敏感度分析簡介單形法求解之前置工作單行法之求解方式(講義檔)最大化與最小化問題求解(Word檔)敏感度分析目標函數係數改變右邊值改變對偶問題分析54第54页第54页MAX15X1+20X2MAX15X1+20X2+S1+S2

Subjectto4X1+2X2<=36Subjectto4X1+2X2+S1=36

X1+2X2<=24X1+2X2+S2=24X1,X2>=0X1,X2,S1,S2>=0

求解前之前置工作B&B電子公司範例Cj基本變數152000右邊值X1X2S1S20S14210360S2120124Zj00000Cj-Zj15200055第55页第55页最大化問題之單行法求解過程Cj基本變數152000右邊值X1X2S1S20S14210360S2120124Zj00000Cj-Zj152000主軸欄：Cj-Zj值大者主軸列：替换率(右邊值/欲進入變數係數)最小者主軸欄主軸列表一56第56页第56页Cj基本變數152000右邊值X1X2S1S20S1301-11220X21/2

101/212Zj1020010240Cj-Zj500-10表二新第二列=1/2(120124)=(1/2101/212)新第一列=(421036)-2(1/2101/212)=(301-112)

臨界率12/3=4,12/1/2=2457第57页第57页Cj基本變數152000右邊值X1X2S1S215X1101/3-1/3420X20

1-1/62/310Zj15205/325/3260Cj-Zj00-5/3-25/3表三新第一列=1/3(301-112)=(101/3-1/34)新第二列=(1/2101/212)-1/2(101/3-1/34)=(01-1/62/310)58第58页第58页司威福公司範例每件T恤單位成本為＄4，每件背心單位成本為＄5，決定要生產30件，其中T恤至少要生產10件以上，總共要印製標誌有100個，每件T恤要4個，每件背心要2個，公司該如何生產T恤及背心生產量以達到成本最小目標？MIN4X1+5X2SubjecttoX1+X2=30X1>=104X1+2X2<=100X1,X2>=059第59页第59页Cj基本變數45MM00右邊值X1X2A1A2S2S3MA1111000

30MA21001-10100S3420001

100Zj2MMMM-M040MCj-Zj4-2M5-M00M0

MIN4X1+5X2+MA1+MA2+0S2+0S3

SubjecttoX1+X2+A1=30

X1–S2+A2=104X1+2X2+S3=100X1,X2,A1,A2,S2,S3>=0表一60第60页第60页Cj基本變數45MM00右邊值X1X2A1A2S2S3MA1011-110204X11001-10100S3020-44160Zj4MM-M+4M-4020M+40Cj-Zj05-M02M-4-M+40表二新第一列：（11100030）-（1001–1010）=(011–11020)新第三列：(420001100)–4(1001–1010)=(020–44160)61第61页第61页Cj基本變數45MM00右邊值X1X2A1A2S2S3MA10½100-1/45MX21½000¼250S20½0-11¼15Zj41/2M+2M00-1/4M+15M+100Cj-Zj03-1/2M0M01/4M-1表三新第三列：1/4(020–44160)=(01/20–111/415)新第一列：（011–11020）-（01/20–111/415）=(01/2100–1/45)新第二列：（1001-1010）+（01/20–111/415）=(11/20001/425)

62第62页第62页Cj基本變數45MM00右邊值X1X2A1A2S2S35X101200-1/2104X210-100½200S200-1-11½10Zj45600-1/2130Cj-Zj00M-6M01/2表四新第一列：2（01/2100–1/45）=(01200–1/210)新第二列：（11/20001/425）-1/2(01200–1/210)=(10–1001/220)新第三列：(01/20–111/415)–1/2(01200–1/210)=(00–1–111/210)63第63页第63页亞靈頓皮箱公司產品利潤以及所需生產資源利潤工時需用倉位普通型$3021實用型$6051MAX30X1+90X2Subjectto2X1+5X2<=80(總可用工時)X1+X2<=25(總可用倉位)X1,X2>=0(非負限制式)X1,X2分別表示每星期普通型、實用型行李箱產量64第64页第64页敏感度分析

1.目標函數係數改變

2.右邊值改變

最適解單行表Cj基本變數309000右邊值X1X2S1S290X20.410.20160S20.60-0.219Zj36901801440Cj-Zj-60-18065第65页第65页Cj基本變數C19000右邊值X1X2S1S290X20.410.20160S20.60-0.219Zj36901801440Cj-ZjC1-360180評估X1目標函數係數改變影響66第66页第66页評估X2目標函數係數改變影響Cj基本變數30C200右邊值X1X2S1S2C2X20.410.20160S20.60-0.219Zj0.4C2C20.2C2016C2Cj-Zj30-0.4C20-0.2C2067第67页第67页Cj基本變數309000右邊值X1X2S1S290X20.410.20160S20.60-0.219Zj36901801440Cj-Zj-60-1802.右邊值改變對偶價影子價

68第68页第68页對偶問題1.將對偶問題公式化對偶限制式數目會等於原始問題變數數目。對偶問題中目標函數數目等於原始問題中限制式數目。原始問題中限制式右邊值會變成對偶問題中目標函數係數值。原始問題中目標函數係數值會變成對偶問題中限制式右邊值。2.原始問題與對偶問題最適解關係69第69页第69页Cj基本變數309000右邊值X1X2S1S290X20.410.20160S20.60-0.219Zj36901801440Cj-Zj-60-180Cj基本變數802500右邊值U1U2S’1S’280U110.20-0.2180S’10-0.61-0.46Zj80160-161440Cj-Zj0

90

16對偶問題原始問題70第70页第70页第六章運輸問題與指派問題簡介運輸法西北角法(建立最初解)踏腳石法(評估現有解)其它最初解办法修正分派法評估空格運輸問題特例指派問題匈牙利法指派問題特例71第71页第71页凱普特電子公司運送馬達單位成本起點終點MiamiDallasAtlanta供給量Lubbock$625100Mobile384150LakeCharles767180需求量21012010043072第72页第72页步驟1：建立一平衡運輸表（滿足供需條件）步驟2：找出一個最初解(以西北角法、最小成本法及差額法求解)步驟3：用踏腳石法或修正分派法去計算每一空格評估指標。在最小化問題中，最適解出現在所有評估指標都為正數或0步驟4：選擇一個單位改进幅度最大空格，用進階路徑找出一個較好解，之後再重複步驟3運輸法73第73页第73页起點終點MiamiDallasAtlanta供給Lubbock

100

625100Mobile

110

340

84150LakeCharles780

6100

7180需求210120100430西北角法之應用總成本=6*100+3*110+8*40+6*80+7*100=243074第74页第74页起點終點MiamiDallasAtlanta供給Lubbock-100

6+25100Mobile+110

3-40

84150LakeCharles780

6100

7180需求210120100踏腳石法Lubbock－Dallas評估指標=+2-6+3-8=-975第75页第75页起點終點MiamiDallasAtlanta供給Lubbock

100

625100Mobile-110

3+40

84150LakeCharles+7-80

6100

7180需求210120100LakeCharles－Miami評估指標=+7-3+8-6=676第76页第76页Mobile－Atlanta評估指標=+4-7+6-8=-5起點終點MiamiDallasAtlanta供給Lubbock100625100Mobile1103-40

8+4150LakeCharles7+80

6-100

7180需求21012010077第77页第77页起點終點MiamiDallasAtlanta供給Lubbock-100

62+5100Mobile+110

3-40

84150LakeCharles7+80

6-100

7180需求210120100LakeCharles－Atlanta評估指標=+5-6+3-8+6-7=-778第78页第78页起點終點MiamiDallasAtlanta供給Lubbock-

6100-40+20+40+5100Mobile+3-110+40840-404150LakeCharles7

６801007180需求210120100進階路徑中改變由Lubbock-Dallas79第79页第79页起點終點MiamiDallasAtlanta供給Lubbock60

6

40

25100Mobile150

3

84150LakeCharles780

6100

7180需求210120100總成本=6*60+3*150+2*40+6*80+7*100=2070第二解Lubbock－Atlanta評估指標=+5-2+6-7=+2Mobile－Dallas評估指標=+8-3+6-2=+9Mobile－Atlanta評估指標=+4-7+6-2+6-3=+4LakeCharles－Miami評估指標=+7-6+2-6=-380第80页第80页繼續尋找最適解起點終點MiamiDallasAtlanta供給Lubbock

6-60-60

2+40+605100Mobile

3150

84150LakeCharles7+0+60

6-80-607100180需求21012010081第81页第81页起點終點MiamiDallasAtlanta供給Lubbock

6100

25100Mobile150

3

84150LakeCharles

60720

6100

7180需求210120100總成本=3*150+7*60+2*100+6*20+7*100=1890第三解(最適解)Lubbock－Miami評估指標=+6-2+6-7=+3Lubbock－Atlanta評估指標=+5-2+6-7=+2Mobile－Dallas評估指標=+6-2+6-7=+6Mobile－Atlanta評估指標=+4-3+7-7=+182第82页第82页最小成本法：1.用成本最小路徑以滿足行或列條件2.找出成本次低路線，並利用此一路線，重複這過程，直到須求及供給條件被滿足為止。起點終點MiamiDallasAtlanta供給Lubbock

625100Mobile384150LakeCharles７

6

7180需求210120100最小成本法分析步驟10083第83页第83页起點終點MiamiDallasAtlanta供給Lubbock

625100Mobile384150LakeCharles７

6

7180需求210120100150100起點終點MiamiDallasAtlanta供給Lubbock

625100Mobile384150LakeCharles７

6

7180需求2101201001001502084第84页第84页起點終點MiamiDallasAtlanta供給Lubbock

625100Mobile384150LakeCharles７

6

7180需求2101201001001501002060Lubbock－Miami評估指標=+6-2+6-7=+3Lubbock－Atlanta評估指標=+5-2+6-7=+2Mobile－Dallas評估指標=+6-2+6-7=+6Mobile－Atlanta評估指標=+4-3+7-7=+185第85页第85页差額法步驟1：將次低成本減去最小成本，計算出各行列機會成本。步驟2：選擇機會成本最高行或列，用成本最低路徑，再回到步驟1。起點終點MiamiDallasAtlanta供給Lubbock

6251005-2=3Mobile3841504-3=1LakeCharles76

71807-6=1需求210

6-3=31206-2=4*1005-4=186第86页第86页起點終點MiamiDallasAtlanta供給Lubbock

625100Mobile3841504-3=1LakeCharles76

71807-6=1需求210

7-3=4*1208-6=21007-4=3起點終點MiamiDallasAtlanta供給Lubbock

625100Mobile384150LakeCharles76

7180需求210

120100100150601002010087第87页第87页修正分派法評估空格步驟1:任意選擇一個Ri或Kj，將這個值設定為0，假如在選擇這個Ri或Kj時，所選擇列或行是有最多數字格行列，將會有助於之後求解。步驟2:運用Cij=

Ri+Kj步驟3:空格評估值=Cij-Ri-Kj，假如此評估值為正值或0，停止，否則，進入步驟4。步驟4:選擇可使成本下降最多空格，並找出進階路徑，用此一路徑再回步驟1。因為最出解已經改變，因此，必須重新找出所有Ri或Kj值。88第88页第88页K1=0K2=K3=起點終點MiamiDallasAtlanta供給R1=Lubbock

625100R2=Mobile

384150R3=LakeCharles76

7180需求210

1201001001104080100K1=0K2=K3=起點終點MiamiDallasAtlanta供給R1=6Lubbock

625100R2=3Mobile

384150R3=LakeCharles76

7180需求210

120100100110408010089第89页第89页K1=0K2=5K3=起點終點MiamiDallasAtlanta供給R1=6Lubbock

625100R2=3Mobile

384150R3=LakeCharles76

7180需求210

1201001001104080100K1=0K2=5K3=起點終點MiamiDallasAtlanta供給R1=6Lubbock

625100R2=3Mobile

384150R3=1LakeCharles76

7180需求210

120100100110408010090第90页第90页K1=0K2=5K3=6起點終點MiamiDallasAtlanta供給R1=6Lubbock

625100R2=3Mobile

384150R3=1LakeCharles76

7180需求210

1201001001104080100空格評估值=Cij-Ri-KjLubbock－Dallas空格評估值=2-6-5=-9Lubbock－Atlanta空格評估值=5-6-6=-7Mobile－Atlanta空格評估值=4-3-6=-5LakeCharles－Miami空格評估值=7-1-0=691第91页第91页運輸問題特例不平衡問題:加入虛擬列或虛擬行退化解(如圖6.12)多重最適解(如圖6.13)最大化問題:目標函數不同及空格評估值為零或負值才停止禁運路線:用大M來代表高額成本92第92页第92页單行法運輸法限制式行與列決策變數表中格子基本解填有數字格子非基本解空格Cj-Zj空格評估指標最小臨界率行或列中要減去方格最小數目離去變數將有數字格子變成空格進入變數填滿空格虛變數虛擬終點格子人造變數虛擬來源格子單行法與運輸法之比較93第93页第93页指派問題(艾里堡建築公司例)艾里堡建築公司有三種機器設備準備下星期開始工作，請根據表中所列各機器於各項工作所需時間資料，提供經理尼克該如何指派那一部機器從事那一工作，才干達到於最短工作天數完毕工作？機器設備工作1工作2工作3A10149B8165C7144各機器設備於各工作所需之工作天數94第94页第94页匈牙利法步驟1：在每一列中，將所有數字減去該列中最小值，所得出就是各指派办法機會成本。之後能够得出一個新矩陣，在這個新矩陣中，將每一行各個數字減去該行最小值。步驟2：找出矩陣中所有為0欄位，畫出數目至少垂直線或水平線，以涵蓋所有數值為0欄位。假如所畫出直線數目小於列數目，進入步驟3。步驟3：找出不在垂直線與水平線上數值中最小值，之後在找出任二條線交點，將交點上數值減去之前所找出最小值，再回到步驟2。95第95页第95页機器設備工作1工作2工作3A000B260C250匈牙利法步驟一之結果機器設備工作1工作2工作3A150B3110C310096第96页第96页05-22-2C06-22-2B000A工作3工作2工作1機器設備機器設備工作1工作2工作3A00*2B0*40C030*

+21.指派機器A從事工作214天指派機器B從事工作18天指派機器C從事工作34天總工作天數26天97第97页第97页機器設備工作1工作2工作3A00*2B040*C0*30指派機器A從事工作214天指派機器B從事工作35天指派機器C從事工作17天總工作天數26天2.98第98页第98页指派問題特例不平衡問題：在虛擬列或行其指派成本設為0多重最適解(指派較有彈性)严禁指派：用大M法將严禁指派消去最大化問題：應用匈牙利法利用機會成本最小化求解利潤最大化指派問題(如圖6.21)99第99页第99页機器設備工作1工作2工作3利潤表(最大化)A211519B231217C251419機器設備工作1工作2工作3計算機會成本A25-2125-1525-19B25-2325-1225-17C25-2525-1425-19機器設備工作1工作2工作3最小化機會成本A4106B2138C0116100第100页第100页第七章整數線性規劃與目標規劃簡介整數線性規劃類型0-1整數規劃問題之公式化整數之放鬆線性規劃與化整求解技巧－分枝法應用分枝法求解賽浦路斯俱樂部問題目標規劃將目標規劃問題公式化加權目標規劃有優先性之目標規劃101第101页第101页資本預算問題-決定投資計畫投資計畫淨現值第一年第二年125,0008,0007,000218,0006,0004,000332,00012,0008,000可用資金預算20,00016,000決策變數之定義：X1=1投資計畫1=0否X2=1投資計畫2=0否X3=1投資計畫3=0否102第102页第102页MAX

25000X1+18000X2+3X3Subjectto8000X1+6000X2+1X3<=0

7000X1+4000X2+8000X3<=16000

X1+X2+X3<=2(orX1+X2+X3=2)X1,X2,X3is0-1IntegerVariable

X1:是否投資計畫1X2:是否投資計畫2X3:是否投資計畫3103第103页第103页固定費用問題-決定何處建廠三個地點建築成本地點固定成本變動成本產能1340,0001211,0002270,0001310,0003290,000109,000某一公司決定至少新建一座工廠，当前有三個地點可供考慮，一旦工廠建好後，公司希望能有足夠產能，每年至少達18000單位，各地點之相關成本下列表所列，求如何規劃地點建廠及產量，以達最小成本？104第104页第104页決策變數之定義：X1=1在地點一建廠=0否X2=1在地點二建廠=0否X3=1在地點三建廠=0否P1=地點一工廠產量P2=地點二工廠產量P3=地點三工廠產量105第105页第105页MIN

340000X1+270000X2+290000X3+12P1+13P2+10PX3SubjecttoP1+P2+P3>=18000

P1<=11000X1P2<=10000X2P3<=9000X3

X1,X2,X3is0-1IntegerVariablesP1,P2,P3isIntegerVariables106第106页第106页賽浦路斯俱樂部行銷例子(p285)MAX

8200X1+5100X2SubjecttoX1>=2

X2<=6

390X1+240X2<=1800(廣告預算)X1,X2>=0

X1:每星期主要時段廣告次數X2:每星期非主時段廣告次數結果：X1=2,X2=4.25,目標函數值為38075人107第107页第107页分枝法步驟1：求解放鬆線性規劃問題，訂出上界＝線性規劃