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

運籌學(xué)整數(shù)線性規(guī)劃整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第1頁!§1整數(shù)規(guī)劃問題在前面的線性規(guī)劃問題中，它的解都假設(shè)為可以取連續(xù)數(shù)值。但是在許多實際問題中，決策變量僅僅取整數(shù)值時才有意義，比如變量表示的是工人的人數(shù)、機(jī)器的臺數(shù)、貨物的箱數(shù)、裝貨的車皮數(shù)等等。為了滿足整數(shù)解的要求，比較自然的簡便方法似乎就是把用線性規(guī)劃方法所求得的非整數(shù)解進(jìn)行“四舍五入”取整或“舍尾取整”處理。當(dāng)然，這樣做有時確實也是有效的，可以取得與整數(shù)最優(yōu)解相近的可行整數(shù)解，因此它是實際工作中經(jīng)常采用的方法。但是實際問題中并不都是如此，有時這樣處理得到的解可能不是原問題的可行解，有的雖是原問題的可行解，但卻不是整數(shù)最優(yōu)解。（詳見后面例1）。因而有必要專門研究只取整數(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ī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第2頁!下面我們舉例說明對于整數(shù)規(guī)劃問題，用“四舍五入”取整，或“舍尾取整”方法，是行不通的。例1現(xiàn)有甲、乙兩種貨物擬用集裝箱托運，每件貨物的體積、重量、可獲利潤，以及集裝箱的托運限制如下表：貨物體積（米3/件）重量（萬斤/件）利潤（萬元/件）甲乙54252010托運限制2413試確定集裝箱中托運甲、乙貨物的件數(shù)，使托運利潤最大。設(shè)x1,x2分別表示甲、乙貨物托運的件數(shù)（整數(shù)），則該問題的數(shù)學(xué)模型為：maxZ=20x1+10x2⑴5x1+4x2≤24⑵2x1+5x2≤13⑶x1,x2≥0，整數(shù)⑷

整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第3頁!§2割平面法割平面法是1958年美國學(xué)者R.E.Gomory提出的求解純整數(shù)規(guī)劃的一種比較簡便的方法，其基本思想是：先不考慮變量的整數(shù)限制求解線性規(guī)劃，如果得到的解不是整數(shù)解，則不斷增加適當(dāng)?shù)募s束，割掉原可行域不含整數(shù)解的一部分，最終得到一個具有若干整數(shù)頂點的可行域，而這些頂點中恰有一個頂點是原問題的整數(shù)解。割平面法的基本步驟：步驟1不考慮變量的整數(shù)限制，求解相應(yīng)的線性規(guī)劃問題，如果該問題無解，或最優(yōu)解已是整數(shù)解，則停止計算，否則轉(zhuǎn)下一步。步驟2對上述線性規(guī)劃的可行域進(jìn)行“切割”，去掉不含整數(shù)解的一部分可行域，即增加適當(dāng)?shù)木€性約束，然后轉(zhuǎn)步驟1。

整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第4頁!從而fi-ΣfijXj≤0⑸?、墒阶鳛榍懈罘匠?。因為任何整數(shù)可行解都滿足這個方程，所以把它加到原問題的約束中，它能夠?qū)υ尚杏蜻M(jìn)行切割，而不會切割掉整數(shù)解。例3用割平面法求解

maxZ=x1+x2

-x1+x2≤1

3x1+x2≤4x1,x2≥0，整數(shù)

解：將問題標(biāo)準(zhǔn)化得maxZ=x1+x2

⑴

-x1+x2+x3=1⑵3x1+x2+x4=4⑶x1,x2≥0⑷

x1,x2

整數(shù)⑸不考慮條件⑸，求解相應(yīng)線性規(guī)劃，結(jié)果見下表：整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第5頁!C11000CBXBB-1bX1X2X3X4X5110X1X2X53/47/4-310-1/41/40013/41/40

00-3-11

σ

00-1/2-1/20110X1X2X31111001/3-1/1201001/40011/3-1/3σ000-1/3-1/6由于x1，x2的值已是整數(shù)，所以該題經(jīng)一次切割已得最優(yōu)解：x1=1，x2=1，最優(yōu)值：Z※=2

整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第6頁!在求解實際問題中，割平面法經(jīng)常會遇到收斂很慢的情況，但若和其它方法，如分枝定界法，聯(lián)合使用，一般能收到比較好的效果。整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第7頁!例2求解下面整數(shù)規(guī)劃

maxZ=40x1+90x2⑴9x1+7x2≤56⑵7x1+20x2≤70⑶x1,x2≥0⑷x1,x2整數(shù)⑸解：先不考慮條件⑸，求解相應(yīng)的線性規(guī)劃問題L，得最優(yōu)解x1=4.81，x2=1.82，Z0=356（見圖）x2806410x19x1+7x2=567x1+20x2=70Z=40x1+90x2該解不是整數(shù)解。選擇其中一個非整數(shù)變量，如x1=4.81，對問題L分別增加約束條件：x1≤4，x1≥5將問題L分解為兩個子問題L1，L2（分枝），也就是去掉問題L不含整數(shù)解的一部分可行域，將原可行域D變?yōu)镈1、D2兩部分（如圖）。4D1D2求解線性規(guī)劃L1、L2

得最優(yōu)解為：問題L1：L+x1≤4問題L2：L+x1≥5x1=4.00x2=2.10Z1=349x1=5.00x2=1.57Z2=341整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第8頁!整個分枝定界過程如下圖所示：問題LZ0=356x1=4.81x2=1.82問題L1Z1=349x1=4.00，x2=2.10問題L2Z2=341x1=5.00，x2=1.57問題L3Z3=340x1=4.00x2=2.00問題L4Z4=327x1=1.42x2=3.00問題L5Z5=308x1=5.44，x2=1.00問題L6無可行解x1≤4x1≥5x2≤2x2≥3x2≤1x2≥2×××Z※=340整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第9頁!這里貨物的件數(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+4x2≤24因而它不是最優(yōu)解；那么用“舍尾取整”方法處理又如何呢？將x1=4.8，x2=0“舍尾取整”為x1=4，x2=0，顯然滿足各約束條件，因而它是整數(shù)規(guī)劃問題的可行解，但它不是整數(shù)最優(yōu)解。因為它對應(yīng)的目標(biāo)函數(shù)值Z=80，而x1=4，x2=1這個解亦是可行解，但它對應(yīng)的目標(biāo)函數(shù)值Z=90。由此例看出，簡單的處理方法常常得不到整數(shù)規(guī)劃的最優(yōu)解，甚至得不到可行解。如何求得這類問題的整數(shù)最優(yōu)解呢？到目前為止，整數(shù)規(guī)劃還沒有一種很滿意的和有效的解法。現(xiàn)在用以求解整數(shù)規(guī)劃的方法基本都是將整數(shù)規(guī)劃變?yōu)橐幌盗芯€性規(guī)劃來求解的。我們將介紹兩種方法——割平面法和分枝定界法。整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第10頁!割平面法的關(guān)鍵在于如何確定切割方程，使之能對可行域進(jìn)行真正的切割，而且切去部分不含有整數(shù)解點。下面討論切割方程的求法。設(shè)與整數(shù)規(guī)劃相對應(yīng)的線性規(guī)劃最優(yōu)解中基變量XBi=（B-1b)i不是整數(shù)，將最優(yōu)單純形表中該基變量對應(yīng)的行還原成約束方程，即

XBi

+ΣaijXj=（B-1b)i⑴將（B-1b)i，aij都分解成整數(shù)與非負(fù)真分?jǐn)?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⑷

當(dāng)諸Xi都是整數(shù)時，⑷式左端是整數(shù)，所以右端亦應(yīng)是整數(shù)，但右端是兩個正數(shù)之差，且∵0＜fi＜1，∴fi-ΣfijXj是小于1的整數(shù)，從整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第11頁!C1100CBXBB-1bX1X2X3X400

X3X414-11103101σ01100…………………11X1X23/47/410-1/41/4013/41/4σ00-1/2-1/2表中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引入松弛變量x5，得方程-3x3-x4+x5=-3將新約束方程加到原最優(yōu)表下面（切割），求得新的最優(yōu)解如下：整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第12頁!現(xiàn)在我們來看看切割方程3x3+x4≥3的幾何意義。例3對應(yīng)的線性規(guī)劃為maxZ=x1+x2

-x1+x2≤1

3x1+x2≤4x1,x2≥0用圖解法求得可行域D及最優(yōu)解點A，見下圖：x2x111-10-x1+x2=13x1+x2=4A（3/4，7/4）由標(biāo)準(zhǔn)化的約束方程組可得x3=1+x1-x2

x4=4-3x1-x2代入切割方程得3（1+x1-x2）+（4-3x1-x2）≥3即x2≤1，將此切割方程加入原約束中，就等于切掉原可行域得A1B部分，如圖。B（1，1）D顯然在A1B區(qū)域不含整數(shù)解點，對原可行域切割的結(jié)果是產(chǎn)生了一個新頂點B，用圖解法在新的可行域（黃色）中可求得整數(shù)最優(yōu)解恰是B（1，1）。整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第13頁!§3分枝定界法分枝定界法是求解整數(shù)規(guī)劃的常用算法，既可用來解全部變量取值都要求為整數(shù)的純整數(shù)規(guī)劃，又可用以求解混合整數(shù)規(guī)劃。該算法的基本思路是：先不考慮整數(shù)限制，求出相應(yīng)的線性規(guī)劃的最優(yōu)解，若此解不符合整數(shù)要求，則去掉不包含整數(shù)解的部分可行域，將可行域D分成D1、D2兩部分（分枝），然后分別求解這兩部分可行域?qū)?yīng)的線性規(guī)劃，如果它們的解仍不是整數(shù)解，則繼續(xù)去掉不包含整數(shù)解的部分可行域，將可行域D1或D2分成D3與D4兩部分，再求解D3與D4對應(yīng)的線性規(guī)劃，……，在計算中若已得到一個整數(shù)可行解X0，則以該解的目標(biāo)函數(shù)值Z0作為分枝的界限，如果某一線性規(guī)劃的目標(biāo)值Z≤Z0，就沒有必要繼續(xù)分枝，因為分枝（增加約束）的結(jié)果所得的最優(yōu)解只能比Z0更差。反之若Z＞Z0，則該線性規(guī)劃分枝后，有可能產(chǎn)生比Z0更好的整數(shù)解，一旦真的產(chǎn)生了一個更好的整數(shù)解，則以這個更好的整數(shù)解目標(biāo)值作為新的界限，繼續(xù)進(jìn)行分枝，直至產(chǎn)生不出更好的整數(shù)解為止。下面以實例來說明算法的步驟。整數(shù)規(guī)劃割平面法分枝定界法共16頁，您現(xiàn)在瀏覽的是第14頁!因為沒有得到整數(shù)解，所以繼續(xù)對L1進(jìn)行分解，增加約束：

x2≤2，x2≥3將L1分解成問題L3與L4，并求得最優(yōu)解如下：問題L3：L1+x2≤2問題L4：L1+x2≥3x1=4.00，x2=2.00Z3=340x1=1.42，x2=3.00Z4=327問題L3的解已是整數(shù)解，它的目標(biāo)值Z3=340，大于問題L4的目標(biāo)值，所以問題L4已無必要再分枝。但由于問題L2的目標(biāo)值Z2大于Z3，分解L2還有可能產(chǎn)生更好的整數(shù)解，因此繼續(xù)對L2分枝。增加約束

x2≤1，x2≥2將L2分解成問題L5與L6，并求解，結(jié)果如下：問題L5：L2+x2≤1問題L6