第二节 Gomory割平面法
§ Gomory割平面法的基本思想
§ Gomory割平面法计算步骤
§ Gomory割平面法的基本思想
考虑纯整数线性规划问题
可行区域记为D
(P)的松弛问题
可行区域
由有限个或可数的格点构成的集合
多面凸集
割平面法的基本思想
费用减小方向
生成割平面条件的代数方法(Gomory)
基变量的下标集合为 S
非基变量的下标集合为
令
相减
相减
Gomory割平面条件
割平面
定理
§ Gomory割平面法计算步骤
第1步
用单纯形法解
ILP
问题
)
(
P
的松弛问题
)
(
0
P
.
若
)
(
0
P
没有最优解，则计算停止，
)
(
P
也没有最优
解
.
若
)
(
0
P
有最优解
0
x
，假若
0
x
是整数向量，则
0
x
是
)
(
P
的最优解，计算停止，输出
0
x
；否则转第
2
步
.
第2步
求割平面方程
第3步
例
求解ILP问题
max x2
解
这个问题及其松弛LP问题的可行区域如图所示
经过两次旋转变换得到最优单纯形表为
max x2
经过两次旋转变换得到最优单纯形表为
max x2
