利用二位元整数规划处理是否决策

©TheMcGraw-HillCompanies,Inc.,2009第7章利用二位元整數規劃處理「是/否」決策學習目標7.2個案研究：加州製造公司問題（7.1節）7.2–7.11利用BIP做專案選擇：Tazer公司問題（7.2節）7.12–7.15利用BIP選擇緊急服務設施的地點：卡林市的問題（7.3節）7.16–7.19利用BIP於機組人員排班：西南航空公司問題（7.4節）7.20–7.24利用混合BIP處理開始生產的整備成本︰偉伯公司問題修正版（7.5節）7.25–7.30補充教材整數規劃導論（華盛頓大學上課教材）7.31–7.46整數規劃之應用（華盛頓大學上課教材）7.47–7.59©TheMcGraw-HillCompanies,Inc.,20097-2二位元變數之應用因為二位元變數（binaryvariable）只有0與1兩種可能的數值，所以自然用它們來表示「是/否」決策（yes-or-nodecisions）。範例：–我們應該執行某一特定專案嗎？–我們應該選擇某一特定投資方案嗎？–我們應該將設施選定在某一特定地點嗎？©TheMcGraw-HillCompanies,Inc.,20097-3加州製造公司的問題加州製造公司是一家多角化經營的公司，有許多的工廠與倉庫遍及整個加州，但是在洛杉磯或舊金山卻還沒有。基本的問題是要在洛杉磯或舊金山二地之中擇一建廠，或是在兩地都設廠。管理階層也考慮到最多蓋一個新倉庫，但是限制其只能蓋在新廠所在的城市。問題：加州製造公司應該在洛杉磯或舊金山擴建工廠和（或）倉庫？©TheMcGraw-HillCompanies,Inc.,20097-4加州製造公司相關資料©TheMcGraw-HillCompanies,Inc.,20097-5二位元決策變數©TheMcGraw-HillCompanies,Inc.,20097-6代數式令x1=1若在洛杉磯蓋工廠；否則為0x2=1若在舊金山蓋工廠；否則為0x3=1若在洛杉磯蓋倉庫；否則為0x4=1若在舊金山蓋倉庫；否則為0最大化NPV=8x1+5x2+6x3+4x4（百萬美元）受限於總資本支出：6x1+3x2+5x3+2x4≤10（百萬美元）最多1個倉庫：x3+x4≤1有設工廠才可能蓋倉庫：x3≤x1x4≤x2且x1,x2,x3,x4為二位元變數©TheMcGraw-HillCompanies,Inc.,20097-7試算表模式©TheMcGraw-HillCompanies,Inc.,20097-8利用規劃求解表進行敏感度分析©TheMcGraw-HillCompanies,Inc.,20097-9管理階層的結論管理階層暫時所考慮的投資金額為1,000萬美元。在此資本下，最佳計畫是在洛杉磯和舊金山都設立工廠，但都不設倉庫。這個計畫有一個優點，就是總共只使用了900萬美元，剩下的100萬美元可用於其他的投資方案。如果可用資本降到900萬美元以下，就會產生嚴重的損失（總淨現值從1,300萬美元減至900萬美元）。如果將資本增加100萬美元（從1,000萬美元變成1,100萬美元），就會增加400萬美元的總淨現值（從1,300萬美元到1,700萬美元）。管理階層最後決定要這樣做。若有如此多的資本可茲運用，則最佳計畫是在洛杉磯與舊金山都設立工廠，並且在舊金山設立倉庫（所產生的總淨現值估計為1,700萬美元）。©TheMcGraw-HillCompanies,Inc.,20097-10一些其他應用投資分析–我們是否應該做某一特定投資？–範例：TurkishPetroleumRefineries(1990),SouthAfricanNationalDefenseForce(1997),Grantham,Mayo,VanOtterlooandCompany(1999)廠址選擇–是否應該選擇某一特定地點作為設廠的位置？–範例：AT&T(1990)設計生產與配銷網路–是否某一特定工廠應該繼續運作？是否應該選擇某一特定地點作為設立新廠的位置？是否某一特定配銷中心應該繼續運作？是否某一特定配銷中心應該被指派來服務某一特定市場區域？–範例：AultFoods(1994),DigitalEquipmentCorporation(1995)©TheMcGraw-HillCompanies,Inc.,20097-11一些其他應用（續）運送指派–是否某一特定路線被選定為某一輛卡車的運行路徑？是否使用某一特定大小的車輛？是否選定某一特定期間作為出車時間？–範例：QualityStores(1987),AirProductsandChemicals,Inc.(1983),ReynoldsMetalsCo.(1991),Sears,RoebuckandCompany(1999)排定相關活動時程–是否某一特定活動在某一期間展開？–範例：TexasStadium(1983),China(1995)排定資產出售時程–是否某一特定資產在某一期間出售？–範例：HomartDevelopment(1987)航空公司應用–是否某一特定類型飛機被指派作為某一特定航班之用？是否指派某一特定航線給某位機師？–範例：AmericanAirlines(1989,1991),AirNewZealand(2001)©TheMcGraw-HillCompanies,Inc.,20097-12專案選擇：Tazer公司問題Tazer為一家製藥公司，目前想要研發一種突破性新藥物。有五個具潛力的R&D專案：–提升專案：研發出更有效的抗憂鬱藥劑，且不會導致病患嚴重的情緒起伏。–穩定專案：研發出抗躁鬱症的藥物。–選擇專案：研發出較少侵入性的女性避孕方法。–希望專案：研發出預防HIV感染的疫苗。–釋出專案：研發出更有效的降血壓藥物。公司可用資金只有12億美元（只夠執行二到三個專案）。問題：應該選擇哪些研發專案？©TheMcGraw-HillCompanies,Inc.,20097-13Tazer公司專案選擇問題的相關資料©TheMcGraw-HillCompanies,Inc.,20097-14Tazer公司專案選擇問題的代數式令xi=1若選擇專案i;0否則(i=1,2,3,4,5)最大化P=300x1+120x2+170x3+100x4+70x5（百萬美元）受限於研發預算：400x1+300x2+600x3+500x4+200x5≤1,200（百萬美元）且xi為二位元(i=1,2,3,4,5)©TheMcGraw-HillCompanies,Inc.,20097-15Tazer公司專案選擇問題的試算表模式©TheMcGraw-HillCompanies,Inc.,20097-16緊急服務設施地點的選擇：卡林市的問題卡林市人口成長快速，居住範圍擴展到原有城市邊界以外。這座城市只有一個消防站，位在擁擠的市中心。結果是當火災發生無法快速抵達城市外圍的地區。目標：提出一個在城市多處設立消防站的計畫。新政策：回應時間≤10分鐘©TheMcGraw-HillCompanies,Inc.,20097-17卡林市問題的回應時間和成本相關資料©TheMcGraw-HillCompanies,Inc.,20097-18卡林市問題的代數式令xj=1若在區域j設立消防站；否則為0(j=1,2,…,8)最小化C=350x1+250x2+450x3+300x4+50x5+400x6+300x7+200x8受限於區域1:x1+x2+x4≥1區域2:x1+x2+x3≥1區域3:x2+x3+x6≥1區域4:x1+x4+x7≥1區域5:x5+x7≥1區域6:x3+x6+x8≥1區域7:x4+x7+x8≥1區域8:x6+x7+x8≥1且xj為二位元(j=1,2,…,8)©TheMcGraw-HillCompanies,Inc.,20097-19卡林市問題的試算表模式©TheMcGraw-HillCompanies,Inc.,20097-20機組人員排班：西南航空公司問題西南航空對於所有排定的航班，需要指派它的機組人員去執行飛航勤務。我們將焦點擺在：指派三位居住於舊金山（SanFrancisco，簡稱SFO）的機組人員來執行11個航班的勤務。問題：應該如何將這三位機組人員指派到三條航線，使得11個航班都有人負責勤務？©TheMcGraw-HillCompanies,Inc.,20097-21西南航空的航班©TheMcGraw-HillCompanies,Inc.,20097-22西南航空問題的相關資料©TheMcGraw-HillCompanies,Inc.,20097-23西南航空問題的代數式令xj=1若接續航線j被指派給某位組員；否則為0(j=1,2,…,12)最小化成本=2x1+3x2+4x3+6x4+7x5+5x6+7x7+8x8+9x9+9x10+8x11+9x12(千美元)受限於航班1：x1+x4+x7+x10≥1航班2：x2+x5+x8+x11≥1::航班11：x6+x9+x10+x11+x12≥1三位組員：x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12≤3且xj為二位元(j=1,2,…,12)©TheMcGraw-HillCompanies,Inc.,20097-24西南航空問題的試算表模式©TheMcGraw-HillCompanies,Inc.,20097-25偉伯公司問題︰考慮整備成本假設偉伯公司問題有兩項改變：1.開始某一產品的生產時需要調整（或設定）生產設施，所以會有所謂的整備成本（setupcost）。2.對於每一種產品，每月只有排定一週來生產。所以原始模式中的D和W現在分別代表門和窗戶的生產量，而不再是生產率。因此，這二個變數必須限制為整數。©TheMcGraw-HillCompanies,Inc.,20097-26原始偉伯問題的圖形解©TheMcGraw-HillCompanies,Inc.,20097-27考慮整備成本偉伯問題的淨利潤©TheMcGraw-HillCompanies,Inc.,20097-28考慮整備成本偉伯問題的可行解©TheMcGraw-HillCompanies,Inc.,20097-29考慮整備成本偉伯問題的代數式令D=門生產量W=窗戶生產量y1=1若整備來生產門；否則為0y2=1若整備來生產窗戶；否則為0最大化P=300D+500W–700y1–1,300y2受限於原始限制式：工廠1：D≤4工廠2：2W≤12工廠3：3D+2W≤18只有整備才能生產：門：D≤99y1窗戶：W≤99y2且D≥0,W≥0,y1與y2為二位元©TheMcGraw-HillCompanies,Inc.,20097-30考慮整備成本偉伯問題的試算表模式©TheMcGraw-HillCompanies,Inc.,20097-31整數規劃何種情況下允許「非整數」解？–解本身是可以切割的•例如：金錢、磅、小時–解代表速率•例如：每週產量–解只是作為規劃的目的何種情況下允許將解取為整數？–當數值相當大時•例如：將114.286取為114或許並無問題何種情況下不允許將解取為整數？–當數值相當小時•例如：將2.6取為2或3可能會有問題–二位元變數•「是╱否」決策©TheMcGraw-HillCompanies,Inc.,20097-32「取為整數」可能形成的問題取為整數後的解可能不再是可行解。取為整數後的解可能已經偏離最佳解相當遠。可能會有許多取為整數後的整數解。–範例：考慮一個具有30個非整數值的LP變數解。若將這些變數值取為整數後，會有多少組可能的整數解？1234512345x1x2©TheMcGraw-HillCompanies,Inc.,20097-33整數問題如何求解？1234512345x1x2©TheMcGraw-HillCompanies,Inc.,20097-34整數問題如何求解（續）123451234