3 割平面法
割平面法是通过生成一系列的平面割掉非整数部分来得到最优整数解的方法。
目前，割平面法有分数割平面法，原始割平面法，对偶整数割平面法，混合割平面法等。
我们介绍Gomory割平面法（纯整数规划割平面法）
用例子说明割平面法基本思想。
例5-8 求下列问题：
Max Z=2x1+ 3x2
+4x2 25
x1 8
2x2 10
x1,x2 0,且取整数值
化成标准问题
Max Z=2x1+ 3x2
+4x2 + x3 =25
x1 + x4 =8
2x2 + x5 =10
xj 0,且取整数值
松驰问题(P)
Max Z=2x1+ 3x2
+4x2 + x3 =25
x1 + x4 =8
2x2 + x5 =10
xj 0
松驰问题(P)
用单纯形法求解得到最优解：
B（8，9/4） Z=22（3/4）
但不是原问题（IP）的解，（IP）可行域是OABDE内的全部方格点组成。
B
D
E
O 1 2 3 4 5 6 7 A8 9 10 11 12
10 9 8 7 6 5 4 3 2 1
X1
X2
引进割平面法
l1: x1+ x2 =10
割去非整数部分FBG
l2: x1+2x2 =12
割去非整数部分HDGF
G
B
F
D
E
l1
O 1 2 3 4 5 6 7 A8 9 10 11 12
10 9 8 7 6 5 4 3 2 1
X1
X2
l2
G
B
F
H
D
E
O 1 2 3 4 5 6 7 A8 9 10 11 12
10 9 8 7 6 5 4 3 2 1
X1
X2
G
H
E
O 1 2 3 4 5 6 7 A8 9 10 11 12
10 9 8 7 6 5 4 3 2 1
X1
X2
形成新的凸可行域OAGHE（整点凸包），它的极点G（方格点）是原规划（IP）的最优解（8，2） Z=22。
约束条件：
l1: x1+ x2 10
l2: x1+2x2 12
称为割平面。
问题是如何寻找割平面？
松驰问题(P)
Max Z=2x1+ 3x2
+4x2 + x3 =25
x1 + x4 =8
2x2 + x5 =10
xj 0
初始单纯形表
最终单纯形表:最优解（8,9/4,0,0,11/2） Z =91/4
X2相应的方程：
x2+(1/4)x3 –(1/2) x4 =9/4
x2+(1/4)x3 –(1/2) x4 =9/4
把所有系数分解成整数和非负真分数之和。
x2+(1/4)x3 – x4+(1/2) x4 =2+1/4
x2– x4 – 2=(1/4)- (1/4)x3 -(1/2) x4
令(1/4)- (1/4)x3 -(1/2) x4 0（*）
加松驰变量：
(1/4)- (1/4)x3 -(1/2) x4 +x6 =0
(1/4)- (1/4)x3 -(1/2) x4 +x6 =0
(1/4)x3 -(1/2) x4 +x6 = - (1/4)
插入原最终表中，继续计算。
原始不可行，对偶可行，用对偶单纯形法计算
第四行乘上（-2）
第一、二行减去第四行，第三行加上第四行的1/2倍
最优解（15/2，5/2，0，1/2，5） Z=45/2
F点
G
B
F
D
E
l1
O 1 2 3 4 5 6 7 A8 9 10 11 12
10 9 8 7 6 5 4 3 2 1
X1
X2
进行第二次切割：
进行第二次切割：
X1-(1/2)x3 +2x6 =15/2
X1-(1/2)x3 +2x6 =15/2
X1-x3 +(1/2)x3 +2x6 - 7= (1/2)
X1-x3 +2x6 - 7= (1/2) -(1/2)x3
令(1/2) -(1/2)x3 0 （**）
-(1/2)x3 -(1/2)
加松驰变量：
-(1/2)x3 + x7 = - (1/2)
插入上表中，继续计算。
得到最优解（8,2,1,0,6,) Z=22 G点
G
H
E
O 1 2 3 4 5 6 7 A8 9 10 11 12
10 9 8 7 6 5 4 3 2 1
X1
X2
B
D
E
O 1 2 3 4 5 6 7 A8 9 10 11 12
10 9 8 7 6 5 4 3 2 1
X1
X2
求解过程：最优解B点
G
B
F
D
E
l1
O 1 2 3 4 5 6 7 A8 9 10 11 12
10 9 8 7 6 5 4 3 2 1
X1
X2
求解过程：最优解F点
l2
G
B
F
D
E
l1
O 1 2 3 4 5 6 7 A8 9 10 11 12
10 9 8 7 6 5 4 3 2 1
X1
X2
求解过程：最优解G点
(1/4)- (1/4)x3 -(1/2) x4 0（*）
(1/2) -(1/2)x3 0 （**）
根据2x1+4x2 + x3 =25
x1 + x4 =8
x3 =25- 2x1- 4x2
x4 =8 - x1
代入（*）（**）
x1 + x2 10 l1
x1 + 2x2 12 l2
即为两个割平面。
Gomory定理：若可行域D非空有界，则经过有限次循环后，算法必将终止。
例5-9 求下列问题：
Max Z= x1+ x2
. -x1+x2 1
3x1+x2 4
x1,x2 0,且取整数值
标准问题：
Max Z= x1+ x2
. -x1+x2+ x3=1
3x1+x2+ x4=4
x1,x2 ,x3 ,x4 0, 取整数值
初始单纯形表
最终单纯形表，最优解（3/4，7/4）
Z=5/2
X1-(1/4)x3 + (1/4) x4 =3/4
X2 +(3/4)x3 + (1/4) x4 =7/4
X1-x3 = 3/4 -(3/4)x3 - (1/4) x4
X2 -1 = 3/4 -(3/4)x3 - (1/4) x4
令 3/4 -(3/4)x3 - (1/4) x4 0
-3x3 - x4 -3
-3x3 - x4 + x5 = -3
得到第一个切割方程，插入原最优表，继续计算。
原始不可行，对偶可行，用对偶单纯形法计算
第三行乘（-1/3）
第一行加第三行乘（ 1/4）
第二行加第三行乘（- 3/4）
得到最优解(1,1,1) Z=2
O 1 2
2 1
X1
X2
A
标准问题：
Max Z= x1+ x2
. -x1+x2+ x3=1
3x1+x2+ x4=4
x1,x2 ,x3 ,x4 0, 取整数值
x3=1 +x1-x2
x4=4 -3x1-x2
代入
-3x3 - x4 -3
x2 1
O 1 2
2 1
X1
X2
A
C
O 1 2
2 1
X1
X2
A
C
O 1 2
2 1
X1
X2
C
最优解（1，1） Z=2
