发布时间 : 星期三 文章§3.2 Gomory 割平面法更新完毕开始阅读3164f152690203d8ce2f0066f5335a8103d2660f
§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