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

1、第 7 章利用二位元整數規劃處理是/否決策學習目標7.2個案研讨：加州製造公司問題7.1節7.27.11 利用 BIP 做專案選擇：Tazer公司問題7.2節7.127.15利用 BIP 選擇緊急服務設施的地點：卡林市的問題7.3節7.167.19利用 BIP 於機組人員排班：西南航空公司問題7.4節7.207.24 利用混合 BIP 處理開始生產的整備本钱偉伯公司問題修正版 7.5節7.257.30補充教材整數規劃導論華盛頓大學上課教材7.317.46整數規劃之應用華盛頓大學上課教材7.477.597-1二位元變數之應用因為二位元變數binary variable只需 0 與 1兩種能够的數

2、值，所以自然用它們來表示是/否決策yes-or-no decisions。 範例：我們應該執行某一特定專案嗎？我們應該選擇某一特定投資方案嗎？我們應該將設施選定在某一特定地點嗎？2加州製造公司的問題 加州製造公司是一家多角化經營的公司，有許多的工廠與倉庫普及整個加州，但是在洛杉磯或舊金山卻還沒有。根本的問題是要在洛杉磯或舊金山二地之中擇一建廠，或是在兩地都設廠。 管理階層也考慮到最多蓋一個新倉庫，但是限制其只能蓋在新廠所在的城市。 問題：加州製造公司應該在洛杉磯或舊金山擴建工廠和或倉庫？3加州製造公司相關資料4二位元決策變數5代數式令x1 = 1 假设在洛杉磯蓋工廠；否則為0 x2 = 1 假

3、设在舊金山蓋工廠；否則為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 為二位元變數6試算表方式7利用規劃求解表進行敏感度分析8管理階層的結論 管理階層暫時所考慮的投資金額為 1,000 萬美圆。在此資本下，最正确計畫是在洛杉磯和舊金山都設立工廠，但都不設倉庫。 這個計畫有一個優點，就是總共只运用了

4、900 萬美圆，剩下的 100 萬美圆可用於其他的投資方案。假设可用資本降到 900 萬美圆以下，就會產生嚴重的損失總淨現值從 1,300 萬美圆減至 900 萬美圆。 假设將資本添加 100 萬美圆從 1,000 萬美圆變成 1,100 萬美圆，就會添加 400 萬美圆的總淨現值從 1,300 萬美圆到 1,700 萬美圆。管理階層最後決定要這樣做。假设有如此多的資本可茲運用，則最正确計畫是在洛杉磯與舊金山都設立工廠，並且在舊金山設立倉庫所產生的總淨現值估計為 1,700 萬美圆。 9一些其他應用投資分析我們能否應該做某一特定投資？範例：Turkish Petroleum Refinerie

5、s (1990), South African National Defense Force (1997), Grantham, Mayo, Van Otterloo and Company (1999)廠址選擇能否應該選擇某一特定地點作為設廠的位置？範例：AT&T (1990)設計生產與配銷網路能否某一特定工廠應該繼續運作？能否應該選擇某一特定地點作為設立新廠的位置？能否某一特定配銷中心應該繼續運作？能否某一特定配銷中心應該被指派來服務某一特定市場區域？範例：Ault Foods (1994), Digital Equipment Corporation (1995)10一些其他應用續運送指

6、派能否某一特定路線被選定為某一輛卡車的運行路徑？能否运用某一特定大小的車輛？能否選定某一特定期間作為出車時間？範例：Quality Stores (1987), Air Products and Chemicals, Inc. (1983), Reynolds Metals Co. (1991), Sears, Roebuck and Company (1999)排定相關活動時程能否某一特定活動在某一期間展開？範例：Texas Stadium (1983), China (1995)排定資產出卖時程能否某一特定資產在某一期間出卖？範例：Homart Development (1987)航空公司

7、應用能否某一特定類型飛機被指派作為某一特定航班之用？能否指派某一特定航線給某位機師？範例：American Airlines (1989, 1991), Air New Zealand (2001)11專案選擇：Tazer 公司問題 Tazer 為一家製藥公司，目前想要研發一種突破性新藥物。 有五個具潛力的 R&D 專案：提升專案：研發出更有效的抗憂鬱藥劑，且不會導致病患嚴重的情緒起伏。穩定專案：研發出抗躁鬱症的藥物。選擇專案：研發出較少侵入性的女性避孕方法。希望專案：研發出預防 HIV 感染的疫苗。釋出專案：研發出更有效的降血壓藥物。 公司可用資金只需12 億美圆只夠執行二到三個專案。問題：

8、應該選擇哪些研發專案？12Tazer 公司專案選擇問題的相關資料 13Tazer 公司專案選擇問題的代數式令 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) 14Tazer 公司專案選擇問題的試算表方式15緊急服務設施地點的選擇：卡林市的問題卡林市人口成長快速，居住範

9、圍擴展到原有城市邊界以外。這座城市只需一個消防站，位在擁擠的市中心。結果是當火災發生無法快速抵達城市外圍的地區。 目標：提出一個在城市多處設立消防站的計畫。新政策： 回應時間 10 分鐘16卡林市問題的回應時間和本钱相關資料17卡林市問題的代數式令 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

10、+ 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) 18卡林市問題的試算表方式19機組人員排班：西南航空公司問題西南航空對於一切排定的航班，需求指派它的機組人員去執行飛航勤務。我們將焦點擺在：指派三位居住於舊金山San Francisco，簡稱 SFO的機組人員來執行 11 個航班的勤務。 問題： 應該如何將這三位機組人員指派到三條航線，使得 11 個航班都有人負責勤務？20西南航空的航班21

11、西南航空問題的相關資料22西南航空問題的代數式令 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 +

12、x11 + x12 3且xj 為二位元 (j = 1, 2, , 12)23西南航空問題的試算表方式24偉伯公司問題考慮整備本钱假設偉伯公司問題有兩項改變：1. 開始某一產品的生產時需求調整或設定生產設施， 所以會有所謂的整備本钱setup cost。2. 對於每一種產品，每月只需排定一週來生產。所以原始方式中的 D 和 W 現在分別代表門和窗戶的生產量，而不再是生產率。因此，這二個變數必須限制為整數。 25原始偉伯問題的圖形解26考慮整備本钱偉伯問題的淨利潤27考慮整備本钱偉伯問題的可行解28考慮整備本钱偉伯問題的代數式令D = 門生產量W = 窗戶生產量y1 = 1 假设整備來生產門；否則

13、為 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 為二位元29考慮整備本钱偉伯問題的試算表方式30整數規劃何種情況下允許非整數解？解本身是可以切割的例如：金錢、磅、小時解代表速率例如：每週產量解只是作為規劃的目的何種情況下允許將解取為整數？當數值相當大時例如：將 114.286 取為 114 或許並無問題何種情況下不允許將解取為整數？當數值相當小時例如：將

14、 2.6 取為 2 或 3 能够會有問題二位元變數是否決策31取為整數能够构成的問題取為整數後的解能够不再是可行解。取為整數後的解能够已經偏離最正确解相當遠。能够會有許多取為整數後的整數解。範例：考慮一個具有30 個非整數值的 LP 變數解。假设將這些變數值取為整數後，會有多少組能够的整數解？32整數問題如何求解？33整數問題如何求解續34二位元變數的應用做是/否類型的決策建造一座工廠？製造一項產品？執行一個專案？指派一個人來做一件任务？集合涵蓋問題指定一組指派使其可以涵蓋一組需求固定本钱假设啟動某項產品的生產，會伴隨一項固定的整備本钱 假设一個倉庫運作的話，會有固定的營運費用35範例 # 1

15、資本預算Norwood 開發公司正考慮四項具潛力的開發專案。每一項專案最多在三年內可以完成。每一項專案所需現金流量、淨現值、以及每年可用現金如下表所示。所需現金流量 (百萬美元)可用現金(百萬美元)專案 1專案 2專案 3專案 4第 1 年9761128第 2 年643013第 3 年604010淨現值30162214問題：應該選擇哪些專案？36Norwood 開發公司資本預算的代數式令 yi = 1 假设選擇專案 i ； 否則為0 (i = 1, 2, 3, 4)最大化 淨現值 = 30y1 + 16y2 + 22y3 + 14y4受限於第 1 年：9y1 + 7y2 + 6y3 + 11y

16、4 28 (百萬美圆)第 2 年：累計15y1 + 11y2 + 9y3 + 11y4 41 (百萬美圆)第 3 年：累計21y1 + 11y2 + 13y3 + 11y4 51 (百萬美圆)且yi 為二位元 (i = 1, 2, 3, 4)37Norwood 開發公司資本預算的試算表解38其他的考量邏輯和相依限制式至少選擇專案 1、2、3 其中一個。除非執行專案 3，否則不能執行專案 2。專案 3 和專案 4 只能二擇一，不能二者都選。總共專案執行件數不超過二件。問題：假设有上述這些額外考量，需求参与哪些限制式？39範例 # 2集合涵蓋問題華盛頓州議會正想要決定要在哪些地點設立搜救隊。成立搜

17、救隊需求許多經費，所以他們希望所成立的隊伍數愈少愈好。回應時間相當關鍵，所以他們希望每一個郡要有一支搜救隊或是在鄰近的郡要有搜救隊。問題：要在哪些地點設立搜救隊？40華盛頓州的郡41代數式令 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

18、)42試算表解43範例 # 3固定本钱Woodridge白鑞錫與鉛、黃銅等的合金製器公司生產三種白鑞製品： 淺盤、碗、以及水罐。每一項產品的製造需求有可運用的機器和模具。製造每一種產品的機器和模具可以租用，租金如下: 製造淺盤為 $400週，製造碗為 $250 週，製造水罐為 $300 週。各種產品所需人工和白鑞如下表所示。銷售價格以及變動本钱亦列在表中。人工(小時)白鑞(磅)銷售價格變動成本淺盤35$100$60碗148550水罐437540可用數量130240問題：應該生產哪些製品，以及多少數量？44代數式令 x1 = 生產淺盤的數量x2 = 生產碗的數量x3 = 生產水罐的數量 yi =

19、 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)45試算表解46二位元變數之應用作是否類型之決策建造一座工廠？製造一項產品？執行一個專案？指派某個人執行某件任务？固定本钱假设生產某項產品，則伴隨有固

20、定整備本钱。假设一座倉庫運作，則伴隨有固定本钱。二擇一限制式 (Either-or constraints)生產量必須 = 0 或 100部分限制式 (Subset of constraints)4 條限制式中必須滿足其中的 3 條47具有附帶限制式之資本預算是否決策某一家公司正在為未來幾年規劃資本預算。他們目前正考慮 10 個具有潛力的專案。他們已經計算出各項專案的期望淨現值，以及未來五年所需的現金流量。此外，假設有以下的附帶限制式contingency constraints：至少必須執行專案1、2、3其中的一個。專案 4 和 專案 5 不能二個都執行。除非專案 6 有執行，否則專案 7

21、不得執行。問題：他們應該執行哪些專案？48資本預算問題之相關資料所需現金流量 (百萬美元)可用現金(百萬美元)專案12345678910第 1 年140443282625第 2 年222224233625第 3 年325242348225第 4 年445453121125第 5 年110655511225淨現值20252230422518352833(百萬美元)49試算表解50發電機啟動規劃固定本钱某座發電廠擁有五部發電機。假设要發電，發電機必須啟動start up，這將伴隨有固定的啟動本钱startup cost。一切發電機在每天結束時會關機。發電機ABCDE固定啟動成本$2,450$1,6

22、00$1,000$1,250$2,200變動成本 (每百萬瓦)$3$4$6$5$4產能 (百萬瓦)2,0002,8004,3002,1002,000問題：該啟動哪幾部發電機以滿足每天 6,000 百萬瓦的總需求量？51試算表解52品質家具二擇一限制式考慮品質家具問題：品質家具公司生產長凳和野餐桌。公司可用以生產的資源人力和木材相當有限， 在下一個生產期間有1,600 人工小時可以運用。公司目前有 9,000 磅的木材可以运用。每張長凳需求 3 人工小時以及 12 磅的木材。每張桌子需求 6 人工小時以及 38 磅的木材。每張長凳和桌子的利潤分別為 $8 與 $18。假設每種產品他們不會生產少於 200 張亦即，生產 0 或 至少 200 張。問題：產品組合為何會使得他們的總利潤最大？53試算表解54滿足部分限制式考慮具有以下限制式之某一線性規劃方式，並且假設只需滿足這 4 條限制式其中 3 條即可。12x1 + 24x2 + 18x3 2,40015x1 + 32x2 + 12x3 1,80020 x1 + 15x2 + 20 x3 2,00018x1