第章整數(shù)規(guī)劃(割平面法)

1、割平面法求解整數(shù)規(guī)劃問題：Max Z=3xi+2x22xi+3x2 蘭 144xi+2x2 蘭 18xi,x 0，且為整數(shù)解：首先，將原問題的數(shù)學(xué)模型標(biāo)準(zhǔn)化，這 里標(biāo)準(zhǔn)化有兩層含義：（1 ）將不等式轉(zhuǎn)化為 等式約束，（2）將整數(shù)規(guī)劃中所有非整數(shù)系 數(shù)全部轉(zhuǎn)化為整數(shù)，以便于構(gòu)造切割平面。 從而有：Max Z=3x1+2x22x1+3x2+x3=142x1+x2+x4=9x1,x- 0，且為整數(shù)利用單純形法求解，得到最優(yōu)單純形表，見 表1 :Xbb320Cb0XiX2X3X42XS2011/2-1/23Xi13/410-1/43/4j59/4001/45/4最優(yōu)解為：Xi=l34, X2=52,

2、Z=59/4根據(jù)上表，寫出非整數(shù)規(guī)劃的約束方程，如:X2+1/2x3-1/2x4=2(1)將該方程中所有變量的系數(shù)及右端常數(shù)項(xiàng) 均改寫成“整數(shù)與非負(fù)真分?jǐn)?shù)之和” 的形式, 即：(1+0)X2+(0+1/2)X3+(-1+1Z2)X4=2+1/2把整數(shù)及帶有整數(shù)系數(shù)的變量移到方程左 邊，分?jǐn)?shù)及帶有分?jǐn)?shù)系數(shù)的變量稱到方程右邊，得:X2 - X4-2 =1/2-(172x3+1/2x4)(2)由于原數(shù)學(xué)模型已經(jīng)“標(biāo)準(zhǔn)化”，因此，在 整數(shù)最優(yōu)解中，x2和x4也必須取整數(shù)值，所 以(2)式左端必為整數(shù)或零，因而其右端也必 須是整數(shù)。又因?yàn)閄3,X- 0，所以必有：1/2-(1/2x3+1/2x4)1由于

3、(2)式右端必為整數(shù)，于是有：1/2-(1/2x3+172x4尸 0(3)或x3+x-1(4)這就是考慮整數(shù)約束的一個(gè)割平面約束方 程，它是用非基變量表示的，如果用基變量 來表示割平面約束方程，則有：2x1+2x211(5)從圖1中可以看出，式所表示的割平面約 束僅割去線性規(guī)劃可行域中不包含整數(shù)可行解的部分區(qū)域，使點(diǎn)E(3.5, 2)成為可行域 的一個(gè)極點(diǎn)。圖1在(3)式中加入松弛變量X5,得：-1/2x3-1/2x4+X5=-1/2(6)得到新的將(6)式增添到問題的約束條件中， 整數(shù)規(guī)劃問題：Max Z=3xi+2x2 2xi+3x2+x3=14 2xi+x2+x4=9 -1/2x3-1/

4、2x4+x5=-1/2Xi-0,且為整數(shù)，i=1,2,5該問題的求解可以在表 1中加入式,然后 運(yùn)用對(duì)偶單純形法求出最優(yōu)解。具體計(jì)算過 程見表2：表2CbXbb32000X1X2X3X4X52X2/2011/21/203Xi13/4101/4$400X51/2001/21/21j59/4001/4S402X22010113Xi7/210011/20X3100112J58/400011/2由此得最優(yōu)解為：x1=72, X2=2, z=584該最優(yōu)解仍不滿足整數(shù)約束條件，因而需進(jìn) 行第二次切割。為此，從表 2中抄下非整數(shù) 解xi的約束方程為：xi+X4-1/2x5 = 72按整數(shù)、分?jǐn)?shù)歸并原則寫成

5、：Xi+X4-X5-3 = 12-1/2X5- 0這就是一個(gè)新的割平面方程，用基變量來表 示，得：xi+x 5(8)在(7)中加入松弛變量 冷，得：-1/2x5+x6=-1/2(9)將(9)式增添到前一個(gè)問題的約束條件中去， 得到又一個(gè)新的整數(shù)規(guī)劃問題，對(duì)它求解可以在表2中加入式，然后運(yùn)用對(duì)偶單純形 法求出最優(yōu)解。具體計(jì)算過程見表3：表3CbXbb320000X1X2X3X4X5X62X22010-1103Xi7/21001-1/200X510011-200X6-1/20000-1/21j58/400011/202X21010-1023Xi410010-10X3300110-40X5100001-2CT .J14000101由此得最優(yōu)解為：Xi=4, X2=1,z=14。該最優(yōu)解 符合整數(shù)條件，因此也是原整數(shù)規(guī)劃問題的 最優(yōu)解。從圖1中可以看出，由(8