第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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

固定成本 燃料添加劑每噸利潤 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頁

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

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

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

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

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

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

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

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

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

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

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

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

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

配銷系統設計 馬丁貝克問題的最佳解如圖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頁

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

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

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

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

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

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

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

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

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

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

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

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

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

產品設計與市占率最佳化 整數線性規劃的最佳解為 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頁

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

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

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

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

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

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

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