割平面法

割平面法

-

2023年2月28日发(作者：女王头)

§3.2Gomory割平面法

1

§3.2Gomory割平面法

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



















为整数向量x

x

bAxts

xcT

0

..

min

（P）















0

..

min

x

bAxts

xcT

（P

0

）

称（P

0

）为（P）的松弛问题。记（P）和（P

0

）的可行区域分别为D和D

0

,则

（1）

0

DD；

（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)

x0

。。

。。

费用减少的方向

(P

0

)x1

。。

。。

费用减少的方向

(P

1

)

。。

。。

§3.2Gomory割平面法

2

割平面的生成：

对给定的（P），用单纯形法求解它的松弛问题（P

0

），得到（P

0

）的最优基

本可行解0x

，设它对应的基为

),,(

1m

BB

AAB

，

m

BB

xx,,

1



为0x

的基变

量，记基变量的下标集合为

S

，非基变量的下标集合为

S

。则松弛问题（P

0

）

的最优单纯形表为







Sj

jj

zxz

0



mibxax

Sj

ijijB

i

,,1,



（3.2.1）

为了使符号简便，令

000

,,

0

zbazx

jjB

。如果mib

i

,,1,0,全

是整数，则0x

是（P）的最优解。计算结束。否则至少有一个

l

b不是整数

)0(ml

，设

l

b所对应的约束方程为

,





Sj

ljljB

bxax

l（3.2.2）

用

][a

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

,][,,][

lllljljlj

fbbSjfaa

（3.2.3）

其中，

lj

f是

lj

a的分数部分，有Sjf

lj

,10，

l

f是

l

b的分数部分，

有.10

l

f

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





Sj

jlj

Sj

jlj

xaxa][

（3.2.4）

所以由（3.2.2）得

,][





Sj

ljljB

bxax

l（3.2.5）

因为在ILP中x限制为整数向量，故（3.2.5）的左端为整数，所以右端用

l

b的

整数部分去代替后，（3.2.5）式的不等式关系仍成立，即

§3.2Gomory割平面法

3

],[][





Sj

ljljB

bxax

l（3.2.6）

用（3.2.2）减（3.2.6）得

]),[(])[(





Sj

lljljlj

bbxaa

（3.2.7）

由（3.2.2），可得线性约束

,





Sj

ljlj

fxf

（3.2.8）

称它为对应于生成行

l

的Gomory割平面条件。

为了将（3.2.8）加到松弛问题（P

0

）的最优单纯形表，应将它变为等式，所

以引入一个剩余变量s，从而（3.2.8）变为

,





Sj

ljlj

fsxf

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

,





Sj

ljlj

fsxf

（3.2.9）

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

把割平面（3.2.9）加到松弛问题（P

0

）的最优单纯形表的最后一行，可得

改进的松弛问题（P

1

）的单纯形表







Sj

jj

zxz

0



mibxax

Sj

ijijB

i

,,1,



,





Sj

ljlj

fsxf

（P

1

）的变量个数为1n，等式约束为1m，它的基变量个数为1m。显

然，

sxx

m

BB

,,,

1



是（P

1

）的基变量。所以，对（P

1

），获得了一个基本解，并

且它的检验数向量0)0,,,(

1

T

n

。所以可用对偶单纯形方法求解改进的

松弛问题（P1）。

§3.2Gomory割平面法

4

定理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）割掉了。因为

Sjxbx

jlB

l

,0,00

所以，

,00





Sj

ljlj

fxf

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

2、Gomory割平面的计算步骤

第1步用单纯形法求解（P）的松弛问题（P

0

）。若（P

0

）没有最优解，则

停止计算，（P）也没有最优解；若（P

0

）的最优解0x是整数向量，则0x是

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

第2步求割平面

任选0x

的一个非整数分量)0(mlb

l

，由

l

b所在的这一行

,





Sj

ljljB

bxax

l

得到Gomory割平面条件

,





Sj

ljlj

fxf

再得到割平面

,





Sj

ljlj

fsxf

（3.2.10）

第3步将割平面（3.2.10）加到第1步所得的最优单纯形表里，用对偶单

纯形方法求解这个改进的松弛问题。若其最优解是整数向量，则它是原问题（P）

的最优解，计算结束。否则，将这个最优解重新记为0x，返回第2步。

§3.2Gomory割平面法

5

例3.2.1求解ILP问题























整数,0,

023

623..

max

21

21

21

2

xx

xx

xxts

xz

（3.2.11）

解：先将（3.2.11）化为标准形式























整数,0,,,

023

623..

min

4321

421

321

2

xxxx

xxx

xxxts

xz

（P）

它对应的松弛问题（P

0

）为























0,,,

023

623..

min

4321

421

321

2

xxxx

xxx

xxxts

xz

（P

0

）

显然，Tx)0,6,0,0(是（P

0

）的初始解，其基变量是

3

x和

4

x。所以（P

0

）的

第一张单纯形表为

1

x

2

x

3

x

4

xRHS

z01000

3

x32106

4

x-32010

1

x

2

x

3

x

4

xRHS

z3/200-1/20

3

x601-16

2

x-3/2101/20

§3.2Gomory割平面法

6

（3.2.13）

所以，松弛问题（P

0

）的最优解为Tx)0,0,

2

3

,1(0

，因0x

不是整数向量，所以

生成割平面（第0行和第2行均可生成割平面）。由第2行生成的割平面条件为

2

1

4

1

4

1

43

xx

相应的割平面为

2

1

4

1

4

1

143

sxx

（3.2.16）

把（3.2.16）加到松弛问题（P

0

）的最优单纯形表（3.2.13）中，得到改进的松弛

问题（P

1

）的单纯形表

用对偶单纯形算法求解

1

x

2

x

3

x

4

xRHS

z00-1/4-1/4-3/2

1

x101/6-1/61

2

x011/41/43/2

1

x

2

x

3

x

4

x

1

sRHS

z00-1/4-1/40-3/2

1

x101/6-1/601

2

x011/41/403/2

1

s00-1/4-1/41-1/2

1

x

2

x

3

x

4

x

1

sRHS

z00-1/4-1/40-3/2

1

x101/6-1/601

2

x011/41/403/2

1

s00-1/4-1/41-1/2

§3.2Gomory割平面法

7

（3.2.17）

所以，改进的松弛问题（P

1

）的最优解为Tx)2,0,0,1,

3

2

(1

，由于0x

不是整数

向量，所以生成割平面。由第1行生成的割平面条件为

3

2

3

2

3

2

14

sx

相应的割平面为

3

2

3

2

3

2

214

ssx

（3.2.18）

把（3.2.18）加到改进的松弛问题（P

1

）的最优单纯形表（3.2.17）中，得到新的

松弛问题（P

2

）的单纯形表

用对偶单纯形算法求解

1

x

2

x

3

x

4

x

1

sRHS

z0000-1-1

1

x100-1/32/32/3

2

x010011

3

x0011-42

1

x

2

x

3

x

4

x

1

s

2

sRHS

z0000-10-1

1

x100-1/32/302/3

2

x0100101

3

x0011-402

2

s000-2/3-2/31-2/3

§3.2Gomory割平面法

8

所以，松弛问题（P

2

）的最优解为Tx)0,0,1,1,1,1(2。所以，原问题的最优解

为Tx)1,1(*。

注：原问题（P）的松驰问题（P

0

）的可行区域是如图的三角形

OAB

区域，

（P）的可行区域是

OAB

中的四个格点：（0，0），（1，0），（2，0），（1，1）。

割平面条件

2

1

4

1

4

1

43

xx

等价为1

2

x

割平面条件

3

2

3

2

3

2

14

sx

等价为

12

xx

1

x

2

x

3

x

4

x

1

s

2

sRHS

z0000-10-1

1

x10001-1/21

2

x0100101

3

x0010-53/21

2

s00011-3/21

。。。

。。。

。。。

O12Ax

1

x

2

2

1

B

目标函数

值增加

。。。

。。。

。。。

O12Ax

1

x

2

2

1

B

目标函数

值增加

。。。

。。。

。。。

O12Ax

1

x

2

2

1

B