愛華網(wǎng)如果區(qū)別與線性規(guī)劃的話，整數(shù)規(guī)劃就是求變量取值為整數(shù)時候的最優(yōu)解，首先聲明的是整數(shù)最優(yōu)解不能通過簡單的線性最優(yōu)解取整而獲得。
整數(shù)規(guī)劃的解決方法有幾個比較主流的，分枝定界是在線性規(guī)劃的基礎(chǔ)上理解起來較為簡單的算法，蒙特卡洛算法是聽起來比較cool的，所以打算準(zhǔn)備整理一下這兩個。
慣例，先念詩：亡我祁連山，使我牛羊不蕃息;失我胭脂山，令我婦女無顏色。
分枝定界有些搜索的基因，是在可行解空間內(nèi)的適當(dāng)搜索和縮小范圍。分枝，把全部的可行解空間反復(fù)地分割為越來越小的子集。定界，對每個子集內(nèi)的解集計(jì)算一個目標(biāo)下屆。越界的可行解子集丟棄不再分枝（剪枝）。
每個整數(shù)規(guī)劃問題A都會有一個線性規(guī)劃問題B與其遙相呼應(yīng)，暗送秋波（注意節(jié)操！摔！）。想，如果線性規(guī)劃的最優(yōu)解不是整數(shù)解，那這個最優(yōu)解顯然就是整數(shù)解的上界，而可行解內(nèi)的任意整數(shù)解都可以使最優(yōu)整數(shù)解的下界。如果你能把這個空間逐步縮小，最后就能找到最優(yōu)整數(shù)解。
例：
求整數(shù)規(guī)劃問題A： max z = 40a + 90b
9a +7b <=56
7a + 20b <=70
a,b >=0
解：
按照線性規(guī)劃求一下式子的最優(yōu)解:
c=[-40;-90] A=[9,7;7,20] b=[56;70]
linprog(c,A,b,[],[],zeros(2,1))
Optimization terminated.
ans=
4.8092
1.8168
如上最優(yōu)解為 a =4.8092 b= 1.8168 最大 z=355.8779顯然，最優(yōu)解不是整數(shù)解，所以整數(shù)最優(yōu)解的z*將以z=355.8779為上界；由題可知a=0b=0顯然是問題的一個整數(shù)可行解。所以我們得到一個相對較大的最優(yōu)解范圍0<= z*<=356。
下面我們就做分枝工作： 因?yàn)樽顑?yōu)解中兩個變量都不是整數(shù)，我們?nèi)芜x一個進(jìn)行分枝，如選 a=4.8092 把a(bǔ)分成兩個子集 第一個：a<=[4.8092]=4 第二個：a>=[4.8092]+1=5同時便把問題A劃分成了兩個問題A1和A2，且因?yàn)?和5之間沒有整數(shù)兩個問題的整數(shù)最優(yōu)解就是原題目的整數(shù)最優(yōu)解：
A1：max z = 40a + 90b
9a +7b <=56
7a + 20b <=70
a<=4,b >=0
A2：max z = 40a + 90b
9a +7b <=56
7a + 20b <=70
a>=5,b >=0
A1:linprog([-40;-90],[9,7;7,20;1,0],[56;70;4],[],[],zeros(2,1))
A2:linprog([-40;-90],[9,7;7,20;-1,0],[56;70;-5],[],[],zeros(2,1))
A1的最優(yōu)解為 a= 4.0000 b = 2.1000z1 =349
A2的最優(yōu)解為 a =5.0000 b = 1.5700z2 = 341.4
選取兩個最優(yōu)解大的更新上界，如果兩個最優(yōu)解存在整數(shù)解，更新下界，這里兩個都不是整數(shù)解所以不更新下界。這一步定界完后，目標(biāo)函數(shù)范圍是：0<=z*<=349。
由于沒有得到最優(yōu)整數(shù)解，還需要繼續(xù)分枝。
那先將A1分為A11和A12兩個問題(由于都是一樣的工作，我只列出linprog函數(shù))。
A11：linprog([-40;-90],[9,7;7,20;1,0;0,1],[56;70;4;2],[],[],zeros(2,1))
最優(yōu)解： a = 4.0000 b = 2.0000;z11 = 340
A12:linprog([-40;-90],[9,7;7,20;1,0;0,-1],[56;70;4;-3],[],[],zeros(2,1))
最優(yōu)解： a = 1.4286 b = 3.0000;z12 = 327.2
我們得到一個整數(shù)可行解，雖然不知道它是不是最優(yōu)的，但能更新目標(biāo)函數(shù)的下界340<=z*<=356
這個界可以幫我們進(jìn)行剪枝，如A12中不可能在出現(xiàn)某個整數(shù)可行解使z>340>327.2，變量在那一部分的取值可舍棄，即剪枝。
而，不要忘了我們還有A2沒有分枝，需要分成A21和A22，
A21：linprog([-40;-90],[9,7;7,20;-1,0;0,1],[56;70;-5;1],[],[],zeros(2,1))
最優(yōu)解： a = 5.4 b = 1 ; z21 = 308
A22:linprog([-40;-90],[9,7;7,20;-1,0;0,-1;],[56;70;-5;2],[],[],zeros(2,1))
無最優(yōu)解
由于在分枝A1的時候確定了新的界，由線性最優(yōu)解可知，A21和A22空間內(nèi)不可能出現(xiàn)使目標(biāo)函數(shù)z值大于340（下界）的的整數(shù)解，兩部分都能剪枝。
至此，只剩下A11空間，且已知最優(yōu)解 a = 4.0000 b = 2.0000; z11 =340。
那在原空間內(nèi)a = 4 ,b = 2 ,z* = 340 ，就是我們所找的最優(yōu)整數(shù)解。
