§3.2 Gomory 割平面法

§3.2 Gomory 割平面法

例3.2.1 求解 ILP 问题

?maxz?x2?s.t.3x?2x?6?12 ? （3.2.11）

?3x?2x?012???x1,x2?0,整数解：先将（3.2.11）化为标准形式

?minz??x2?s.t.3x?2x?x?6?123 ? （P）

?x4?0??3x1?2x2??x1,x2,x3,x4?0,整数它对应的松弛问题（P0）为

?minz??x2?s.t.3x?2x?x?6?123 ? （P0）

?x4?0??3x1?2x2??x1,x2,x3,x4?0显然，x?(0,0,6,0)T是（P0）的初始解，其基变量是 x3 和x4。所以（P0）的第一张单纯形表为

x1 x2 x3 x4

0 3 -3

1 2 2 0 1 0

0 0 1

RHS 0 6 0

z

x3 x4

x1 x2 x3

3/2 6 0 0

0 1 0

z

x3 x2

-3/2 1

x4 RHS

-1/2 0 -1 6 1/2 0

5

§3.2 Gomory 割平面法

x1 x2 x3 x4 RHS

z 0 0 -1/4 -1/4 -3/2

（3.2.13）

x1 1 0 1/6 -1/6 1

x2 0 1 1/4 1/4 3/2

3所以，松弛问题（P0）的最优解为 x0?(1,,0,0)T，因x0 不是整数向量，所以

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

111 x3?x4?

442相应的割平面为

111 ?x3?x4?s1?? （3.2.16）

442把（3.2.16）加到松弛问题（P0）的最优单纯形表（3.2.13）中，得到改进的松弛问题（P1）的单纯形表

x1 x2 x3 x4 s1 RHS

z 0 0 -1/4 -1/4 0 -3/2

x1 1 0 1/6 -1/6 0 1

x2 0 1 1/4 1/4 0 3/2

s1 0 0 -1/4 -1/4 1 -1/2

用对偶单纯形算法求解

x1 x2 x3 x4 s1 RHS

z 0 0 -1/4 -1/4 0 -3/2

x1 1 0 1/6 -1/6 0 1

x2 0 1 1/4 1/4 0 3/2

s1 0 0 -1/4 -1/4 1 -1/2

6

§3.2 Gomory 割平面法

x1 x2 x3

0 1 0 0

0 0 1 0

0 0 0 1

z

x1 x2 x3

x4 s1 RHS

0 -1 -1

-1/3 2/3 2/3 （3.2.17）

0 1 1 1 -4 2

2所以，改进的松弛问题（P1）的最优解为 x1?(,1,0,0,2)T，由于x0 不是整数

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

222 x4?s1?

333相应的割平面为

222 ?x4?s1?s2?? （3.2.18）

333把（3.2.18）加到改进的松弛问题（P1）的最优单纯形表（3.2.17）中，得到新的松弛问题（P2）的单纯形表

x1 x2 x3 x4 s1 s2 RHS

z 0 0 0 0 -1 0 -1

x1 1 0 0 -1/3 2/3 0 2/3

x2 0 1 0 0 1 0 1

x3 0 0 1 1 -4 0 2

s2 0 0 0 -2/3 -2/3 1 -2/3

用对偶单纯形算法求解

7

§3.2 Gomory 割平面法

x1 x2 x3 x4 s1 s2

0 1 0 0

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

-1

0

RHS -1 1 1 1 1

z

x1 x2 x3

1 -1/2 1

0

-5 3/2 1 -3/2

s2 0

所以，松弛问题（P2）的最优解为 x2?(1,1,1,1,0,0)T。所以，原问题的最优解为 x*?(1,1)T。

注： 原问题（P）的松驰问题（P0）的可行区域是如图的三角形 ?OAB区域，（P）的可行区域是?OAB中的四个格点：（0，0），（1，0），（2，0），（1，1）。

111割平面条件x3?x4? 等价为 x2?1

442222 割平面条件x4?s1? 等价为 x2?x1

333 目标函数目标函数 值增加 值增加 x2 x2 x2 2 。 。 。 2 。 。 。 2 。 。 。 B B B 1 。 。 。 1 。 。 。 1 。 。 。 。 。 。 。 。 。 。 。 。 O 1 2 A x1 O 1 2 A x1 O 1 2 A x1

8