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

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

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

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


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

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




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





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

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