在线性规划问题中,最优解有可能是小数。对于某些具体问题,常常要求解必须是整数,FBMH1608HL471-T如加工的晶圆数目、占用的设备数等。此时,这类线性规划问题称为整数规划(IntcgerPro箩allnlling,IP);如果所有的决策变量都限制为整数,则称为整数规划;如果一部分决策变量限制为整数而另一部分限制为实数的规划则称为混合整数规划(Mixcd htcgcrProgra1111ning, MIP)。

   整数规划主要求解方法包括割平面法和匈牙利法。

   割平面法

   采用割平面法,通过增加新的约束来切割原问题伴随规划的可行域,使它不断缩小,从而将原问题的整数最优解逐渐暴露且趋于可行域极点的位置,这样就有可能用单纯形法求出最优解。求解步骤如下。

   第一步:先去掉整数规划中的整数约束,按一般连续线性规划求解,得到连续的最优解。

   第=步:构造一个新的线性约束,相当于在解向量空间中构成由一个割平面形成的半空间。