整数规划及其割平面法

        在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求某些变量的解必须是整数。例如，当变量代表的是机器的台数，工作的人数或装货的车数等。

  为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。

  在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是01规划，它的变数仅限于0或1。不同于线性规划问题，整数和01规划问题至今尚未找到一般的多项式解法。

   割平面法主要用于求解整数规划问题的方法。1958年由美国格莫理提出。基本思路是：先不考虑整数性约束，求解相应的线性规划问题。若线性规划问题的最优解恰好是整数解，则此解即为整数规划问题的最优解。否则，就增加一个新的约束条件,称为割平面。

割平面必须具有两条性质：        

（1)从线性规划问题的可行域中至少割掉目前的非整数最优解；      

（2)不割掉任何整数可行域，然后在缩小的可行域上继续解线性规划问题。        

重复以上做法，经有限次切割后，必可在缩小的可行域的一个整数极点上达到整数规划问题的最优解