整數規劃 Integer Programming

Presentation on theme: "整數規劃 Integer Programming"— Presentation transcript:

1 整數規劃 Integer Programming
第十一章 整數規劃 Integer Programming 作業研究 二版 2009 © 廖慶榮

2 章節大綱 前言 整數規劃應用範例 BIP的分支界限演算法 MIP的分支界限演算法 作業研究 二版 Ch.11 整數規劃

3 11.1 前言 整數規劃（integer programming；IP） 純整數規劃（pure IP；PIP）
11.1 前言 整數規劃（integer programming；IP） 部分或全部變數必須是整數的線性規劃 更周全的名稱應為整數線性規劃（ILP） 純整數規劃（pure IP；PIP） 所有變數都必須是整數 混整數規劃（mixed IP；MIP） 僅部分變數必須是整數 二元整數規劃（binary IP；BIP） 所有的變數均為二元變數 整數形式： 作業研究 二版 Ch.11 整數規劃

4 範例11.1 化整無法得到最佳解甚至可行解 作業研究 二版 Ch.11 整數規劃

5 11.2 整數規劃應用範例 貨物裝載問題（cargo-loading problem） 亦稱為背包問題（knapsack problem）
11.2 整數規劃應用範例 貨物裝載問題（cargo-loading problem） 總重量限制為W的貨車。現在有N類貨物要裝載，其中貨物i的重量為wi、價值為vi。每類貨物應裝多少數量（須為整數），才能獲致最高的總價值？ 亦稱為背包問題（knapsack problem） 登山者放哪些物品在背包，以使背包總價值最高 IP模式： 作業研究 二版 Ch.11 整數規劃

6 範例11.2 /貨物裝載問題 總重量限制200公噸的貨櫃 最佳解： 作業研究 二版 Ch.11 整數規劃

7 資本預算問題 資本預算問題（capital budgeting problem） 應投資哪些計畫，才能獲致最大的總預期收益？ 定義:
IP模式： 作業研究 二版 Ch.11 整數規劃

8 範例11.3 /資本預算問題 問題資料： IP模式： 作業研究 二版 Ch.11 整數規劃

9 固定費用問題 固定費用問題 IP模式： 作業研究 二版 Ch.11 整數規劃

10 範例11.4 /固定費用問題 問題資料：需生產200個位的產品 IP模式： 作業研究 二版 Ch.11 整數規劃

11 兩者擇一限制式 考慮以下兩個限制式 若僅要求兩者之一成立，則其IP模式如下： 作業研究 二版 Ch.11 整數規劃

12 N者擇K限制式 考慮以下四個限制式： 若要求其中三個成立，則其IP模式如下： 作業研究 二版 Ch.11 整數規劃

13 N者擇K限制式 若要求N個限制式中其中K個成立，則 若要求至少K個成立，則 若要求至多K個成立，則 作業研究 二版 Ch.11 整數規劃

14 N個可能的變數值 應用 範例 鋼管的直徑只有三種選擇 欲訂購的產品數量必須是24（一箱）的倍數
假設變數僅能是3.6、5.0、8.2、11.4之一 IP模式： 作業研究 二版 Ch.11 整數規劃

15 從屬限制式 （限制式1） （限制式2） 考慮以下兩個限制式： 若要求當限制式1成立時，限制式2必須成立，則其 IP模式如下： 或
作業研究 二版 Ch.11 整數規劃

16 集合涵蓋問題 範例11.5 該城市應分別在哪些地點建立消防隊，才能以最少的消防隊數涵蓋所有的區域？ 作業研究 二版 Ch.11 整數規劃

17 11.3 BIP的分支界限演算法 理論上，若能有效率地求解BIP問題，則所有IP問 題均得以求解。 例如，對於整數限制：
可用0-1整數轉換如下： 但當變數值很大時，此方式並不是有效率的方法 作業研究 二版 Ch.11 整數規劃

18 Balas分支界限演算法 在應用此演算法前，模式必須滿足以下條件：
目標是極小化 限制式均為≧的形式 目標函數係數滿足 以上的條件並不要求右手邊常數 ，因此任何BIP問題都可轉換為符合這些條件的形式 作業研究 二版 Ch.11 整數規劃

19 範例11.6 Balas演算法的分支樹 作業研究 二版 Ch.11 整數規劃

20 Balas演算法（對min問題） 作業研究 二版 Ch.11 整數規劃

21 Balas演算法（對min問題） 作業研究 二版 Ch.11 整數規劃

22 B&B方法用於max問題 對於一般B&B法，若用於max問題，則需以下修正：
起始步驟：設定 分支步驟：選取UB（upper bound）最大的節點 界限步驟：計算UB，而非LB 洞悉步驟：測試1改為UB≦Z，測試2的LB改為UB 此外，不同的B&B演算法，對於計算界限值的方式以 及洞悉測試的條件等，均有所差異 作業研究 二版 Ch.11 整數規劃

23 11.4 MIP的分支界限演算法 範例11.7 作業研究 二版 Ch.11 整數規劃

24 範例11.7 將原問題分為兩個節 點不會影響原問題的 解 作業研究 二版 Ch.11 整數規劃

25 MIP之B&B法摘要（對max問題） 作業研究 二版 Ch.11 整數規劃

26 MIP之B&B法摘要（對max問題） 作業研究 二版 Ch.11 整數規劃

27 min問題的修正 若為min問題，則需修正： 起始步驟：設定 界限步驟：UB改為LB 洞悉步驟：測試1改為LB≧Z
作業研究 二版 Ch.11 整數規劃