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

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

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

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


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

  （2）割平面法求解ILP問(wèn)題的一般步驟




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





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

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