整数规划模型求解的一般思路是，先不考虑整数约束进行求解，而是把这个解凑整，然后估计一下凑整后的解使目标函数值损失的上限或下限，如果目标函数值损失不大，就可以用凑整后的解作为考虑整数约束时的最优解。

初看起来，为了满足最优解必须是整数的要求，只要把线性规划带小数的最优解“舍入化整”就可以了，但这往往会造成不可行问题的出现。因为化整后的解不一定是可行解，有时即便是可行解，也未必是最优解。因此，对全部或部分决策变量的取值要求为整数的线性规划问题的求解，应该有能够求整数解的方法。

下面通过一个例题，分析一下通过凑整方法求解时出现的问题。

例7.1　某企业用钢和铝生产两种产品A、B，有关资料如表7.1所示，求生产产品A、B各为多少时才能使利润最大？

表7.1

(www.daowen.com)

设x1为A产品的产量，x2为B产品的产量，线性规划模型如下：

针对上例，首先不考虑整数约束的条件，使用单纯形法求出的最优解为x1=4.8，x2=0，对应的目标函数值z=96。现在把x1=4.8，x2=0凑整为x1=5，x2=0，把这个解代入第一个约束条件方程，会使该方程不成立，这说明这个解不是可行解；再把x1=4.8，x2=0凑整为x1=4，x2=0，把这个解代入约束条件方程组中，所有的方程都成立，是可行解，对应的目标函数值z=80，但不是最优解，因为有另外一个解x1=4，x2=1是最优解，对应的目标函数值z=90，这就说明这个解比x1=4，x2=0还要优。

由此看来，对非整数解进行“舍入化整”的方法容易想得到，但常常得不到整数要求的最优解，有时甚至根本不是可行解，因此对整数规划求解应该有专门的方法。

下面以目标函数为max型为例。假设不考虑整数约束的最优解对应的目标函数值为zc，用整数规划方法求出的整数最优解对应的目标函数值为zd，不考虑整数约束的最优解凑整后对应的目标函数值为zr，则zc－zr就是目标函数值损失的上界。另外，三者之间存在的关系是zr≤zd≤zc，这就是后面第7.1.3节中分枝定界算法是否终止分枝的一个重要判别条件，也是所谓的“定界”依据。