运筹学笔记 整数编程-3 整数编程和切割平面法

此方法的基础仍然是用解线性规划的方法去解整数规划问题。
思路： 先不考虑变量x_i是整数这一条件，但增加线性约束条件（几何术语：割平面）使得由原可行域中切割掉一部分（此部分只包含非整数解，没有切割掉任何整数可行解），使切割后最终得到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。
该方法是1958年R.E.Gormory首先提出的，故又称为Gormory割平面法
割平面法的关键： 如何找到适当的割平面？
构造割平面约束的方法很多，下面只介绍一种（它可以从相应线性规划的最终单纯形表中直接产生）

先通过举一简单的例子入手，介绍算法的过程

将上推导对应一般情况，可得：
思路：
用割平面法解整数规划时，若其松弛问题的最优解x不满足整数条件，则从x的非整分量中选取一个，用以构造一个线性约束条
件，将其加入原松弛问题中，形成一个新的线性规划之后求解。
若新的最优解满足整数条件，则它就是整数规划的最优解，否则重复上述步骤，直到获得最优解为止。
为获得整数最优解，每次增加的线性约束条件应满足2个基本性质
（1）已获得的不符合整数要求的线性规划最优解不满足该线性约束条件，从而不可能在以后的解中再出现。
（2）凡整数可行解均满足该线性约束条件，故整数最优解始终被保留在每次形成的线性规划可行域中。