整數(shù)規(guī)劃 割平面法 分枝定界法

1、運 籌 學,整數(shù)線性規(guī)劃,1 整數(shù)規(guī)劃問題,在前面的線性規(guī)劃問題中，它的解都假設為可以取連續(xù)數(shù)值。但是在許多實際問題中，決策變量僅僅取整數(shù)值時才有意義，比如變量表示的是工人的人數(shù)、機器的臺數(shù)、貨物的箱數(shù)、裝貨的車皮數(shù)等等。為了滿足整數(shù)解的要求，比較自然的簡便方法似乎就是把用線性規(guī)劃方法所求得的非整數(shù)解進行“四舍五入”取整或“舍尾取整”處理。當然，這樣做有時確實也是有效的，可以取得與整數(shù)最優(yōu)解相近的可行整數(shù)解，因此它是實際工作中經(jīng)常采用的方法。但是實際問題中并不都是如此，有時這樣處理得到的解可能不是原問題的可行解，有的雖是原問題的可行解，但卻不是整數(shù)最優(yōu)解。（詳見后面例1）。因而有必要專門研究只

2、取整數(shù)解的線性規(guī)劃的解法問題。 在一個線性規(guī)劃問題中，如果它的所有決策變量都要求取整數(shù)時，就稱為純整數(shù)規(guī)劃；如果僅部分決策變量要求取整數(shù)則稱為混合整數(shù)規(guī)劃，二者統(tǒng)稱為整數(shù)規(guī)劃。整數(shù)規(guī)劃的一個特殊情形是0-1規(guī)劃，它的決策變量取值僅限于0或1兩個邏輯值。整數(shù)規(guī)劃是近幾年發(fā)展起來的規(guī)劃論的一個分支,下面我們舉例說明對于整數(shù)規(guī)劃問題，用“四舍五入”取整，或“舍尾取整”方法，是行不通的。 例1 現(xiàn)有甲、乙兩種貨物擬用集裝箱托運，每件貨物的體積、重量、可獲利潤，以及集裝箱的托運限制如下表,試確定集裝箱中托運甲、乙貨物的件數(shù)，使托運利潤最大。 設x1,x2分別表示甲、乙貨物托運的件數(shù)（整數(shù)），則該問題的數(shù)

3、學模型為： maxZ=20 x1+10 x2 5x1+4x224 2x1+5x213 x1,x20，整數(shù),這里貨物的件數(shù)只能是整數(shù)，所以這是一個純整數(shù)規(guī)劃。若先不考慮整數(shù)限制，可求得問題的最優(yōu)解為： x1=4.8，x2=0， maxZ=96 由于x1=4.8不符合整數(shù)要求，所以該解不是整數(shù)規(guī)劃的最優(yōu)解。 是否可以將非整數(shù)解用“四舍五入”方法處理呢？事實上，如果將x1=4.8，x2=0近似為x1=5，x2=0，則該解不符合體積限制條件： 5x1+4x224 因而它不是最優(yōu)解； 那么用“舍尾取整”方法處理又如何呢？將x1=4.8，x2=0 “舍尾取整”為x1=4，x2=0，顯然滿足各約束條件，因而

4、它是整數(shù)規(guī)劃問題的可行解，但它不是整數(shù)最優(yōu)解。因為它對應的目標函數(shù)值Z=80，而x1=4，x2=1這個解亦是可行解，但它對應的目標函數(shù)值Z=90。 由此例看出，簡單的處理方法常常得不到整數(shù)規(guī)劃的最優(yōu)解，甚至得不到可行解。 如何求得這類問題的整數(shù)最優(yōu)解呢？到目前為止，整數(shù)規(guī)劃還沒有一種很滿意的和有效的解法?，F(xiàn)在用以求解整數(shù)規(guī)劃的方法基本都是將整數(shù)規(guī)劃變?yōu)橐幌盗芯€性規(guī)劃來求解的。我們將介紹兩種方法割平面法和分枝定界法,2 割平面法,割平面法是1958年美國學者R.E.Gomory提出的求解純整數(shù)規(guī)劃的一種比較簡便的方法，其基本思想是：先不考慮變量的整數(shù)限制求解線性規(guī)劃，如果得到的解不是整數(shù)解，則不

5、斷增加適當?shù)募s束，割掉原可行域不含整數(shù)解的一部分，最終得到一個具有若干整數(shù)頂點的可行域，而這些頂點中恰有一個頂點是原問題的整數(shù)解。 割平面法的基本步驟： 步驟1 不考慮變量的整數(shù)限制，求解相應的線性規(guī)劃問題，如果該問題無解，或最優(yōu)解已是整數(shù)解，則停止計算，否則轉下一步。 步驟2 對上述線性規(guī)劃的可行域進行“切割”，去掉不含整數(shù)解的一部分可行域，即增加適當?shù)木€性約束，然后轉步驟1,割平面法的關鍵在于如何確定切割方程，使之能對可行域進行真正的切割，而且切去部分不含有整數(shù)解點。 下面討論切割方程的求法,設與整數(shù)規(guī)劃相對應的線性規(guī)劃最優(yōu)解中基變量XBi=（B-1b)i不是整數(shù)，將最優(yōu)單純形表中該基變量

6、對應的行還原成約束方程，即 XBi +aijXj=（B-1b)i 將（B-1b)i，aij都分解成整數(shù)與非負真分數(shù)之和的形式，即 （B-1b)i=Ni+fi 其中0 fi 1 aij=Nij+fij 其中0 fij 1 這里Ni、Nij是整數(shù)，將、 代入，得 XBi +（Nij+fij）Xj=Ni+fi 即 XBi +NijXj-Ni=fi-fijXj 當諸Xi都是整數(shù)時， 式左端是整數(shù)，所以右端亦應是整數(shù)，但右端是兩個正數(shù)之差，且0 fi 1， fi-fijXj是小于1的整數(shù)，從,從而 fi-fijXj0 取式作為切割方程。因為任何整數(shù)可行解都滿足這個方程，所以把它加到原問題的約束中，它能夠

7、對原可行域進行切割，而不會切割掉整數(shù)解,例3 用割平面法求解 maxZ=x1+x2 -x1+x21 3x1+x24 x1,x20，整數(shù),解：將問題標準化得 maxZ=x1+x2 -x1+x2+x3 =1 3x1+x2+x4=4 x1,x20 x1,x2 整數(shù),不考慮條件，求解相應線性規(guī)劃，結果見下表,表中x1=3/4，不是整數(shù)，將表中第一行還原成方程，即 x1-1/4x3+1/4x4=3/4 因為3/4=0+3/4，-1/4=-1+3/4，1/4=0+1/4 所以有 x1-x3=3/4-3/4x3-1/4x4 因而有切割方程： 3/4x3+1/4x4 3/4 即 3x3+x4 3 引入松弛變量

8、x5，得方程 -3x3-x4+x5=-3 將新約束方程加到原最優(yōu)表下面（切割），求得新的最優(yōu)解如下,由于x1，x2的值已是整數(shù)，所以該題經(jīng)一次切割已得最優(yōu)解： x1=1，x2=1，最優(yōu)值：Z=2,現(xiàn)在我們來看看切割方程 3x3+x4 3 的幾何意義。 例3對應的線性規(guī)劃為 maxZ=x1+x2 -x1+x21 3x1+x24 x1,x20,用圖解法求得可行域D及最優(yōu)解點A，見下圖,x2,x1,1,1,1,0,x1+x2=1,3x1+x2=4,A（3/4，7/4,由標準化的約束方程組可得 x3 =1+x1-x2 x4=4 -3x1-x2 代入切割方程 得 3（1+x1-x2）+（4-3x1-x2

9、）3 即 x21，將此切割方程 加入原約束中，就等于切掉原可行域得A1B部分，如圖,B（1，1,D,顯然在A1B區(qū)域不含整數(shù)解點，對原可行域切割的結果是產(chǎn)生了一個新頂點B，用圖解法在新的可行域（黃色）中可求得整數(shù)最優(yōu)解恰是B（1，1,在求解實際問題中，割平面法經(jīng)常會遇到收斂很慢的情況，但若和其它方法，如分枝定界法，聯(lián)合使用，一般能收到比較好的效果,3 分枝定界法,分枝定界法是求解整數(shù)規(guī)劃的常用算法，既可用來解全部變量取值都要求為整數(shù)的純整數(shù)規(guī)劃，又可用以求解混合整數(shù)規(guī)劃。 該算法的基本思路是：先不考慮整數(shù)限制，求出相應的線性規(guī)劃的最優(yōu)解，若此解不符合整數(shù)要求，則去掉不包含整數(shù)解的部分可行域，將

10、可行域D分成D1、D2兩部分（分枝） ，然后分別求解這兩部分可行域對應的線性規(guī)劃，如果它們的解仍不是整數(shù)解，則繼續(xù)去掉不包含整數(shù)解的部分可行域，將可行域D1或D2分成D3與D4兩部分，再求解D3與D4對應的線性規(guī)劃，在計算中若已得到一個整數(shù)可行解X0，則以該解的目標函數(shù)值Z0作為分枝的界限，如果某一線性規(guī)劃的目標值Z Z0 ，就沒有必要繼續(xù)分枝，因為分枝（增加約束）的結果所得的最優(yōu)解只能比Z0 更差。反之若Z Z0 ，則該線性規(guī)劃分枝后，有可能產(chǎn)生比Z0 更好的整數(shù)解，一旦真的產(chǎn)生了一個更好的整數(shù)解，則以這個更好的整數(shù)解目標值作為新的界限，繼續(xù)進行分枝，直至產(chǎn)生不出更好的整數(shù)解為止。 下面以實

11、例來說明算法的步驟,例2 求解下面整數(shù)規(guī)劃 maxZ=40 x1+90 x2 9x1+ 7x256 7x1+20 x270 x1,x20 x1,x2整數(shù),解：先不考慮條件，求解相應的線性規(guī)劃問題L，得最優(yōu)解 x1=4.81，x2=1.82，Z0=356（見圖,x2,8,0,6,4,10,x1,9x1+ 7x2=56,7x1+20 x2=70,Z=40 x1+90 x2,該解不是整數(shù)解。選擇其中一個非整數(shù)變量，如x1=4.81，對問題L分別增加約束條件： x14，x15 將問題L分解為兩個子問題L1，L2（分枝），也就是去掉問題L不含整數(shù)解的一部分可行域，將原可行域D變?yōu)镈1、D2兩部分（如圖,

12、4,D1,D2,因為沒有得到整數(shù)解，所以繼續(xù)對L1進行分解，增加約束： x22，x23將L1分解成問題L3與L4，并求得最優(yōu)解如下,問題L3的解已是整數(shù)解，它的目標值Z3=340，大于問題L4的目標值，所以問題L4已無必要再分枝。但由于問題L2的目標值Z2大于Z3，分解L2還有可能產(chǎn)生更好的整數(shù)解，因此繼續(xù)對L2分枝。增加約束 x21，x22 將L2分解成問題L5與L6，并求解，結果如下,問題L5的Z5 =308 Z3=340 ，所以不必分解了；問題L6無可行解，于是可以斷定問題L3的解： x1=4.00，x2=2.00即為最優(yōu)整數(shù)解,整個分枝定界過程如下圖所示,問題L Z0=356 x1=4

13、.81x2=1.82,問題L1 Z1=349 x1=4.00，x2=2.10,問題L2 Z2=341 x1=5.00，x2=1.57,問題L3 Z3=340 x1=4.00 x2=2.00,問題L4 Z4=327 x1=1.42 x2=3.00,問題L5 Z5=308 x1=5.44，x2=1.00,問題L6 無可行解,x14,x15,x22,x23,x21,x22,Z=340,用分枝定界法求解整數(shù)規(guī)劃的步驟可總結如下： 步驟1：求解與整數(shù)規(guī)劃相對應的線性規(guī)劃L，若L無可行解，則整數(shù)規(guī)劃也沒有可行解，計算停；若L的最優(yōu)解是整數(shù)解，則該解即為整數(shù)規(guī)劃的最優(yōu)解，計算停；若L的最優(yōu)解不是整數(shù)解，則轉步驟2。 步驟2（分枝）在L的最優(yōu)解中任選一個不符合整數(shù)條件的變量XBi，其值為（B-1b)i，（B-1b)i 為小于（B-1b)i的最大整數(shù)，構造兩個約束條件 XBi （B-1b)i 和XBi （B-1b)i +1 將這兩個約束條件分別加在問題L的約束條件上，形成兩個子問題L1和L2，并求解L1和L2 。 步驟3（定界 ）取