二元整数规划.ppt

範例11.6 作業研究 二版 Ch.11 整數規劃 作業研究 二版 Ch.11 整數規劃 第十一章 整數規劃 Integer Programming ? 廖慶榮 作業研究 二版 2009 p.*/27 章節大綱 前言 整數規劃應用範例 BIP的分支界限演算法 MIP的分支界限演算法 作業研究 二版 Ch.11 整數規劃 作業研究 二版 Ch.11 整數規劃 p.*/27 11.1 前言 整數規劃（integer programming；IP） 部分或全部變數必須是整數的線性規劃 更周全的名稱應為整數線性規劃（ILP） 純整數規劃（pure IP；PIP） 所有變數都必須是整數 混整數規劃（mixed IP；MIP） 僅部分變數必須是整數 二元整數規劃（binary IP；BIP） 所有的變數均為二元變數 整數形式： 1. 2. 作業研究 二版 Ch.11 整數規劃 p.*/27 範例11.1 化整無法得到最佳解甚至可行解 作業研究 二版 Ch.11 整數規劃 p.*/27 11.2 整數規劃應用範例 貨物裝載問題（cargo-loading problem） 總重量限制為W的貨車。現在有N類貨物要裝載，其中貨物i的重量為wi、價值為vi。每類貨物應裝多少數量（須為整數），才能獲致最高的總價值？ 亦稱為背包問題（knapsack problem） 登山者放哪些物品在背包，以使背包總價值最高 IP模式： 作業研究 二版 Ch.11 整數規劃 p.*/27 範例11.2 /貨物裝載問題 總重量限制200公噸的貨櫃 最佳解： 作業研究 二版 Ch.11 整數規劃 p.*/27 資本預算問題 資本預算問題（capital budgeting problem） 應投資哪些計畫，才能獲致最大的總預期收益？ 定義: IP模式： 作業研究 二版 Ch.11 整數規劃 p.*/27 範例11.3 /資本預算問題 問題資料： IP模式： 作業研究 二版 Ch.11 整數規劃 p.*/27 固定費用問題 固定費用問題 IP模式： 作業研究 二版 Ch.11 整數規劃 p.*/27 範例11.4 /固定費用問題 問題資料：需生產200個位的產品 IP模式： 作業研究 二版 Ch.11 整數規劃 p.*/27 兩者擇一限制式 考慮以下兩個限制式 若僅要求兩者之一成立，則其IP模式如下： 作業研究 二版 Ch.11 整數規劃 p.*/27 N者擇K限制式 考慮以下四個限制式： 若要求其中三個成立，則其IP模式如下： 作業研究 二版 Ch.11 整數規劃 p.*/27 N者擇K限制式 若要求N個限制式中其中K個成立，則 若要求至少K個成立，則 若要求至多K個成立，則 作業研究 二版 Ch.11 整數規劃 p.*/27 N個可能的變數值 應用 鋼管的直徑只有三種選擇 欲訂購的產品數量必須是24（一箱）的倍數 範例 假設變數僅能是3.6、5.0、8.2、11.4之一 IP模式： 作業研究 二版 Ch.11 整數規劃 p.*/27 從屬限制式 考慮以下兩個限制式： （限制式1） （限制式2） 若要求當限制式1成立時，限制式2必須成立，則其IP模式如下： 或 作業研究 二版 Ch.11 整數規劃 p.*/27 集合涵蓋問題 範例11.5 該城市應分別在哪些地點建立消防隊，才能以最少的消防隊數涵蓋所有的區域？ 作業研究 二版 Ch.11 整數規劃 p.*/27 11.3 BIP的分支界限演算法 理論上，若能有效率地求解BIP問題，則所有IP問題均得以求解。 例如，對於整數限制： 可用0-1整數轉換如下： 但當變數值很大時，此方式並不是有效率的方法 作業研究 二版 Ch.11 整數規劃 p.*/27 Balas分支界限演算法 在應用此演算法前，模式必須滿足以下條件： 目標是極小化 限制式均為≧的形式 目標函數係數滿足 以上的條件並不要求右手邊常數 ，因此任何BIP問題都可轉換為符合這些條件的形式 ＊再將變數重新編號 作業研究 二版 Ch.11 整數規劃 p.*/27 範例11.6 Balas演算法的分支樹 作業研究 二版 Ch.11 整數規劃 p.*/27 Balas演算法（對min問題） 作業研究 二版 Ch.11 整數規劃 p.*/27 Ba