§3.2 G o m o r y 割平面法1、G o m o r y 割平面法的基本思想⎪⎪⎩⎪⎪⎨⎧≥=为整数向量x x bAx t s xc T 0..min （P ） ⎪⎩⎪⎨⎧≥=0..min x b Ax t s x c T （P 0）称（P 0）为（P ）的松弛问题。
记（P ）和（P 0）的可行区域分别为D 和D 0 , 则（1）0D D ⊂；（2）若（P 0）无可行解，则（P ）无可行解； （3）（P 0）的最优值是（P ）的最优值的一个下界；（4）若（P 0）的最优解 0x 是整数向量，则 0x 是（P ）的最优解。
基本思想：（1）用单纯形法求解松弛问题（P 0），若（P 0）的最优解 0x 是整数向量，则 0x 是（P ）的最优解。
计算结束。
(2) 若（P 0）的最优解 0x 不是整数向量，则对松弛问题（P 0）增加一个线性约束条件（称它为割平面条件）， 新增加的约束条件将（P 0）的行区域D 0割掉一块，且这个非整数向量 0x 恰在被割掉的区域内，而原问题（P ）的任何一个可行解（格点）都没有被割去。
记增加了割平面的问题为（P 1）， 称（P 1）为（P 0）的改进的松弛问题。
（3）用对偶单纯形法求解（P 1），若（P 1）的最优解 1x 是整数向量，则 1x是（P ）的最优解。
计算结束。
否则转（2）割平面的生成：对给定的（P ）， 用单纯形法求解它的松弛问题（P 0），得到（P 0）的最优基本可行解 0x ，设它对应的基为 ),,(1m B B A A B Λ=， m B B x x ,,1Λ为 0x 的基变量，记基变量的下标集合为 S ，非基变量的下标集合为 S 。
则松弛问题（P 0）的最优单纯形表为∑∈=+Sj j j z x z 0ξm i b x a x Sj i j ij B i ,,1,Λ==+∑∈ （3.2.1）为了使符号简便，令000,,0z b a z x j j B ===ξ。
如果m i b i ,,1,0,Λ= 全是整数，则 0x 是（P ）的最优解。
计算结束。
否则至少有一个 l b 不是整数)0(m l ≤≤，设 l b 所对应的约束方程为,∑∈=+Sj l j lj B b x a x l （3.2.2）用 ][a 表示不超过实数 a 的最大整数，则,][,,][l l l lj lj lj f b b S j f a a +=∈+= （3.2.3）其中，lj f 是 lj a 的分数部分，有 S j f lj ∈<≤,10， l f 是 l b 的分数部分，有 .10<≤l f由于在（3.2.2）中的变量是非负的，因此有∑∑∈∈≤Sj j ljSj jljxa x a ][ （3.2.4）所以由（3.2.2）得,][∑∈≤+Sj l j lj B b x a x l （3.2.5）因为在ILP 中 x 限制为整数向量，故（3.2.5）的左端为整数，所以右端用 l b 的整数部分去代替后，（3.2.5）式的不等式关系仍成立，即],[][∑∈≤+Sj l j lj B b x a x l （3.2.6）用（3.2.2） 减（3.2.6）得]),[(])[(∑∈-≥-Sj l l j lj ljb b x a a（3.2.7）由（3.2.2），可得线性约束,∑∈≥Sj l j ljf x f（3.2.8）称它为对应于生成行 l 的 Gomory 割平面条件。
为了将（3.2.8）加到松弛问题（P 0）的最优单纯形表，应将它变为等式，所以引入一个剩余变量 s ，从而 （3.2.8）变为,∑∈=-S j l j ljf s x f在两端同乘以 （-1），得,∑∈-=+-Sj l j lj f s x f （3.2.9）（3.2.9）是一个超平面，称它为割平面。
把割平面（3.2.9）加到松弛问题（P 0）的最优单纯形表的最后一行，可得改进的松弛问题（P 1）的单纯形表∑∈=+Sj j j z x z 0ξm i b x a x Sj i jij B i ,,1,Λ==+∑∈,∑∈-=+-Sj l j lj f s x f（P 1）的变量个数为 1+n ，等式约束为 1+m ，它的基变量个数为 1+m 。
显然，s x x m B B ,,,1Λ是（P 1）的基变量。
所以，对（P 1），获得了一个基本解，并且它的检验数向量 0)0,,,(1≤=T n ξξξΛ。
所以可用对偶单纯形方法求解改进的松弛问题（P 1）。
定理 3.2.1 如果把割平面（3.2.9）加到松弛问题（P 0）的最优单纯形表里，那么没有割掉原ILP 的任何整数可行点，当 l b 不是整数时，新表里是一个原始基本不可行解和对偶可行解。
证：ILP 的任何整数可行点都一定满足（3.2.2）和（3.2.6），所以满足（3.2.8）和（3.2.9），因此不会被割平面（3.2.9）割掉。
注：松弛问题（P 0）的非整数最优解 0x 被割平面（3.2.9）割掉了。
因为S j x b x j l B l∈==,0,0所以，,00∑∈<=Sj l j lj f x f所以 0x 不满足（3.2.8），即不满足（3.2.9）。
2、G o m o r y 割平面的计算步骤第1步 用单纯形法求解（P ）的松弛问题（P 0）。
若（P 0）没有最优解，则停止计算，（P ）也没有最优解； 若（P 0）的最优解 0x 是整数向量，则 0x 是（P ）的最优解。
计算结束。
否则，转第2步。
第2步 求割平面任选 0x 的一个非整数分量 )0(m l b l ≤≤，由 l b 所在的这一行,∑∈=+Sj l j lj B b x a x l得到Gomory 割平面条件 ,∑∈≥S j l j ljf x f再得到割平面,∑∈-=+-Sj l j lj f s x f （3.2.10）第3步 将割平面（3.2.10）加到第1步所得的最优单纯形表里，用对偶单纯形方法求解这个改进的松弛问题。
若其最优解是整数向量，则它是原问题（P ）的最优解，计算结束。
否则，将这个最优解重新记为 0x ，返回第2步。
例3.2.1 求解 ILP 问题⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+=整数,0,023623..max 2121212x x x x x x t s x z （3.2.11）解：先将（3.2.11）化为标准形式⎪⎪⎩⎪⎪⎨⎧≥=++-=++-=整数,0,,,023623..min 43214213212x x x x x x x x x x t s x z （P ）它对应的松弛问题（P 0）为⎪⎪⎩⎪⎪⎨⎧≥=++-=++-=0,,,023623..min 43214213212x x x x x x x x x x t s x z （P 0）显然，T x )0,6,0,0(=是（P 0）的初始解，其基变量是 3x 和4x 。
所以（P 0）的第一张单纯形表为1x 2x 3x 4xRHS z0 1 0 0 0 3x 3 2 1 0 6 4x-3211x 2x 3x4x RHS z3/2 0 0 -1/2 0 3x 61 -1 6 2x-3/2 11/2 0（3.2.13）所以，松弛问题（P 0）的最优解为 T x )0,0,23,1(0=，因0x 不是整数向量，所以生成割平面（第0行和第2行均可生成割平面）。
由第2行生成的割平面条件为21414143≥+x x相应的割平面为214141143-=+--s x x （3.2.16）把（3.2.16）加到松弛问题（P 0）的最优单纯形表（3.2.13）中，得到改进的松弛问题（P 1）的单纯形表用对偶单纯形算法求解1x 2x 3x 4x RHS z 0 0 -1/4 -1/4 -3/2 1x 1 0 1/6 -1/6 1 2x 0 1 1/4 1/4 3/2 1x 2x 3x 4x 1s RHS z 0 0 -1/4 -1/4 0 -3/2 1x 1 0 1/6 -1/6 0 1 2x 0 1 1/4 1/4 0 3/2 1s 0 0 -1/4 -1/4 1 -1/2 1x 2x 3x 4x 1s RHS z 0 0 -1/4 -1/4 0 -3/2 1x 1 0 1/6 -1/6 0 1 2x 0 1 1/4 1/4 0 3/2 1s 0 0 -1/4 -1/4 1 -1/2（3.2.17）所以，改进的松弛问题（P 1）的最优解为 T x )2,0,0,1,32(1=，由于0x 不是整数向量，所以生成割平面。
由第1行生成的割平面条件为32323214≥+s x相应的割平面为323232214-=+--s s x （3.2.18）把（3.2.18）加到改进的松弛问题（P 1）的最优单纯形表（3.2.17）中，得到新的松弛问题（P 2）的单纯形表用对偶单纯形算法求解1x 2x 3x4x 1s RHS z0 0 0 0 -1 -1 1x 1 0 0 -1/3 2/3 2/3 2x 0 1 0 0 1 1 3x11 -42 1x 2x 3x 4x 1s 2s RHS z 0 0 0 0 -1 0 -1 1x 1 0 0 -1/3 2/3 0 2/3 2x 0 1 0 0 1 0 1 3x 0 0 1 1 -4 0 2 2s 0 0 0 -2/3 -2/3 1 -2/3所以，松弛问题（P 2）的最优解为 T x )0,0,1,1,1,1(2=。
所以，原问题的最优解为 T x )1,1(*=。
注： 原问题（P ）的松驰问题（P 0）的可行区域是如图的三角形 OAB ∆区域，（P ）的可行区域是OAB ∆中的四个格点：（0，0），（1，0），（2，0），（1，1）。
割平面条件21414143≥+x x 等价为 12≤x割平面条件32323214≥+s x 等价为 12x x ≤1x 2x 3x 4x 1s 2sRHS z0 0 0 0 -1-1 1x 1 0 0 0 1 -1/2 1 2x 0 1 0 0 11 3x0 1 0 -5 3/2 1 2s 011 -3/21。