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

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

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

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

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

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

6、對(duì)應(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í)， 式左端是整數(shù)，所以右端亦應(yīng)是整數(shù)，但右端是兩個(gè)正數(shù)之差，且0 fi 1， fi-fijXj是小于1的整數(shù)，從,從而 fi-fijXj0 取式作為切割方程。因?yàn)槿魏握麛?shù)可行解都滿(mǎn)足這個(gè)方程，所以把它加到原問(wèn)題的約束中，它能夠

7、對(duì)原可行域進(jìn)行切割，而不會(huì)切割掉整數(shù)解,例3 用割平面法求解 maxZ=x1+x2 -x1+x21 3x1+x24 x1,x20，整數(shù),解：將問(wèn)題標(biāo)準(zhǔn)化得 maxZ=x1+x2 -x1+x2+x3 =1 3x1+x2+x4=4 x1,x20 x1,x2 整數(shù),不考慮條件，求解相應(yīng)線性規(guī)劃，結(jié)果見(jiàn)下表,表中x1=3/4，不是整數(shù)，將表中第一行還原成方程，即 x1-1/4x3+1/4x4=3/4 因?yàn)?/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)在我們來(lái)看看切割方程 3x3+x4 3 的幾何意義。 例3對(duì)應(yīng)的線性規(guī)劃為 maxZ=x1+x2 -x1+x21 3x1+x24 x1,x20,用圖解法求得可行域D及最優(yōu)解點(diǎn)A，見(jiàn)下圖,x2,x1,1,1,1,0,x1+x2=1,3x1+x2=4,A（3/4，7/4,由標(biāo)準(zhǔn)化的約束方程組可得 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ù)解點(diǎn)，對(duì)原可行域切割的結(jié)果是產(chǎn)生了一個(gè)新頂點(diǎn)B，用圖解法在新的可行域（黃色）中可求得整數(shù)最優(yōu)解恰是B（1，1,在求解實(shí)際問(wèn)題中，割平面法經(jīng)常會(huì)遇到收斂很慢的情況，但若和其它方法，如分枝定界法，聯(lián)合使用，一般能收到比較好的效果,3 分枝定界法,分枝定界法是求解整數(shù)規(guī)劃的常用算法，既可用來(lái)解全部變量取值都要求為整數(shù)的純整數(shù)規(guī)劃，又可用以求解混合整數(shù)規(guī)劃。 該算法的基本思路是：先不考慮整數(shù)限制，求出相應(yīng)的線性規(guī)劃的最優(yōu)解，若此解不符合整數(shù)要求，則去掉不包含整數(shù)解的部分可行域，將

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

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

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

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