整數(shù)線性規(guī)劃ILP

第7章 整數(shù)線性規(guī)劃（ILP） 在前面討論的線性規(guī)劃問題中，最優(yōu)解可能是分數(shù)或小數(shù)，但對于某些具體問題常要求解答是整數(shù)。我們稱這樣的線性規(guī)劃問題為整數(shù)線性規(guī)劃問題（Integer Linear Programming 簡記為ILP）,整數(shù)規(guī)劃是近20年來發(fā)展起來的規(guī)劃論的一個分支。
一、數(shù)線性規(guī)劃問題的提出 整數(shù)規(guī)劃中如果所有的變量都限制為（非負）整數(shù)，就稱為純整數(shù)規(guī)劃（Pure ILP）,如果僅一部分變量限制為整數(shù)，就稱為混合整數(shù)規(guī)劃（Mixed ILP）,整數(shù)規(guī)劃的一個特例就是0—1規(guī)劃，他的變量僅取0或1。
整數(shù)線性規(guī)劃問題舉例 1、  投資決策問題 某部門在今后五年中可用于投資的資金總額為B萬元，有n(n 2)個可以投資的項目，假定每個項目最多投資一次，第j個項目所需投資資金為 萬元，獲得的利潤為 萬元， 問如何選擇投資項目，才能使獲得的總利潤最大。
設獲得的總利潤為z，則上述問題的數(shù)學模型為：

顯然上述是一個決策變量只能取0或1的整數(shù)規(guī)劃問題，這樣的整數(shù)規(guī)劃問題稱為0——1規(guī)劃。決策變量取0或1這個約束可以用一個非線性約束來代替：
2、  某廠擬用集裝箱托運甲乙兩種貨物，每箱的體積、重量、可獲得的利潤及托運所受的限制入下表：

解：設 分別為甲乙兩種貨物的托運箱數(shù)，設獲得的總利潤為z，則上述問題的數(shù)學模型為：
3、旅行售貨員問題（貨郎擔問題）


第一組約束條件表示各個城市恰好進入一次，第二約束條件表示各個城市恰好離開一次，第三組約束條件用以防止出現(xiàn)對于一個互不連通的旅行路線圈。 顯然這是一個混合整數(shù)規(guī)劃問題。
二、整數(shù)線性規(guī)劃問題的求解 ——割平面法
（1）       基本思想 給出整數(shù)規(guī)劃
可先求其對應的線性規(guī)劃問題

  （2）割平面法求解ILP問題的一般步驟




三、整數(shù)線性規(guī)劃問題的求解 ——分枝定界法（Branch and Bound Method）
1）基本思想 分枝定界法求解整數(shù)規(guī)劃問題的基本思想是：通過分枝枚舉來尋找最優(yōu)解。實施的作法是：首先不考慮對變量的整數(shù)要求，求解相應的線性規(guī)劃問題，如求得的最優(yōu)解不符合整數(shù)要求，則把原問題分解為兩部分，每一部分都增加新的約束條件以減小原線性規(guī)劃問題的可行域。通過不斷地分解，逐步逼近滿足要求的最優(yōu)解，直到求得最優(yōu)解。在這個過程中包括了"分枝"和"定 界"兩個關鍵步驟。
（2）分枝定界法求解ILP問題的一般步驟 根據(jù)分枝定界法的基本思想，人們歸納總結(jié)出了分枝定界法求解整數(shù)規(guī)劃問題的一般步驟，這里以求目標函數(shù)值最大化問題為例加以說明：  給出整數(shù)規(guī)劃
可先求其對應的線性規(guī)劃問題





分枝定界法可用于解純整數(shù)規(guī)劃問題，也可以用于求混合整數(shù)規(guī)劃問題。在20世紀60年代初由Land和Dong提出經(jīng)Dakin修正的，其優(yōu)點是方法靈活并且十分便于計算機求解，所以現(xiàn)在它已成為求解整數(shù)規(guī)劃的重要方法之一，目前已成功地應用于求解整數(shù)規(guī)劃問題、生產(chǎn)進度表問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等。分枝定界法比窮舉法優(yōu)越，因為它僅在一部分可行解的整數(shù)解中尋求最優(yōu)解，計算量比窮舉法小，但若變量數(shù)目很大，其計算工作量也是相當可觀的。因此，它有時也需要與其他方法(如切割平面法)配合使用，效率更高一些。  
四、ILP問題的計算機求解

整數(shù)線性規(guī)劃ILP