第3章整数2割平面法

第

3

章Integer

ProgrammingI

P整数规划3.1整数规划问题及其建模3.2分支定界法3.3割平面法3.40-1型整数线性规划的解法3.5指派问题第3章整数规划第3章整数规划2以下只讨论纯整数线性规划的情形，下面举例说明。割平面法是1958年美国学者R.E.Gomory提出的，所以又称为Gomory的割平面法。基本思想：先不考虑变量的取整数约束，求解相应的线性规划，然后不断增加线性约束条件（即割平面），将原可行域割掉不含整数可行解的一部分，最终得到一个具有整数坐标顶点的可行域，而该顶点恰好是原整数规划问题的最优解。割平面求解举例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：如不考虑条件⑤，容易求得相应的线性规划的最优解：x1=3/4，x2=7/4，maxz=10/4它就是图5-5中域R的顶点A，但不合于整数条件。现设想，如能找到像CD那样的直线去切割域R(图5-6)，

去掉三角形域ACD，那么具有整数坐标的C点(1，1)就是域R′的一个极点，如在域R′上求解①～④，而得到的最优解又恰巧在C点,

就得到原问题的整数解，所以解法的关键:

就是怎样构造一个这样的

“割平面”CD，

它就是一个新的约束。

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

在原问题的前两个不等式中增加非负松弛变量x3、x4，使两式变成等式约束：-x1+x2+x3=1⑥3x1+x2+x4=4⑦不考虑条件⑤，用单纯形表解题，见表5-2。解松弛问题的最优单纯形表为：CBXBb1100x1x2x3x40x31-11100x443101σ1100…………………1x13/410-1/41/41x27/4013/41/4Z=5/2σ00-1/2-1/2从表5-2的最终计算表中，得到非整数的最优解：x1=3/4，x2=7/4，x3=x4=0，maxz=5/2可从最终计算表中得到非整数基变量对应的关系式：不能满足整数最优解的要求。

为此考虑将带有分数的最优解的可行域中分数部分割去，再求最优解。就可以得到整数的最优解。为了得到整数最优解。将上式变量的系数和常数项都分解成整数和”非负”真分数两部分之和(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列中可看到，这时得到的是非可行解，于是需要用对偶单纯形法继续进行计算选择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

和这直线下的可行区域，整数点也在其中，没有切割掉。直观地表示在图5-7中。但从解题过程来看，这一步是不必要的。割平面法的计算步骤：1、用单纯形法求解(整数规划IP)对应的松弛问题(线性规划LP)：⑴.若(LP)没有可行解，则(IP)也没有可行解，停止计算。⑵.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。⑶.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。

2、从(LP)的最优解中，任选一个不为整数的分量xr,,

将最优单纯形表中该行的系数arj′和br′分解为

整数部分和非负真分数部分之和，并以该行为源行，按下式作割平面方程：的非负真分数部分的非负真分数部分

3、将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回1。例：用割平面法求下面整数规划问题第一步：把问题中所有约束条件的系数均化为整数.G0：第二步：因为x3，x40x1x2×××××××××O×第三步：将Gomory约束加到G0中得到新的线性规划问题G1如下：G1：第四步：重复第一至第三步一直到找出问题的整数最优解为止.G1：G