《利用二位元整数规划处理是否决策.ppt》由会员分享，可在线阅读，更多相关《利用二位元整数规划处理是否决策.ppt（59页珍藏版）》请在三一文库上搜索。
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.59,7-2,二位元變數之應用,因為二位元變數（binary var
2、iable）只有 0 與 1兩種可能的數值，所以自然用它們來表示是/否決策（yes-or-no decisions）。 範例：我們應該執行某一特定專案嗎？我們應該選擇某一特定投資方案嗎？我們應該將設施選定在某一特定地點嗎？,7-3,加州製造公司的問題,加州製造公司是一家多角化經營的公司，有許多的工廠與倉庫遍及整個加州，但是在洛杉磯或舊金山卻還沒有。基本的問題是要在洛杉磯或舊金山二地之中擇一建廠，或是在兩地都設廠。 管理階層也考慮到最多蓋一個新倉庫，但是限制其只能蓋在新廠所在的城市。 問題：加州製造公司應該在洛杉磯或舊金山擴建工廠和（或）倉庫？,7-4,加州製造公司相關資料,7-5,二位元決策變
3、數,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 萬美元。
4、在此資本下，最佳計畫是在洛杉磯和舊金山都設立工廠，但都不設倉庫。 這個計畫有一個優點，就是總共只使用了 900 萬美元，剩下的 100 萬美元可用於其他的投資方案。如果可用資本降到 900 萬美元以下，就會產生嚴重的損失（總淨現值從 1,300 萬美元減至 900 萬美元）。 如果將資本增加 100 萬美元（從 1,000 萬美元變成 1,100 萬美元），就會增加 400 萬美元的總淨現值（從 1,300 萬美元到 1,700 萬美元）。管理階層最後決定要這樣做。若有如此多的資本可茲運用，則最佳計畫是在洛杉磯與舊金山都設立工廠，並且在舊金山設立倉庫（所產生的總淨現值估計為 1,700 萬美元
5、）。,7-10,一些其他應用,投資分析我們是否應該做某一特定投資？範例：Turkish Petroleum Refineries (1990), South African National Defense Force (1997), Grantham, Mayo, Van Otterloo and Company (1999)廠址選擇是否應該選擇某一特定地點作為設廠的位置？範例：AT&T (1990)設計生產與配銷網路是否某一特定工廠應該繼續運作？是否應該選擇某一特定地點作為設立新廠的位置？是否某一特定配銷中心應該繼續運作？是否某一特定配銷中心應該被指派來服務某一特定市場區域？範例：Ault
6、 Foods (1994), Digital Equipment Corporation (1995),7-11,一些其他應用（續）,運送指派是否某一特定路線被選定為某一輛卡車的運行路徑？是否使用某一特定大小的車輛？是否選定某一特定期間作為出車時間？範例：Quality Stores (1987), Air Products and Chemicals, Inc. (1983), Reynolds Metals Co. (1991), Sears, Roebuck and Company (1999)排定相關活動時程是否某一特定活動在某一期間展開？範例：Texas Stadium (1983)
7、, China (1995)排定資產出售時程是否某一特定資產在某一期間出售？範例：Homart Development (1987)航空公司應用是否某一特定類型飛機被指派作為某一特定航班之用？是否指派某一特定航線給某位機師？範例：American Airlines (1989, 1991), Air New Zealand (2001),7-12,專案選擇：Tazer 公司問題,Tazer 為一家製藥公司，目前想要研發一種突破性新藥物。 有五個具潛力的 R&D 專案：提升專案：研發出更有效的抗憂鬱藥劑，且不會導致病患嚴重的情緒起伏。穩定專案：研發出抗躁鬱症的藥物。選擇專案：研發出較少侵入性的女
8、性避孕方法。希望專案：研發出預防 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 （百萬美元
9、）且 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
10、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,機組人員排班：西南航空公司問題,西南航空對於所有排定的航班，需要指派它的機組人員去執行飛航勤務
11、。我們將焦點擺在：指派三位居住於舊金山（San Francisco，簡稱 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 +
12、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. 開始某一產品的生產時需要調整（或設定）生產設施， 所以會有所謂的整備成本（setup cost）。2. 對於每一種產品，每月只有排定一週來生產。所以原始模式中的 D 和
13、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 為二
14、位元,7-30,考慮整備成本偉伯問題的試算表模式,7-31,整數規劃,何種情況下允許非整數解？解本身是可以切割的例如：金錢、磅、小時解代表速率例如：每週產量解只是作為規劃的目的何種情況下允許將解取為整數？當數值相當大時例如：將 114.286 取為 114 或許並無問題何種情況下不允許將解取為整數？當數值相當小時例如：將 2.6 取為 2 或 3 可能會有問題二位元變數是否決策,7-32,取為整數可能形成的問題,取為整數後的解可能不再是可行解。取為整數後的解可能已經偏離最佳解相當遠。可能會有許多取為整數後的整數解。範例：考慮一個具有30 個非整數值的 LP 變數解。若將這些變數值取為整數後，會
15、有多少組可能的整數解？,7-33,整數問題如何求解？,7-34,整數問題如何求解（續）,7-35,二位元變數的應用,做是/否類型的決策建造一座工廠？製造一項產品？執行一個專案？指派一個人來做一件工作？集合涵蓋問題指定一組指派使其可以涵蓋一組需求固定成本若啟動某項產品的生產，會伴隨一項固定的整備成本 若一個倉庫運作的話，會有固定的營運費用,7-36,範例 # 1（資本預算）,Norwood 開發公司正考慮四項具潛力的開發專案。每一項專案最多在三年內可以完成。每一項專案所需現金流量、淨現值、以及每年可用現金如下表所示。,問題：應該選擇哪些專案？,7-37,Norwood 開發公司資本預算的代數式,
16、令 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 其中一個。除非執
17、行專案 3，否則不能執行專案 2。專案 3 和專案 4 只能二擇一，不能二者都選。總共專案執行件數不超過二件。問題：若有上述這些額外考量，需要加入哪些限制式？,7-40,範例 # 2（集合涵蓋問題）,華盛頓州議會正想要決定要在哪些地點設立搜救隊。成立搜救隊需要許多經費，所以他們希望所成立的隊伍數愈少愈好。回應時間相當關鍵，所以他們希望每一個郡要有一支搜救隊或是在鄰近的郡要有搜救隊。問題：要在哪些地點設立搜救隊？,7-41,華盛頓州的郡,7-42,代數式,令 yi = 1 若在郡 i 設有搜救隊; 0 否則 (i = 1, 2, , 37)最小化 搜救隊數 = y1 + y2 + + y37受限
18、於郡 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 週。各種產品所需人
19、工和白鑞如下表所示。銷售價格以及變動成本亦列在表中。,問題：應該生產哪些製品，以及多少數量？,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 ，
20、 yi 為二位元 (i = 1, 2, 3),7-46,試算表解,7-47,二位元變數之應用,作是否類型之決策建造一座工廠？製造一項產品？執行一個專案？指派某個人執行某件工作？固定成本若生產某項產品，則伴隨有固定整備成本。若一座倉庫運作，則伴隨有固定成本。二擇一限制式 (Either-or constraints)生產量必須 = 0 或 100部分限制式 (Subset of constraints)4 條限制式中必須滿足其中的 3 條,7-48,具有附帶限制式之資本預算（是否決策）,某一家公司正在為未來幾年規劃資本預算。他們目前正考慮 10 個具有潛力的專案。他們已經計算出各項專案的期望淨現
21、值，以及未來五年所需的現金流量。此外，假設有以下的附帶限制式（contingency constraints）：至少必須執行專案1、2、3其中的一個。專案 4 和 專案 5 不能二個都執行。除非專案 6 有執行，否則專案 7 不得執行。問題：他們應該執行哪些專案？,7-49,資本預算問題之相關資料,7-50,試算表解,7-51,發電機啟動規劃（固定成本）,某座發電廠擁有五部發電機。若要發電，發電機必須啟動（start up），這將伴隨有固定的啟動成本（startup cost）。所有發電機在每天結束時會關機。,問題：該啟動哪幾部發電機以滿足每天 6,000 百萬瓦的總需求量？,7-52,試算表
22、解,7-53,品質家具（二擇一限制式）,考慮品質家具問題：品質家具公司生產長凳和野餐桌。公司可用以生產的資源（人力和木材）相當有限， 在下一個生產期間有1,600 人工小時可以運用。公司目前有 9,000 磅的木材可以使用。每張長凳需要 3 人工小時以及 12 磅的木材。每張桌子需要 6 人工小時以及 38 磅的木材。每張長凳和桌子的利潤分別為 $8 與 $18。假設每種產品他們不會生產少於 200 張（亦即，生產 0 或 至少 200 張）。問題：產品組合為何會使得他們的總利潤最大？,7-54,試算表解,7-55,滿足部分限制式,考慮具有下列限制式之某一線性規劃模式，並且假設只要滿足這 4
23、條限制式其中 3 條即可。12x1 + 24x2 + 18x3 2,40015x1 + 32x2 + 12x3 1,80020 x1 + 15x2 + 20 x3 2,00018x1 + 21x2 + 15x3 1,600,7-56,滿足部分限制式（續）,令 yi = 1 若滿足限制式 i ; 0 否則限制式：y1 + y2 + y3 + y4 312x1 + 24x2 + 18x3 2,400y115x1 + 32x2 + 12x3 1,800y220 x1 + 15x2 + 20 x3 2,000 + M (1 y3)18x1 + 21x2 + 15x3 1,600 + M (1 y4)其中 M 為一個大的正數,7-57,設施位置,考慮某一家公司，它有 5 座工廠和 3 個倉庫，供應 4 個不同區域的顧客。為了降低成本，他們正考慮透過關閉一座或多座工廠和倉庫的方式，來精簡產銷流程。每座工廠有相關的固定成本、運送成本、與生產成本。每座工廠具有有限的產能。每座倉庫有相關的固定成本和運送成本。每座倉庫具有有限的儲放空間。問題：哪幾座工廠應該繼續營運？哪幾座倉庫應該繼續營運？營運工廠間生產量應該如何分配？應該從每座工廠運送至每座倉庫，以及從每座倉庫運送到每位顧客多少數量？,7-58,設施位置問題相關資料,7-59,試算表解,