第3章整數(shù)2割平面法

第

3

章Integer

ProgrammingI

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

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

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

就得到原問題的整數(shù)解，所以解法的關(guān)鍵:

就是怎樣構(gòu)造一個(gè)這樣的

“割平面”CD，

它就是一個(gè)新的約束。

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

在原問題的前兩個(gè)不等式中增加非負(fù)松弛變量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的最終計(jì)算表中，得到非整數(shù)的最優(yōu)解：x1=3/4，x2=7/4，x3=x4=0，maxz=5/2可從最終計(jì)算表中得到非整數(shù)基變量對應(yīng)的關(guān)系式：不能滿足整數(shù)最優(yōu)解的要求。

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

x3、x4也都是非負(fù)整數(shù),

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

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

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

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

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

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

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

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

整數(shù)部分和非負(fù)真分?jǐn)?shù)部分之和，并以該行為源行，按下式作割平面方程：的非負(fù)真分?jǐn)?shù)部分的非負(fù)真分?jǐn)?shù)部分

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