设纯整数规划
松弛问题
的最优解
设xi不为整数，
运筹学 北京邮电大学
将 分离成一个整数与一个非负真分数之和：
则有
等式两边都为整数并且有
运筹学 北京邮电大学
加入松弛变量si得
此式称为以xi行为源行（来源行）的割平面，或分数切割式，或(高莫雷)约束方程。
将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。
则
运筹学 北京邮电大学
例如，
x1行：
移项：
令
加入松弛变量s1得
同理，对于x2行有：
运筹学 北京邮电大学
如果在对偶单纯形法中原切割方程的松弛变量仍为基变量，则此松弛变量所在列化为单位向量后就可以去掉该行该列，再切割。
【例】已知整数规划
【解】不考虑整数约束，松弛问题的最优表如下
运筹学 北京邮电大学
－5/4
－1/4
0
0
λj
13/4
3/4
－1/4
0
1
x1
3
5/2
－1/2
1/2
1
0
x2
2
b
x4
x3
x2
x1
XB
CB
0
0
2
3
cj
最优表
最优解X=(－1/2，3/4，0，0)T， x1 、x2不满足整数要求，选择x2行进行分割：
得到Gomory约束
添加到最优表中，得
运筹学 北京邮电大学
0
1
0
0
x5
0
－1/2
－1/2
－1/2
0
0
x5
0
－5/4
－1/4
0
0
λj
13/4
3/4
－1/4
0
1
x1
3
5/2
－1/2
1/2
1
0
x2
2
b
x4
x3
x2
x1
XB
CB
0
0
2
3
cj
－1/2
－2
－1/2
½
1
1
1
0
0
x3
0
－1
0
0
0
λj
7/2
1
0
0
1
x1
3
－1
0
1
0
x2
2
2
x1行：
Gomory约束
添加到最优表中，得
运筹学 北京邮电大学
0
1
0
0
0
x6
0
－1/2
－1/2
0
0
0
0
x6
0
－1/2
－1
－1/4
½
x5
0
1
1
1
0
0
x3
0
－1
0
0
0
λj
7/3
1
0
0
1
x1
3
2
－1
0
1
0
x2
2
b
x4
x3
x2
x1
XB
CB
0
0
2
3
cj
－1
－2
－4
－1
2
1
1
0
0
0
0
x6
0
0
0
0
0
3
1
1
0
0
x3
0
－1
0
0
0
λj
4
1
0
0
1
x1
3
－1
0
1
0
x2
2
1
运筹学 北京邮电大学
得到整数最优解：X＝(4，1)，Z＝14
注1：
Gomory约束可写为
注2： Gomory约束只是割去线性规划可行域的一部分，保留了全部整数解。
用图解法表示：
运筹学 北京邮电大学
13/4,5/2
松弛问题
第一次切割
4,1
第二次切割
x1+x2≤5
运筹学 北京邮电大学
作业：教材P134
0—1规划
指派问题
Exit
1.领会割平面法的基本原理
1.分离源行，求出Gomory约束
2.在最优表中增加Gomory约束，用 对偶单纯形法迭代
运筹学 北京邮电大学
