（3）线性规划松弛问题的最优解不满足新的割约束
x2
x2
O （a）
x1
O
x1
（b）
7
OR:SM
五、割平面法求解举例
例：某厂拟购进甲、乙两类机床生产新产品。已知甲、乙机床进价分别为 2万元和3万元；安装占地面积分别为4m2和2m2；投产后的收益分别为3百元 /日和2百元/日。厂方仅有资金14万元，安装面积18m2。为使收益最大，厂 方应购进甲、乙机床各多少台？
将（5）式标准化:
1 2
x5
x6
1 2
加到前面单纯形表最终表中，有：
XB
x1
x2
x3
x4
x5
x6
x2
0
1
0
-1
1
0
x1
1
0
0
1
-1/2
0
x3
0
0
1
1
-2
0
x6
0
0
0
0
-1/2
1
Z
0
0
0
-1
-1/2
0
用对偶
x2
0
1
0
-1
ቤተ መጻሕፍቲ ባይዱ
0
2
单纯形
x1
1
0
0
1
0
-1
法求解， 得：
x3 x5
0 0
0 0
1 0
1 0
0 1
（5）式用决策变量表达的割平面方程为 6x1 5x2 29 6
x2
图示切 割过程
15
6x1+5x2=31
6
4x1+2x2=18
5
4
(3.25,2.5)
3
(3.5,2)
2 1
(4,1) 2x1+3x2=14
0
6x1+5x2=2x91
1 2 34 5 6 7 8 9
OR:SM
五、割平面法求解举例
20
OR:SM
一、选择题（续）
2、当你应用切割平面法，（ ）。
A）在处理每一块切割平面时，也要应用标准 线性规划方法
B）因为可以切去部分无用可行集，利用整数 规划方法可以得到比利用标准线性规划方法更 好的答案
C）因为削去了一些约束条件，实际上减少了 问题的约束条件。
D）因为加了约束，原最优解还起作用。
运筹学--管理科学方法
李军
桂林电子科技大学商学院
第四节 切割平面法
算法和流程
1、切割平面法原理 2、切割平面法算法
3、切割平面法计算 步骤
切割方程
1、切割方程构造 2、计算实例1 3、计算实例2
注意事项
1、切割平面法的优点 和不足 2、切割平面法使用注 意事项
2
OR:SM
一、割平面法的创立
割平面法是1958年由美国学者 R.E.Gomory提出来的，它是为克服分枝
xi N ik xk N bi fbi fik xk 0
k
k
（3）得割平面方程 fbi fik xk 0
k
6
OR:SM
四、割平面法的切割原理
由以上三式可知：
（1）切割方程真正进行了切割，至少把非整数最优解这一点割掉了。 （2）没有割掉整数解，这是因为相应的线性规划的任意整数可行解都满 足切割方程的缘故。
五、割平面法求解举例
对线性松弛问题，借用单纯形法，经迭代得最终表
XB
x1
x2
x3
x4
b
x2
0
1
1/2 -1/4 5/2
x1
1
0 -1/4 3/8 13/4
Z
0
0 - 1/4 -5/8 59/4
x1,x2均为 非整数
最优解： x1=13/4，x2=5/2， Z=59/4
任选一个构造 割平面方程
9
OR:SM
x3 x4
14 18
2 x1 4 x1
3x2 2x2
x2
6x1+5x2=31
6x1 5x2 31 （4） 6
4x1+2x2=18
5
（4）式是用决策 4
变量表达的割平 3
面方程。
2
(3.25,2.5) (3.5,2)
1
图示切 割过程
2x1+3x2=14
0
x1
1 2 34 5 6 7 8 9
12
OR:SM
五、割平面法求解举例
（3）对原数模引入割平面约束，将（3）式标准化：
1 2
x3
1 2
x4
x5
1 2
加到前面单纯形表中
XB
x1
x2
x3
x4
x5
b
对
x2
0
1
1/2 -1/2 0
5/2
偶
x1
1
0
-1/4 3/4
0
13/4
单 纯
x5
0
0
-1/2 -1/2
1
-1/2
形
Z
0
0
- 1/4 -5/4
（1）从单纯形最终表中抄下决策变量非整数解方程，
设为： xi aik xk bi
k
（1）
其 中bi是 基变量 的非整数解。
（2）将aik和bi分解为整数N和正的真分数f 两部分之和
aik Nik fik , bi Nni fbi
2
将（2）代入(1)中,然后将整数置于方程左边，分 数置于方程右变，即
五、割平面法求解举例
（2）寻找割平面方程（上表中非整数解）
x2
1 2
x3
1 2
x4
5 2
1
将（1）式所有系数和常数分解为整数和正的真分数之和
1
0x2
0
1 2
x3
1
1 2
x 4
2
1 2
1
（1 ）′式中整数系数项归于方程左边，真分数项归于
右边，有：
x2
x4
2
1 2
1 2
x3
1 2
返回目录
17
OR:SM
E-mail：lijun@
18
OR:SM
课堂练习
你明白了一点吗？
19
一、选择题
1、切割平面法（ ）。
A）也称为Gomory方法 B）有时称为戈尔斯基方法 C）只在0-1整数规划问题中应用 D）即使线性规划算法提供了初始整数解，我们也
要采用这一方法
OR:SM
一、选择题（续）
3、下列说法正确的是（ ）。
A）用分枝定界得到松弛问题的多个可行解，可任 取一个为整数规划问题目标函数值的上界。
B）整数规划问题的目标函数值优于其相应的松弛 问题解的目标函数值
C）割平面有可能割去非最优解的整数解 D）割平面方程是决策变量取整数的一个必要条件
22
OR:SM
0
59/4
法
13
OR:SM
五、割平面法求解举例
x2
0
1
0
-1
1
2非
x1
1
0
0
1
-1/2 7/2 整
x3
0
0
1
1
-2
1数
Z
0
0
0
-1 -1/2 58/4
转入第二步，求割平面方程。
x1
x4
1 2
x5
7 2
整理
x1
x4
x5
3
1 2
1 2
x5
0
即
1 2
1 2
x5
0
即-
1 2
x5
-
1 2
5
14
OR:SM
五、割平面法求解举例
-4 -2
返回目录
Z
0
0
0
-1
0
-1
16
b 2 7/2 1 -1/2 58/4
1 4 3 1 14
OR:SM
六、割平面法的优点和不足
优点： ①适于中小型整
数规划问题，也可 解混合整数规划问 题。
②学术性较强
切割平面法
不足： ①收敛较慢，舍入
误差大； ②割平面法取法不
唯一； ③不便于计算机求
解
割平面法在学术界影响较大
x4
2
10
OR:SM
五、割平面法求解举例
x2
1 2
x3
1 2
x4
5 2
1
正真分数
x2
x4
2
1 2
1 2
x3
1 2
x4
2
整数
因此有
1 2
（1 2
x3
1 2
x4）
0
正数
小于0的 整数
即有
1 2
x3
1 2
x4
1 2
3
（3）式即为为割平面方程。
11
OR:SM
五、割平面法求解举例
从标准规范形中得 代入(3)式中得：
界法的不足提出来的，基本思想是通过添加切割方程使整数解由内点变 为顶点。
3
OR:SM
算 法 步 骤
4
二、割平面法的算法
求松弛问题的 最优基可行解
判断是否
是
为整数解
否
在单纯性表中加入一列 利用对偶单纯性算法
求最优解
得到最优解
停止
如何构 造割平 面程？
OR:SM
二、割平面法计算步骤
step1
对整数规划问题 ，去掉整数约束 ，用单纯形法求 解。若最优解是 整数，停止计算 ，否则转第（2 ）步。