割平面法課件

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

2.割平面法的關(guān)鍵在于如何確定切割方程，使之能對可行域進(jìn)行真正的切割，而且切去部分不含有整數(shù)解點(diǎn)。下面討論切割方程的求法。設(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ù)，從3.從而fi-ΣfijXj≤0⑸?、墒阶鳛榍懈罘匠?。因?yàn)槿魏握麛?shù)可行解都滿足這個方程，所以把它加到原問題的約束中，它能夠?qū)υ尚杏蜻M(jìn)行切割，而不會切割掉整數(shù)解。例3用割平面法求解

maxZ=x1+x2

-x1+x2≤13x1+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é)果見下表：4.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因?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引入松弛變量x5，得方程-3x3-x4+x5=-3將新約束方程加到原最優(yōu)表下面（切割），求得新的最優(yōu)解如下：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

6.現(xiàn)在我們來看看切割方程3x3+x4≥3的幾何意義。例3對應(yīng)的線性規(guī)劃為maxZ=x1+x2

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