第3章整數2割平面法

第

3

章Integer

ProgrammingI

P整數規(guī)劃3.1整數規(guī)劃問題及其建模3.2分支定界法3.3割平面法3.40-1型整數線性規(guī)劃的解法3.5指派問題第3章整數規(guī)劃第3章整數規(guī)劃2以下只討論純整數線性規(guī)劃的情形，下面舉例說明。割平面法是1958年美國學者R.E.Gomory提出的，所以又稱為Gomory的割平面法?；舅枷耄合炔豢紤]變量的取整數約束，求解相應的線性規(guī)劃，然后不斷增加線性約束條件（即割平面），將原可行域割掉不含整數可行解的一部分，最終得到一個具有整數坐標頂點的可行域，而該頂點恰好是原整數規(guī)劃問題的最優(yōu)解。割平面求解舉例MaxZ=x1+x2①-x1+x2≤1②3x1+x2≤4③x1,x2≥0④

x1,x2為整數⑤松弛問題MaxZ=x1+x2-x1+x2≤13x1+x2≤4x1,x2≥0-x1+x2+x3=13x1+x2+x4=4x1,x2≥0例3：如不考慮條件⑤，容易求得相應的線性規(guī)劃的最優(yōu)解：x1=3/4，x2=7/4，maxz=10/4它就是圖5-5中域R的頂點A，但不合于整數條件。現設想，如能找到像CD那樣的直線去切割域R(圖5-6)，

去掉三角形域ACD，那么具有整數坐標的C點(1，1)就是域R′的一個極點，如在域R′上求解①～④，而得到的最優(yōu)解又恰巧在C點,

就得到原問題的整數解，所以解法的關鍵:

就是怎樣構造一個這樣的

“割平面”CD，

它就是一個新的約束。

盡管它可能不是唯一的，也可能不是一步能求到的。下面給出本例完整的求解過程：

在原問題的前兩個不等式中增加非負松弛變量x3、x4，使兩式變成等式約束：-x1+x2+x3=1⑥3x1+x2+x4=4⑦不考慮條件⑤，用單純形表解題，見表5-2。解松弛問題的最優(yōu)單純形表為：CBXBb1100x1x2x3x40x31-11100x443101σ1100…………………1x13/410-1/41/41x27/4013/41/4Z=5/2σ00-1/2-1/2從表5-2的最終計算表中，得到非整數的最優(yōu)解：x1=3/4，x2=7/4，x3=x4=0，maxz=5/2可從最終計算表中得到非整數基變量對應的關系式：不能滿足整數最優(yōu)解的要求。

為此考慮將帶有分數的最優(yōu)解的可行域中分數部分割去，再求最優(yōu)解。就可以得到整數的最優(yōu)解。為了得到整數最優(yōu)解。將上式變量的系數和常數項都分解成整數和”非負”真分數兩部分之和(1+0)x1+(-1+3/4)x3+1/4x4=0+3/4x2+(3/4)x3+(1/4)x4=1+3/4然后將整數部分與分數部分分開，移到等式左右兩邊，得到：現考慮整數條件⑤要求x1、x2都是非負整數，于是由條件⑥、⑦可知,-x1+x2+x3=1⑥3x1+x2+x4=4⑦

x3、x4也都是非負整數,

這一點對以下推導是必要的，如不都是整數，則應在引入x3、x4之前乘以適當調整系數和常數，使之都是整數。在上式中(其實只考慮一式即可)從等式左邊看是整數；等式右邊也應是整數。但在等式右邊的(·)內是正數；所以等式右邊必是非正整數。就是說，右邊的整數值最大是零。于是整數條件⑤可由下式所代替；

即-3x3-x4≤-3⑧這就得到一個切割方程(或稱為切割約束)，將它作為增加約束條件，再解例3。引入松弛變量x5，得到等式-3x3-x4+x5=-3將這新的約束方程加到表5-2的最終計算表，得表5-3。

表5-3從表5-3的b列中可看到，這時得到的是非可行解，于是需要用對偶單純形法繼續(xù)進行計算選擇x5為換出變量，計算將x3做為換入變量，再按原單純形法進行迭代，得表5-4。x1、x2的值已都是整數，解題已完成。

幾何解釋：新得到的約束條件⑧-3x3-x4≤-3

如用x1、x2表示，由⑥、⑦式得3(1+x1-x2)+(4-3x1-x2)≥3x2≤1則是(x1，x2)平面內形成新的可行域，即包括平行于x1軸的直線x2=1

和這直線下的可行區(qū)域，整數點也在其中，沒有切割掉。直觀地表示在圖5-7中。但從解題過程來看，這一步是不必要的。割平面法的計算步驟：1、用單純形法求解(整數規(guī)劃IP)對應的松弛問題(線性規(guī)劃LP)：⑴.若(LP)沒有可行解，則(IP)也沒有可行解，停止計算。⑵.若(LP)有最優(yōu)解，并符合(IP)的整數條件，則(LP)的最優(yōu)解即為(IP)的最優(yōu)解，停止計算。⑶.若(LP)有最優(yōu)解，但不符合(IP)的整數條件，轉入下一步。

2、從(LP)的最優(yōu)解中，任選一個不為整數的分量xr,,

將最優(yōu)單純形表中該行的系數arj′和br′分解為

整數部分和非負真分數部分之和，并以該行為源行，按下式作割平面方程：的非負真分數部分的非負真分數部分

3、將所得的割平面方程作為一個新的約束條件置于最優(yōu)單純形表中（同時增加一個單位列向量），用對偶單純形法求出新的最優(yōu)解，返回1。例：用割平面法求下面整數規(guī)劃問題第一步：把問題中所有約束條件的系數均化為整數.G0：第二步：因為x3，x40x1x2×××××××××O×第三步：將Gomory約束加到G0中得到新的線性規(guī)劃問題G1如下：G1：第四步：重復第一至第三步一直到找出問題的整數最優(yōu)解為止.G1：G