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

第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 7 2 二位元變數之應用 因為二位元變數 binaryvariable 只有0與1兩種可能的數值 所以自然用它們來表示 是 否 決策 yes or nodecisions 範例 我們應該執行某一特定專案嗎 我們應該選擇某一特定投資方案嗎 我們應該將設施選定在某一特定地點嗎 7 3 加州製造公司的問題 加州製造公司是一家多角化經營的公司 有許多的工廠與倉庫遍及整個加州 但是在洛杉磯或舊金山卻還沒有 基本的問題是要在洛杉磯或舊金山二地之中擇一建廠 或是在兩地都設廠 管理階層也考慮到最多蓋一個新倉庫 但是限制其只能蓋在新廠所在的城市 問題 加州製造公司應該在洛杉磯或舊金山擴建工廠和 或 倉庫 7 4 加州製造公司相關資料 7 5 二位元決策變數 7 6 代數式 令x1 1若在洛杉磯蓋工廠 否則為0 x2 1若在舊金山蓋工廠 否則為0 x3 1若在洛杉磯蓋倉庫 否則為0 x4 1若在舊金山蓋倉庫 否則為0最大化NPV 8x1 5x2 6x3 4x4 百萬美元 受限於總資本支出 6x1 3x2 5x3 2x4 10 百萬美元 最多1個倉庫 x3 x4 1有設工廠才可能蓋倉庫 x3 x1x4 x2且x1 x2 x3 x4為二位元變數 7 7 試算表模式 7 8 利用規劃求解表進行敏感度分析 7 9 管理階層的結論 管理階層暫時所考慮的投資金額為1 000萬美元 在此資本下 最佳計畫是在洛杉磯和舊金山都設立工廠 但都不設倉庫 這個計畫有一個優點 就是總共只使用了900萬美元 剩下的100萬美元可用於其他的投資方案 如果可用資本降到900萬美元以下 就會產生嚴重的損失 總淨現值從1 300萬美元減至900萬美元 如果將資本增加100萬美元 從1 000萬美元變成1 100萬美元 就會增加400萬美元的總淨現值 從1 300萬美元到1 700萬美元 管理階層最後決定要這樣做 若有如此多的資本可茲運用 則最佳計畫是在洛杉磯與舊金山都設立工廠 並且在舊金山設立倉庫 所產生的總淨現值估計為1 700萬美元 7 10 一些其他應用 投資分析我們是否應該做某一特定投資 範例 TurkishPetroleumRefineries 1990 SouthAfricanNationalDefenseForce 1997 Grantham Mayo VanOtterlooandCompany 1999 廠址選擇是否應該選擇某一特定地點作為設廠的位置 範例 AT T 1990 設計生產與配銷網路是否某一特定工廠應該繼續運作 是否應該選擇某一特定地點作為設立新廠的位置 是否某一特定配銷中心應該繼續運作 是否某一特定配銷中心應該被指派來服務某一特定市場區域 範例 AultFoods 1994 DigitalEquipmentCorporation 1995 7 11 一些其他應用 續 運送指派是否某一特定路線被選定為某一輛卡車的運行路徑 是否使用某一特定大小的車輛 是否選定某一特定期間作為出車時間 範例 QualityStores 1987 AirProductsandChemicals Inc 1983 ReynoldsMetalsCo 1991 Sears RoebuckandCompany 1999 排定相關活動時程是否某一特定活動在某一期間展開 範例 TexasStadium 1983 China 1995 排定資產出售時程是否某一特定資產在某一期間出售 範例 HomartDevelopment 1987 航空公司應用是否某一特定類型飛機被指派作為某一特定航班之用 是否指派某一特定航線給某位機師 範例 AmericanAirlines 1989 1991 AirNewZealand 2001 7 12 專案選擇 Tazer公司問題 Tazer為一家製藥公司 目前想要研發一種突破性新藥物 有五個具潛力的R D專案 提升專案 研發出更有效的抗憂鬱藥劑 且不會導致病患嚴重的情緒起伏 穩定專案 研發出抗躁鬱症的藥物 選擇專案 研發出較少侵入性的女性避孕方法 希望專案 研發出預防HIV感染的疫苗 釋出專案 研發出更有效的降血壓藥物 公司可用資金只有12億美元 只夠執行二到三個專案 問題 應該選擇哪些研發專案 7 13 Tazer公司專案選擇問題的相關資料 7 14 Tazer公司專案選擇問題的代數式 令xi 1若選擇專案i 0否則 i 1 2 3 4 5 最大化P 300 x1 120 x2 170 x3 100 x4 70 x5 百萬美元 受限於研發預算 400 x1 300 x2 600 x3 500 x4 200 x5 1 200 百萬美元 且xi為二位元 i 1 2 3 4 5 7 15 Tazer公司專案選擇問題的試算表模式 7 16 緊急服務設施地點的選擇 卡林市的問題 卡林市人口成長快速 居住範圍擴展到原有城市邊界以外 這座城市只有一個消防站 位在擁擠的市中心 結果是當火災發生無法快速抵達城市外圍的地區 目標 提出一個在城市多處設立消防站的計畫 新政策 回應時間 10分鐘 7 17 卡林市問題的回應時間和成本相關資料 7 18 卡林市問題的代數式 令xj 1若在區域j設立消防站 否則為0 j 1 2 8 最小化C 350 x1 250 x2 450 x3 300 x4 50 x5 400 x6 300 x7 200 x8受限於區域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 7 19 卡林市問題的試算表模式 7 20 機組人員排班 西南航空公司問題 西南航空對於所有排定的航班 需要指派它的機組人員去執行飛航勤務 我們將焦點擺在 指派三位居住於舊金山 SanFrancisco 簡稱SFO 的機組人員來執行11個航班的勤務 問題 應該如何將這三位機組人員指派到三條航線 使得11個航班都有人負責勤務 7 21 西南航空的航班 7 22 西南航空問題的相關資料 7 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 7 24 西南航空問題的試算表模式 7 25 偉伯公司問題 考慮整備成本 假設偉伯公司問題有兩項改變 1 開始某一產品的生產時需要調整 或設定 生產設施 所以會有所謂的整備成本 setupcost 2 對於每一種產品 每月只有排定一週來生產 所以原始模式中的D和W現在分別代表門和窗戶的生產量 而不再是生產率 因此 這二個變數必須限制為整數 7 26 原始偉伯問題的圖形解 7 27 考慮整備成本偉伯問題的淨利潤 7 28 考慮整備成本偉伯問題的可行解 7 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為二位元 7 30 考慮整備成本偉伯問題的試算表模式 7 31 整數規劃 何種情況下允許 非整數 解 解本身是可以切割的例如 金錢 磅 小時解代表速率例如 每週產量解只是作為規劃的目的何種情況下允許將解取為整數 當數值相當大時例如 將114 286取為114或許並無問題何種情況下不允許將解取為整數 當數值相當小時例如 將2 6取為2或3可能會有問題二位元變數 是 否 決策 7 32 取為整數 可能形成的問題 取為整數後的解可能不再是可行解 取為整數後的解可能已經偏離最佳解相當遠 可能會有許多取為整數後的整數解 範例 考慮一個具有30個非整數值的LP變數解 若將這些變數值取為整數後 會有多少組可能的整數解 7 33 整數問題如何求解 7 34 整數問題如何求解 續 7 35 二位元變數的應用 做 是 否 類型的決策建造一座工廠 製造一項產品 執行一個專案 指派一個人來做一件工作 集合涵蓋問題指定一組指派使其可以涵蓋一組需求固定成本若啟動某項產品的生產 會伴隨一項固定的整備成本若一個倉庫運作的話 會有固定的營運費用 7 36 範例 1 資本預算 Norwood開發公司正考慮四項具潛力的開發專案 每一項專案最多在三年內可以完成 每一項專案所需現金流量 淨現值 以及每年可用現金如下表所示 問題 應該選擇哪些專案 7 37 Norwood開發公司資本預算的代數式 令yi 1若選擇專案i 否則為0 i 1 2 3 4 最大化淨現值 30y1 16y2 22y3 14y4受限於第1年 9y1 7y2 6y3 11y4 28 百萬美元 第2年 累計 15y1 11y2 9y3 11y4 41 百萬美元 第3年 累計 21y1 11y2 13y3 11y4 51 百萬美元 且yi為二位元 i 1 2 3 4 7 38 Norwood開發公司資本預算的試算表解 7 39 其他的考量 邏輯和相依限制式 至少選擇專案1 2 3其中一個 除非執行專案3 否則不能執行專案2 專案3和專案4只能二擇一 不能二者都選 總共專案執行件數不超過二件 問題 若有上述這些額外考量 需要加入哪些限制式 7 40 範例 2 集合涵蓋問題 華盛頓州議會正想要決定要在哪些地點設立搜救隊 成立搜救隊需要許多經費 所以他們希望所成立的隊伍數愈少愈好 回應時間相當關鍵 所以他們希望每一個郡要有一支搜救隊或是在鄰近的郡要有搜救隊 問題 要在哪些地點設立搜救隊 7 41 華盛頓州的郡 7 42 代數式 令yi 1若在郡i設有搜救隊 0否則 i 1 2 37 最小化搜救隊數 y1 y2 y37受限於郡1 y1 y2 1郡2 y1 y2 y3 y6 y7 1郡3 y2 y3 y4 y7 y8 y14 1 郡37 y32 y36 y37 1且yi為二位元 i 1 2 37 7 43 試算表解 7 44 範例 3 固定成本 Woodridge白鑞 錫與鉛 黃銅等的合金 製器公司生產三種白鑞製品 淺盤 碗 以及水罐 每一項產品的製造需要有可運用的機器和模具 製造每一種產品的機器和模具可以租用 租金如下 製造淺盤為 400 週 製造碗為 250 週 製造水罐為 300 週 各種產品所需人工和白鑞如下表所示 銷售價格以及變動成本亦列在表中 問題 應該生產哪些製品 以及多少數量 7 45 代數式 令x1 生產淺盤的數量x2 生產碗的數量x3 生產水罐的數量yi 1若租用製造產品i的機器和模具 否則為0 i 1 2 3 最大化利潤 100 60 x1 85 50 x2 75 40 x3 400y1 250y2 300y3受限於人工 3x1 x2 4x3 130小時白鑞 5x1 4x2 3x3 240磅只有機器和模具有租用時才可以生產 x1 99y1x2 99y2x3 99y3且xi 0 yi為二位元 i 1 2 3 7 46 試算表解 7 47 二位元變數之應用 作 是 否 類型之決策建造一座工廠 製造一項產品 執行一個專案 指派某個人執行某件工作 固定成本若生產某項產品 則伴隨有固定整備成本 若一座倉庫運作 則伴隨有固定成本 二擇一限制式 Either orconstraints 生產量必須 0或 100部分限制式 Subsetofconstraints 4條限制式中必須滿足其中的3條 7 48 具有附帶限制式之資本預算 是 否決策 某一家公司正在為未來幾年規劃資本預算 他們目前正考慮10個具有潛力的專案 他們已經計算出各項專案的期望淨現值 以及未來五年所需的現金流量 此外 假設有以下的附帶限制式 contingencyconstraints 至少必須執行專案1 2 3其中的一個 專案4和專案5不能二個都執行 除非專案6有執行 否則專案7不得執行 問題 他們應該執行哪些專案 7 49 資本預算問題之相關資料 7 50 試算表解 7 51 發電機啟動規劃 固定成本 某座發電廠擁有五部發電機 若要發電 發電機必須啟動 startup 這將伴隨有固定的啟動成本 startupcost 所有發電機在每天結束時會關機 問題 該啟動哪幾部發電機以滿足每天6 000百萬瓦的總需求量 7 52 試算表解 7 53 品質家具 二擇一限制式 考慮品質家具問題 品質家具公司生產長凳和野餐桌 公司可用以生產的資源 人力和木材 相當有限 在下一個生產期間有1 600人工小時可以運用 公司目前有9 000磅的木材可以使用 每張長凳需要3人工小時以及12磅的木材 每張桌子需要6人工小時以