§3.2 Gomory 割平面法

§3.2 Gomory 割平面法

§3.2 Gomory 割平面法

1、Gomory 割平面法的基本思想

?mincTx?mincTx???s.t.Ax?b ? （P） ?s.t.Ax?b （P0）

x?0??x?0??x为整数向量?称（P0）为（P）的松弛问题。记（P）和（P0）的可行区域分别为D和D0 , 则

（1）D?D0；

（2）若（P0）无可行解，则（P）无可行解； （3）（P0）的最优值是（P）的最优值的一个下界；

（4）若（P0）的最优解 x0 是整数向量，则 x0 是（P）的最优解。 基本思想：

（1）用单纯形法求解松弛问题（P0），若（P0）的最优解 x0 是整数向量，

则 x0 是（P）的最优解。计算结束。

(2) 若（P0）的最优解 x0 不是整数向量，则对松弛问题（P0）增加一个

线性约束条件（称它为割平面条件）， 新增加的约束条件将（P0）的行区域D0割掉一块，且这个非整数向量 x0 恰在被割掉的区域内，而原问题（P）的任何一个可行解（格点）都没有被割去。记增加了割平面的问题为（P1）， 称（P1）为（P0）的改进的松弛问题。

（3）用对偶单纯形法求解（P1），若（P1）的最优解 x1 是整数向量，则 x1

是（P）的最优解。计算结束。否则转（2）

x0 费用减少的方向 费用减少的方向 。 。 。 。 (P) 。 。 。 。 x1 1

。 。 。 。 (P1)

(P0) §3.2 Gomory 割平面法

割平面的生成：

对给定的（P）， 用单纯形法求解它的松弛问题（P0），得到（P0）的最优基

本可行解 x0，设它对应的基为 B?(AB1,?,ABm)， xB1,?,xBm为 x0的基变量，记基变量的下标集合为 S，非基变量的下标集合为 S。则松弛问题（P0）的最优单纯形表为

z???jxj?z0

j?SxBi??aijxj?bi,i?1,?,m （3.2.1）

j?S为了使符号简便，令

xB0?z,a0j??j,b0?z0。如果

bi,i?0,1,?,m 全

是整数，则 x0 是（P）的最优解。计算结束。否则至少有一个 bl 不是整数

(0?l?m)，设 bl 所对应的约束方程为

xBl??aljxj?bl,j?S （3.2.2）

用 [a] 表示不超过实数 a 的最大整数，则

alj?[alj]?flj,j?S,bl?[bl]?fl, （3.2.3）

j?S， fl 是 bl 的分数部分，

其中，flj 是 alj的分数部分，有 0?flj?1,有 0?fl?1.

由于在（3.2.2）中的变量是非负的，因此有

?[a]x??axljjljj?Sj?Sj?Sj （3.2.4）

所以由（3.2.2）得

xBl??[alj]xj?bl, （3.2.5）

因为在ILP中 x 限制为整数向量，故（3.2.5）的左端为整数，所以右端用 bl 的整数部分去代替后，（3.2.5）式的不等式关系仍成立，即

2

§3.2 Gomory 割平面法

xBl??[alj]xj?[bl],j?S （3.2.6）

用（3.2.2） 减（3.2.6）得

?(aj?Slj?[alj])xj?(bl?[bl]),xj?fl,（3.2.7）

由（3.2.2），可得线性约束

?fj?Slj （3.2.8）

称它为对应于生成行 l 的 Gomory 割平面条件。

为了将（3.2.8）加到松弛问题（P0）的最优单纯形表，应将它变为等式，所以引入一个剩余变量 s，从而 （3.2.8）变为

?fj?Sj?Sljxj?s?fl,

在两端同乘以 （-1），得

??fljxj?s??fl, （3.2.9）

（3.2.9）是一个超平面，称它为割平面。

把割平面（3.2.9）加到松弛问题（P0）的最优单纯形表的最后一行，可得改进的松弛问题（P1）的单纯形表

z???jxj?z0

j?SxBi??aijxjj?S?bi,i?1,?,m

??fljxj?s??fl,j?S（P1）的变量个数为 n?1，等式约束为 m?1，它的基变量个数为 m?1。显然，xB1,?,xBm,s是（P1）的基变量。所以，对（P1），获得了一个基本解，并且它的检验数向量 ??(?1,?,?n,0)T?0。所以可用对偶单纯形方法求解改进的松弛问题（P1）。

3

§3.2 Gomory 割平面法

定理 3.2.1 如果把割平面（3.2.9）加到松弛问题（P0）的最优单纯形表里，那么没有割掉原ILP的任何整数可行点，当 bl 不是整数时，新表里是一个原始基本不可行解和对偶可行解。

证：ILP的任何整数可行点都一定满足（3.2.2）和（3.2.6），所以满足（3.2.8）

和（3.2.9），因此不会被割平面（3.2.9）割掉。

注：松弛问题（P0）的非整数最优解 x0 被割平面（3.2.9）割掉了。因为

00xB?b,xlj?0,lj?S

所以，

0fx?ljj?0?fl,j?S

所以 x0 不满足（3.2.8），即不满足（3.2.9）。

2、Gomory 割平面的计算步骤

第1步 用单纯形法求解（P）的松弛问题（P0）。若（P0）没有最优解，则停止计算，（P）也没有最优解； 若（P0）的最优解 x0 是整数向量，则 x0 是（P）的最优解。计算结束。否则，转第2步。

第2步 求割平面

任选 x0的一个非整数分量 bl(0?l?m)，由 bl所在的这一行

xBl??aljxj?bl,j?S

得到Gomory 割平面条件 再得到割平面

?fj?Sj?Sljxj?fl,

??fljxj?s??fl,（3.2.10）

第3步 将割平面（3.2.10）加到第1步所得的最优单纯形表里，用对偶单纯形方法求解这个改进的松弛问题。若其最优解是整数向量，则它是原问题（P）的最优解，计算结束。否则，将这个最优解重新记为 x0，返回第2步。

4