第三节割平面法

割平面法是1958年由R.E.Gomory提出来的，因此又称为Gomory的割平面法。其基本思路是，先不考虑变量是整数的约束条件，解整数规划相应的松驰问题，所得的最优解如不符合整数条件，再增加新线性约束条件(其几何术语称为割平面)，使得从原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。割平面法就是指出怎样找到适当的割平面(不见得一次就找到)，使切割后最终得到的可行域中的一个整数坐标的极点，它恰好是问题的最优解。由此可见，割平面法的基础仍然是用解线性规划的方法去求解整数规划问题。

割平面法在求解纯整数规划问题的基本步骤：

(1)解松驰问题。先不考虑整数条件，求解整数规划(IP)对应的松弛问题(LP)，可能得到以下情况之一：

①若(LP)没有可行解，则(IP)也没有可行解，停止计算。

②若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。

③若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。

(2)求切割方程。按以下方法求切割方程：

令为松驰问题(LP)最优解中分为数值的一个基变量，由最优单纯形表可得

                                        (3-3)

。

将和都分解成整数部分N和非负真分数f之和，即：

           (3-4)

将(3-3)代入(3-4)可得

                        (3-5)

当变量约束为整数时，(3-5)式左边看必须是整数，但右边因为有，所以不能为正，即

                                        (3-6)

(3-6)就是一个切割约束，引入松驰变量，得切割方程如下：

(3)解新的松驰问题。在原来松驰问题(LP)约束条件的基础上增加一个切割约束，构成新的线性规划问题(LP1)，再求出(LP1)的最优解。再返回到步骤(2)。

(4)重复以上步骤，直到求得最优解或判断原问题无可行解为止。

现举例说明割平面法在求解纯整数规划问题中的应用。

【例3.2】用割平面法求解下列整数规划。

解：用单纯形法求解该整数规划对应的松弛问题(LP)，得其最优单纯形表3-1。

表3-1 最优单纯形表

其中，，为松驰变量。(LP)的最优解为，显然不符合整数条件。

从最优单纯形表中两个约束条件中提出一个如下：

将上式中系数和常数项分解成整数和非负真分数之和，得以下式子：

移项使整数部分在等号的左边，小数部分在等号的右边得：

当，都取非负整数时，由于上式的左边取整数，与之相等的右边也只能取整数，而右边不可能取得正整数，所以只能取负整数，即有不等式：

即：

引入松驰变量，得割平面方程：

                  (3-7)

将上式作为一个新的约束条件，增加到(LP)，构成(LP1)。按如下方法求解(LP1)：将(3-7)式添加在(LP)的最优单纯形表中，得到表3-2。

表3-2 割平面法计算过程

表3-2中，检验数全部非负，但b列数存在负分量，用对偶单纯形法继续迭代，得最优单纯形表3-3。

表3-3割平面法计算过程

最优解为，不符合整数条件，需要再求一次切割方程。

从表3-3中提出第二个约束条件：

按照前述方法，求得切割约束为：

引入松驰变量，得割平面方程：                   (3-8)

将(3-8)式添加在(LP1)的最优单纯形表3-3中，得到表3-4。

表3-4割平面法计算过程

用对偶单纯形法继续迭代，得最优单纯形表3-5。

表3-5割平面法计算过程

最优解为，符合整数条件，对应的目标函数。

所以原问题的最优解，对应的目标函数。