割平面法：什么意思、基本思想、求解步骤

割平面法：什么意思、基本思想、求解步骤

割平面法的基础仍然是用线性规划的求解方法去解整数规划问题。首先不考虑变量为整数这一约束条件，但增加线性约束条件（用几何术语，称为割平面）使得从原可行解域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。

因此，采用割平面法的关键是如何找到割平面约束方程，使切割后最终得到这样的可行解域，它的一个有整数坐标的极点恰好就是问题的最优解。这个方法是由美国学者高莫瑞（R.E.Gomory）于1958年提出来的，所以又称为Gomory割平面法。

求解步骤

（1）去掉整数约束，用单纯形法求解。若最优解是整数，停止计算，否则转下一步。

（2）寻求附加约束（割平面方程）。

① 从最优表中抄下非整数解的某个约束方程；

② 将该约束方程的所有系数和常数分解为整数和正真分数之和；

③ 整数项（包括整系数项和整常数项）归写于方程左边，真分数项写于右边；

④ 利用整数约束条件求出割平面方程。

（3）将割平面方程标准规范化后加到约束方程组中求解，如所求得的最优解仍为非整数，则转到第（2）步继续进行，直到找到最优整数解为止。