第9章 整數線性規劃 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.

Presentation on theme: "第9章 整數線性規劃 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted."— Presentation transcript:

1 第9章 整數線性規劃 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

2 第9章 整數線性規劃 9.1 整數線性規劃模式的類型 9.2 全整數線性規劃的圖解及電腦解 9.3 包含0-1變數的應用
整數變數賦予的建模彈性 第9章 整數線性規劃 第373頁

3 前言 線性規劃模式中，額外要求一個或更多決策變數必須為整數，此類問題稱為整數線性規劃(integer linear programs)。
如果所有變數都必須是整數，稱為全整數線性規劃。 如果只有某些變數，而不是全部變數都為整數，則稱為混合整數線性規劃。 某些線性規劃應用的一些變數被要求必須為0 或1，此種變數稱為 0-1 或二元變數(binary variables)。 如果所有的變數都是 0-1 變數，則稱為 0-1 整數線性規劃。 第9章 整數線性規劃 第374頁

4 9.1 整數線性規劃模式的類型 以下是兩個變數的全整數線性規劃模式。
在上述模式中將「且為整數」去掉，就成為我們熟知的兩變數線性規劃。去掉決策變數必須為整數的要求，得到的線性規劃問題，稱為整數線性規劃的 LP 寬鬆式(LP Relaxation)。 第9章 整數線性規劃 第375頁

5 9.1 整數線性規劃模式的類型 只有一部分而非全部的決策變數必須是整數，則稱為混合整數線性規劃(mixed-integer linear program)。以下是二變數的混合整數線性規劃模式。 若去掉 x2 必須為整數的要求，則得到混合整數線性規劃的 LP 寬鬆式。 第9章 整數線性規劃 第 頁

6 9.2 全整數線性規劃的圖解及電腦解 東生不動產公司可用2,000,000 美元購置房屋以供出租。經過初步篩選，公司將投資方案限定為別墅及公寓。別墅每棟 282,000 美元，目前有 5 戶別墅可購買；每棟公寓售價 400,000 美元，公寓的供應數量則沒有上限。 管理人員每個月最多有 140 工作小時。每棟別墅每個月需要 4 小時來管理，每棟公寓則需 40 小時。每年現金流量入扣除貸款及費用後，別墅每棟為 10,000 美元，公寓每棟為 15,000 美元。公司要決定別墅及公寓的購買數量，使年收入最高。 第9章 整數線性規劃 第377頁

7 9.2 全整數線性規劃的圖解及電腦解 定義決策變數如下：
變數T及A 必須非負數，而且沒有不是一棟的別墅和公寓，因此T及A必須是整數。東生不動產問題成為全整數線性規劃如下： 第9章 整數線性規劃 第 頁

8 LP寬鬆式的圖解 以第 2 章的圖解法解東生不動產問題的 LP 寬鬆式，最佳解如圖 9.1，得到別墅為 棟，公寓為 棟。 第9章 整數線性規劃 第378頁

9 LP寬鬆式的圖解 第9章 整數線性規劃 第379頁

10 利用四捨五入得到整數解 許多時候，四捨五入非整數解後可得到可接受的整數解。
四捨五入並非永遠都是好對策。當決策變數的數值很小，卻對目標函數的值或限制式的滿足與否有很大的影響時，就需要真正的整數最佳解。 東生不動產問題 LP 寬鬆式的最佳解為T = 棟別墅，A = 棟公寓。由於每棟別墅價值 282,000 美元，每棟公寓價值 400,000 美元，可預期以四捨五入得到整數解將對問題產生重大的經濟衝擊。 四捨五入成整數解是試誤過程，必須評估每一個四捨五入得到的解的可行性及對目標函數值的影響。即使四捨五入解是可行解，也不能保證已經是最佳整數解。 第9章 整數線性規劃 第 頁

11 全整數問題的圖解 將目標函數線往值比較大的方向移動，直到使其值為最大的點為止。
最佳整數解發生在 T = 4 棟別墅和 A = 2 棟公寓的點。現金年收入為 70,000 美元。 第9章 整數線性規劃 第380頁

12 全整數問題的圖解 非可行解 T=2, A=4 T=2, A=3 T=3, A=3 第9章 整數線性規劃 第380頁

13 利用LP寬鬆式建立解的界限 關係到整數解的最佳值和 LP 寬鬆式解的最佳解。
如果 LP 寬鬆式的解恰好是整數解，必定也是整數線性規劃的最佳解。LP 寬鬆式的四捨五入解是可行解，而且其目標函數值幾乎和 LP 寬鬆式的最佳解「一樣好」，就可以知道此四捨五入解是一個近似最佳整數解。此時，我們也可以省去解整數線性規劃問題的麻煩。 第9章 整數線性規劃 第 頁

14 電腦解 LINGO 或Frontline System 的Solver 可用來解本章大部分的整數線性規劃。本章附錄會說明如何使用EXCEL 的規劃求解來處理整數線性規劃。 第9章 整數線性規劃 第381頁

15 9.3 包含 0-1 變數的應用 整數線性規劃在建立模型時的彈性，許多來自使用 0-1 變數。
許多應用的0-1 變數表示選擇與否，變數值為 1 代表採用對應的活動，變數值為 0 則代表不採用對應的活動。 第9章 整數線性規劃 第381頁

16 資本預算 艾思可冰箱公司考慮往後 4 年期間各種不同資金需求的投資計畫。如表 9.1。 第9章 整數線性規劃 第382頁

17 資本預算 四個 0-1 決策變數如下： 資本預算問題(capital budgeting problem) 的公司目標函數是使資本預算計畫的淨現值最大。問題共有四個限制式，各代表每年的可用資金。 第9章 整數線性規劃 第382頁

18 資本預算 0-1 整數線性規劃模式如下，以千美元為單位： 第9章 整數線性規劃 第382頁

19 資本預算 整數規劃解如圖 9.4。最佳解為 P = 1、W = 1、M = 1、R = 0， 總淨現值為140,000 美元。
公司應該投資工廠擴建計畫、倉庫擴建計畫及購買新機器。 應該暫停新產品研發計畫，除非還有額外可用資金。 圖 9.4 的寬鬆變數顯示，公司在第1 年有 5000 美元的剩餘資金，第 2 年有 15,000 美元的剩餘資金，第 4 年有 11,000 美元的剩餘資金。 第9章 整數線性規劃 第 頁

20 資本預算 第9章 整數線性規劃 第383頁

21 固定成本 使用 0-1 變數，得以將生產應用模式中的固定成本納入考慮。 RMC 公司固定成本問題(fixed cost problem)
決策變數如下： 第9章 整數線性規劃 第383頁

22 固定成本 燃料添加劑每噸利潤 40 美元、溶劑基劑每噸 30 美元及地毯清潔劑每噸 50 美元。
每噸燃料添加劑含 0.4 噸原料 1 及 0.6 噸原料 3；每噸溶劑基劑含 0.5 噸原料 1、0.2 噸原料 2 及 0.3 噸原料 3；每噸地毯清潔劑含 0.6 噸原料 1、0.1 噸原料 2 及 0.3 噸原料 3。 RMC 公司有 20 噸的原料 1、5 噸的原料 2 及 21 噸的原料 3。 第9章 整數線性規劃 第383頁

23 固定成本 RMC 問題的線性規劃模式如下： 最佳解是 27.5 噸的燃料添加劑、0 噸的溶劑基劑及 15 噸的地毯清潔劑，最大利潤為 1850 美元，見圖 9.5。 第9章 整數線性規劃 第 頁

24 固定成本 第9章 整數線性規劃 第384頁

25 固定成本 重寫目標函數式，加入整備成本。淨利的目標函數變成： 重寫產能限制式，以便整備變數為 0 時，不允許生產該產品；
第9章 整數線性規劃 第 頁

26 固定成本 RMC 問題的固定成本模式如下： 第9章 整數線性規劃 第385頁

27 固定成本 如圖 9.6。最佳解為 25 噸的燃料添加劑及 20 噸的溶劑基劑。減去整備成本後的目標函數值為 1350 美元。
第9章 整數線性規劃 第385頁

28 固定成本 建立固定成本模式的關鍵，在於為每項固定成本引入0-1 變數，並且為該項產品確立其產量上限。
對產量 x，可以使用型如 x ≤ My 的限制式，當 y = 1 時表示可以生產；當整備變數 y = 0 時則表示不生產。 第9章 整數線性規劃 第386頁

29 配銷系統設計 馬丁貝克公司計畫在底特律、拖利多、丹佛或堪薩斯市增設工廠以增加產量。估計四個候選地點的年固定成本及產能估計值如下：
第9章 整數線性規劃 第373頁

30 配銷系統設計 公司的長程規劃小組預估各配銷中心的年需求量如下： 第9章 整數線性規劃 第386頁

31 配銷系統設計 從各工廠到各配銷中心的單位運輸成本如表 9.2。
可能的配銷系統網路模式如圖 9.7，產能及需求皆以千為單位。興建工廠的地點尚未決定。 第9章 整數線性規劃 第386頁

32 配銷系統設計 第9章 整數線性規劃 第387頁

33 配銷系統設計 配銷系統設計問題(distribution system design problem)利用 0-1 變數建立模式，以選擇最佳的工廠設置地點，並決定每一家工廠至各配銷點的運輸量。我們可使用以下的 0-1 變數代表設廠的決定。 工廠至配銷點的運輸量變數，定義方式和運輸問題一樣。 第9章 整數線性規劃 第 頁

34 配銷系統設計 新工廠每年營運的固定成本，以千美元為單位表示成： 第9章 整數線性規劃 第388頁

35 配銷系統設計 馬丁貝克配銷系統設計問題的完整模式如下： 第9章 整數線性規劃 第 頁

36 配銷系統設計 馬丁貝克問題的最佳解如圖9.8。 在堪薩斯市設置新廠(y4 = 1)；將從堪薩斯市運送20,000 個產品到亞特蘭大(x42 = 20)，另外 20,000 個從堪薩斯市運往休士頓(x43 = 20)，以及從聖路易市運送 30,000 個產品往波士頓(x51 = 30)。總成本為 860,000美元 可擴充此基本模式。利用 0-1 變數的特殊性質，此模式修改後也可以適應各種不同的設廠位置限制條件。例如，加入以下的限制式： 此限制式允許 y1 或 y2 其中一個為 1，但不允許同時為 1。如果我們把限制式寫成等式，則在達拉斯及渥夫茲堡之中必須選一個地方設廠。 第9章 整數線性規劃 第389頁

37 配銷系統設計 第9章 整數線性規劃 第390頁

38 銀行設址 俄亥俄信託的長程規劃部門打算擴展業務到俄亥俄州東北的 20 個郡（圖 9.9）。依據俄亥俄州的銀行法，銀行在某郡設立業務中心(principal place of business, PPB) 之後，就可以在該郡或鄰郡設立分行。 第9章 整數線性規劃 第 頁

39 銀行設址 第9章 整數線性規劃 第391頁

40 銀行設址 公司要找出在 20 個郡營業所需最少 PPB 數。0-1 整數規劃模式可以解決俄亥俄信託這個設址問題(location problem)。我們定義變數如下： 為使所需 PPB 數目最少，我們將目標函數寫成： 滿足此限制式可確保有一個 PPB 會設在 Ashtabula 郡或其相鄰的郡。 第9章 整數線性規劃 第 頁

41 銀行設址 第9章 整數線性規劃 第392頁

42 銀行設址 銀行設址問題的完整模式如下： 圖 9.10 是俄亥俄信託 PPB 設址問題解。從這個結果可看到最佳解是在 Ashland郡、Stark 郡及 Geauga 郡設置業務中心。 第9章 整數線性規劃 第392頁

43 銀行設址 第9章 整數線性規劃 第393頁

44 銀行設址 第9章 整數線性規劃 第394頁

45 產品設計與市占率最佳化 聯合分析是一種市場調查技術，可用於瞭解潛在顧客如何評價產品屬性。
說明如何將聯合分析的結果用於產品設計與市占率最佳化問題(product design and market share optimization problem) 的整數規劃模式。 表 9.4 是由八位樣本顧客提供的每一屬性每一等級的部分價值。消費者 1 給薄餅皮的部分價值是 11，厚餅皮是 2，顯示出對薄餅皮的偏好。 第9章 整數線性規劃 第 頁

46 產品設計與市占率最佳化 第9章 整數線性規劃 第395頁

47 產品設計與市占率最佳化 部分價值可以決定每位消費者賦予某一種披薩的整體價值（效用）。例如，消費者 1 目前喜歡安東尼牌披薩，這種披薩採用厚餅皮、馬茲瑞拉起司、嗆辣醬料和口味適中的香腸。可以利用表 9.4 的部分價值找出這種披薩對消費者 1 的效用。安東尼牌披薩對消費者 1 的效用為 = 52。 國王牌披薩採用的是薄餅皮，對消費者 1 的效用為 = 47。一般而言，某一種披薩對消費者的效用等於相關部分價值總和。 第9章 整數線性規劃 第 頁

48 產品設計與市占率最佳化 為了品牌的成功，必須誘使市場的消費者從現在購買的品牌轉向雪倫。可以利用求解整數規劃模式幫助雪倫找出適當的披薩組合。行銷文獻將此稱為選擇共享(share of choices) 問題。 決策變數定義如下： 目標是選擇屬性使選擇產品的消費者數極大化。目標函數為： 第9章 整數線性規劃 第395頁

49 產品設計與市占率最佳化 本研究中八位消費者的限制式： 每個屬性必須再加上一個限制式，確保每個屬性只選擇一個等級。
第9章 整數線性規劃 第396頁

50 產品設計與市占率最佳化 整數線性規劃的最佳解為 l11 = l22 = l23 = l14 = 1，y1 = y2 = y6 = y7 = 1。最佳解的目標值為 4，表示若雪倫生產此種披薩，八位顧客中有四位的喜歡程度將會高於他們現在購買的品牌。由於 l11 = l22 = l23 = l14 = 1，為雪倫取得最大市場占有率的披薩口味將會採用薄餅皮、混合起司、嗆辣醬料及淡味香腸。 y1 = y2 = y6 = y7 = 1 代表消費者 1、2、6、7 會喜歡雪倫披薩。 第9章 整數線性規劃 第373頁

51 9.4 0-1 整數變數賦予的建模彈性 利用 0-1 整數變數建立多重選擇與互斥的限制式。
整數變數賦予的建模彈性 利用 0-1 整數變數建立多重選擇與互斥的限制式。 中艾思可冰箱公司的資本預算問題。假設艾思可冰箱公司共考慮三個倉庫擴建計畫，至少必須擴建一個倉庫，但需求量尚不足以擴建一個以上的倉庫。以下所定義的變數，以及多重選擇限制式(multiple-choice constraint)，可加入原先的 0-1 整數線性規劃模式以反映此狀況。令 第9章 整數線性規劃 第 頁

52 多重選擇與互斥限制式 表達只能且必須有一個倉庫擴建計畫被接受的多重選擇限制式，可以寫成：
如果不要求至少必須擴建一個倉庫，多重選擇限制條件就可以修改為： 此種修改可允許不擴建倉庫 (W1 = W2 = W3 = 0)，但不允許擴建一個以上的倉庫。通常稱此限制式為互斥限制式(mutually exclusive constraint)。 第9章 整數線性規劃 第398頁

53 n 個方案中選擇 k 個方案的限制式 假設 W1、W2、W3、W4 及 W5 代表五種可能的倉庫擴建計畫，且必須在其中選擇兩個。滿足新要求的限制式為： 這些變數的值都必須限制為 0-1 值。 第9章 整數線性規劃 第398頁

54 條件性與同時要求之限制式 假設艾思可冰箱公司除非擴建工廠，否則不
考慮擴建倉庫。以 P 代表工廠擴建，W 代表倉庫擴建，以下條件限制式(conditional constraint) 能夠滿足這個要求： 如果接受工廠擴建計畫，也要接受倉庫擴建計畫，反之亦然，則我們稱 P 與 W表示共同要求限制式(corequisite constraint)。只要將前述的限制式改為等式即可： 第9章 整數線性規劃 第399頁

55 條件性與同時要求之限制式 第9章 整數線性規劃 第400頁

56 敏感度分析的注意事項 整數線性規劃的敏感度分析比線性規劃問題更重要。限制式係數非常小的改變就可能使最佳解的值產生很大變化。考慮以下整數線性規劃模式： 最佳解為 x1 = 1、x2 = 1、x3 = 1 及 x4 = 0，目標函數值為 170 美元。但是如果可用資金增加 1 美元（從 100 美元到 101 美元），最佳解將變成 x1 = 1、x2 = 0、x3 = 0 及 x4 = 1，目標函數值為 200 美元，也就是預算增加 1 美元將使報酬增加 30 美元。 第9章 整數線性規劃 第 頁

57 敏感度分析的注意事項 由於最佳解的目標值對限制式的係數非常敏感，因此建議在選定最佳解之前，先將係數稍作變化，然後再解整數線性規劃數次。
第9章 整數線性規劃 第401頁