文档介绍：§ Gomory 割平面法
1、Gomory 割平面法的基本思想
(P) (P0)
称(P0)为(P)的松弛问题。记(P)和(P0)的可行区域分别为D和D0 , 则
(1);
(2)若(P0)无可行解,则(P)无可行解;
(3)(P0)的最优值是(P)的最优值的一个下界;
(4)若(P0)的最优解是整数向量,则是(P)的最优解。
基本思想:
(1)用单纯形法求解松弛问题(P0),若(P0)的最优解是整数向量,则是(P)的最优解。计算结束。
(2) 若(P0)的最优解不是整数向量,则对松弛问题(P0)增加一个线性约束条件(称它为割平面条件), 新增加的约束条件将(P0)的行区域D0割掉一块,且这个非整数向量恰在被割掉的区域内,而原问题(P)的任何一个可行解(格点)都没有被割去。记增加了割平面的问题为(P1), 称(P1)为(P0)的改进的松弛问题。
(3)用对偶单纯形法求解(P1),若(P1)的最优解是整数向量,则是(P)的最优解。计算结束。否则转(2)
(P)
x0
。。
。。
费用减少的方向
(P0)
x1
。。
。。
费用减少的方向
(P1)
。。
。。
割平面的生成:
对给定的(P), 用单纯形法求解它的松弛问题(P0),得到(P0)的最优基本可行解,设它对应的基为, 为的基变量,记基变量的下标集合为,非基变量的下标集合为。则松弛问题(P0)的最优单纯形表为

()
为了使符号简便,令。如果全是整数,则是(P)的最优解。计算结束。否则至少有一个不是整数,设所对应的约束方程为
()
用表示不超过实数的最大整数,则
()
其中, 是的分数部分,有, 是的分数部分,有
由于在()中的变量是非负的,因此有
()
所以由()得
()
因为在ILP中限制为整数向量,故()的左端为整数,所以右端用的整数部分去代替后,()式的不等式关系仍成立,即
()
用() 减()得
()
由(),可得线性约束
()
称它为对应于生成行的 Gomory 割平面条件。
为了将()加到松弛问题(P0)的最优单纯形表,应将它变为等式,所以引入一个剩余变量,从而()变为

在两端同乘以(-1),得
()
()是一个超平面,称它为割平面。
把割平面()加到松弛问题(P0)的最优单纯形表的最后一行,可得改进的松弛问题(P1)的单纯形表

(P1)的变量个数为,等式约束为,它的基变量个数为。显然,是(P1)的基变量。所以,对(P1),获得了一个基本解,并且它的检验数向量。所以可用对偶单纯形方法求解改进的松弛问题(P1)。
定理如果把割平面()加到松弛问题(P0)的最优单纯形表里,那么没有割掉原ILP的任何整数可行点,当不是整数时,新表里是一个原始基本不可行解和对偶可行解。
证:ILP的任何整数可行点都一定满足()和(),所以满足()和(),因此不会被割平面(.