利用二位元整數(shù)規(guī)劃處理是否決策ppt課件

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

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

3、設(shè)在舊金山蓋工廠；否則為0 x3 = 1 假設(shè)在洛杉磯蓋倉庫；否則為0 x4 = 1 假設(shè)在舊金山蓋倉庫；否則為0 最大化 NPV = 8x1 + 5x2 + 6x3 + 4x4 百萬美圓受限於總資本支出：6x1 + 3x2 + 5x3 + 2x4 10 百萬美圓最多1個倉庫：x3 + x4 1有設(shè)工廠才能夠蓋倉庫：x3 x1x4 x2且x1, x2, x3, x4 為二位元變數(shù)6試算表方式7利用規(guī)劃求解表進(jìn)行敏感度分析8管理階層的結(jié)論 管理階層暫時所考慮的投資金額為 1,000 萬美圓。在此資本下，最正確計畫是在洛杉磯和舊金山都設(shè)立工廠，但都不設(shè)倉庫。 這個計畫有一個優(yōu)點，就是總共只運用了

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

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

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

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

8、應(yīng)該選擇哪些研發(fā)專案？12Tazer 公司專案選擇問題的相關(guān)資料 13Tazer 公司專案選擇問題的代數(shù)式令 xi = 1 假設(shè)選擇專案 i ; 0 否則 ( i = 1, 2, 3, 4, 5)最大化 P = 300 x1 + 120 x2 + 170 x3 + 100 x4 + 70 x5 百萬美圓受限於研發(fā)預(yù)算： 400 x1 + 300 x2 + 600 x3 + 500 x4 + 200 x5 1,200 百萬美圓且 xi 為二位元 ( i = 1, 2, 3, 4, 5) 14Tazer 公司專案選擇問題的試算表方式15緊急服務(wù)設(shè)施地點的選擇：卡林市的問題卡林市人口成長快速，居住範(fàn)

9、圍擴(kuò)展到原有城市邊界以外。這座城市只需一個消防站，位在擁擠的市中心。結(jié)果是當(dāng)火災(zāi)發(fā)生無法快速抵達(dá)城市外圍的地區(qū)。 目標(biāo)：提出一個在城市多處設(shè)立消防站的計畫。新政策： 回應(yīng)時間 10 分鐘16卡林市問題的回應(yīng)時間和本錢相關(guān)資料17卡林市問題的代數(shù)式令 xj = 1 假設(shè)在區(qū)域 j 設(shè)立消防站；否則為 0 (j = 1, 2, , 8)最小化 C = 350 x1 + 250 x2 + 450 x3 + 300 x4 + 50 x5 + 400 x6 + 300 x7 + 200 x8受限於區(qū)域 1: x1 + x2 + x4 1區(qū)域 2: x1 + x2 + x3 1區(qū)域 3: x2 + x3

10、+ x6 1區(qū)域 4: x1 + x4 + x7 1區(qū)域 5: x5 + x7 1區(qū)域 6: x3 + x6 + x8 1區(qū)域 7: x4 + x7 + x8 1區(qū)域 8: x6 + x7 + x8 1且 xj 為二位元 ( j = 1, 2, , 8) 18卡林市問題的試算表方式19機(jī)組人員排班：西南航空公司問題西南航空對於一切排定的航班，需求指派它的機(jī)組人員去執(zhí)行飛航勤務(wù)。我們將焦點擺在：指派三位居住於舊金山San Francisco，簡稱 SFO的機(jī)組人員來執(zhí)行 11 個航班的勤務(wù)。 問題： 應(yīng)該如何將這三位機(jī)組人員指派到三條航線，使得 11 個航班都有人負(fù)責(zé)勤務(wù)？20西南航空的航班21

11、西南航空問題的相關(guān)資料22西南航空問題的代數(shù)式令 xj = 1 假設(shè)接續(xù)航線 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偉伯公司問題考慮整備本錢假設(shè)偉伯公司問題有兩項改變：1. 開始某一產(chǎn)品的生產(chǎn)時需求調(diào)整或設(shè)定生產(chǎn)設(shè)施， 所以會有所謂的整備本錢setup cost。2. 對於每一種產(chǎn)品，每月只需排定一週來生產(chǎn)。所以原始方式中的 D 和 W 現(xiàn)在分別代表門和窗戶的生產(chǎn)量，而不再是生產(chǎn)率。因此，這二個變數(shù)必須限制為整數(shù)。 25原始偉伯問題的圖形解26考慮整備本錢偉伯問題的淨(jìng)利潤27考慮整備本錢偉伯問題的可行解28考慮整備本錢偉伯問題的代數(shù)式令D = 門生產(chǎn)量W = 窗戶生產(chǎn)量y1 = 1 假設(shè)整備來生產(chǎn)門；否則

13、為 0y2 = 1 假設(shè)整備來生產(chǎn)窗戶；否則為 0 最大化 P = 300D + 500W 700y1 1,300y2受限於原始限制式：工廠 1：D 4工廠 2：2W 12工廠 3：3D + 2W 18只需整備才干生產(chǎn)：門：D 99y1窗戶：W 99y2且D 0, W 0, y1 與 y2 為二位元29考慮整備本錢偉伯問題的試算表方式30整數(shù)規(guī)劃何種情況下允許非整數(shù)解？解本身是可以切割的例如：金錢、磅、小時解代表速率例如：每週產(chǎn)量解只是作為規(guī)劃的目的何種情況下允許將解取為整數(shù)？當(dāng)數(shù)值相當(dāng)大時例如：將 114.286 取為 114 或許並無問題何種情況下不允許將解取為整數(shù)？當(dāng)數(shù)值相當(dāng)小時例如：將

14、 2.6 取為 2 或 3 能夠會有問題二位元變數(shù)是否決策31取為整數(shù)能夠構(gòu)成的問題取為整數(shù)後的解能夠不再是可行解。取為整數(shù)後的解能夠已經(jīng)偏離最正確解相當(dāng)遠(yuǎn)。能夠會有許多取為整數(shù)後的整數(shù)解。範(fàn)例：考慮一個具有30 個非整數(shù)值的 LP 變數(shù)解。假設(shè)將這些變數(shù)值取為整數(shù)後，會有多少組能夠的整數(shù)解？32整數(shù)問題如何求解？33整數(shù)問題如何求解續(xù)34二位元變數(shù)的應(yīng)用做是/否類型的決策建造一座工廠？製造一項產(chǎn)品？執(zhí)行一個專案？指派一個人來做一件任務(wù)？集合涵蓋問題指定一組指派使其可以涵蓋一組需求固定本錢假設(shè)啟動某項產(chǎn)品的生產(chǎn)，會伴隨一項固定的整備本錢 假設(shè)一個倉庫運作的話，會有固定的營運費用35範(fàn)例 # 1

15、資本預(yù)算Norwood 開發(fā)公司正考慮四項具潛力的開發(fā)專案。每一項專案最多在三年內(nèi)可以完成。每一項專案所需現(xiàn)金流量、淨(jìng)現(xiàn)值、以及每年可用現(xiàn)金如下表所示。所需現(xiàn)金流量 (百萬美元)可用現(xiàn)金(百萬美元)專案 1專案 2專案 3專案 4第 1 年9761128第 2 年643013第 3 年604010淨(jìng)現(xiàn)值30162214問題：應(yīng)該選擇哪些專案？36Norwood 開發(fā)公司資本預(yù)算的代數(shù)式令 yi = 1 假設(shè)選擇專案 i ； 否則為0 (i = 1, 2, 3, 4)最大化 淨(jìng)現(xiàn)值 = 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 開發(fā)公司資本預(yù)算的試算表解38其他的考量邏輯和相依限制式至少選擇專案 1、2、3 其中一個。除非執(zhí)行專案 3，否則不能執(zhí)行專案 2。專案 3 和專案 4 只能二擇一，不能二者都選。總共專案執(zhí)行件數(shù)不超過二件。問題：假設(shè)有上述這些額外考量，需求參與哪些限制式？39範(fàn)例 # 2集合涵蓋問題華盛頓州議會正想要決定要在哪些地點設(shè)立搜救隊。成立搜

17、救隊需求許多經(jīng)費，所以他們希望所成立的隊伍數(shù)愈少愈好。回應(yīng)時間相當(dāng)關(guān)鍵，所以他們希望每一個郡要有一支搜救隊或是在鄰近的郡要有搜救隊。問題：要在哪些地點設(shè)立搜救隊？40華盛頓州的郡41代數(shù)式令 yi = 1 假設(shè)在郡 i 設(shè)有搜救隊; 0 否則 (i = 1, 2, , 37)最小化 搜救隊數(shù) = 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範(fàn)例 # 3固定本錢Woodridge白鑞錫與鉛、黃銅等的合金製器公司生產(chǎn)三種白鑞製品： 淺盤、碗、以及水罐。每一項產(chǎn)品的製造需求有可運用的機(jī)器和模具。製造每一種產(chǎn)品的機(jī)器和模具可以租用，租金如下: 製造淺盤為 $400週，製造碗為 $250 週，製造水罐為 $300 週。各種產(chǎn)品所需人工和白鑞如下表所示。銷售價格以及變動本錢亦列在表中。人工(小時)白鑞(磅)銷售價格變動成本淺盤35$100$60碗148550水罐437540可用數(shù)量130240問題：應(yīng)該生產(chǎn)哪些製品，以及多少數(shù)量？44代數(shù)式令 x1 = 生產(chǎn)淺盤的數(shù)量x2 = 生產(chǎn)碗的數(shù)量x3 = 生產(chǎn)水罐的數(shù)量 yi =

19、 1 假設(shè)租用製造產(chǎn)品 i 的機(jī)器和模具；否則為 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 磅只需機(jī)器和模具有租用時才可以生產(chǎn)：x1 99y1x2 99y2x3 99y3且xi 0 ， yi 為二位元 (i = 1, 2, 3)45試算表解46二位元變數(shù)之應(yīng)用作是否類型之決策建造一座工廠？製造一項產(chǎn)品？執(zhí)行一個專案？指派某個人執(zhí)行某件任務(wù)？固定本錢假設(shè)生產(chǎn)某項產(chǎn)品，則伴隨有固

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

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

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