毕业论文移动版

2.2分支定界法

当我们求解整数规划的问题时，如果可行域是有界的，可以使用穷举法来穷举所有可行的整数组合，接着一一比较它们的目标函数值就可以直接决定出最优解。但是，穷举变量仅仅只适合小规模的问题，问题的规模小，变量数就会很少，要穷举的可行的整数组合种类也是很少的，此时这个方法就既是可行的，也是有效的。就比如在上述的例1中，变量就只有x1和x2两个；由于条件②的约束，x1所能取的整数值就只有0、1、2、3、4；同样由于条件③的约束，x2所能取的整数值也只有0、1、2，所以它们能构成的组合（不都是可行的）一共就3515(个)，此时使用穷举法还是勉强能行的。但是对于规模大的问题来说，可行的整数组合种类很多，组合数量是很大的。这样的问题如果要一一计算，即使是每秒能计算百万次的计算机，也需要几万年的时间才能做出来，因此，要求解这样的问题，穷举法就变得不可取了[3]。分支定界法（branchandbound）是求整数规划问题中最常见的算法之一，它不仅能求纯整数规划最优解，还可以用来求混合整数规划问题的最优解。从根本上讲，分支定界法是一种广义的搜索算法，人工使用非常繁琐，但由于计算机的运算速度快的特点，这种算法十分适合计算机进行。分支定界法是计算机最擅长的广义搜索穷举算法。

分支定界法的基本思想是：

1.松弛问题的最优解要优于其相应的整数规划的解，由于松弛模型可行解的区域（多边形）包含了对应的整数规划的可行解的集合（多边形内的整数点），因而，松弛问题的解要优于整数规划的解。这就是说，如果问题是求最大值的，则松弛问题最优解对应的目标函数值必大于或等于整数规划最优解对应的目标函数值如果问题是求最小值的，则松弛问题的最优解对应的目标函数值必小于或等于整数规划最优解对应的目标函数值。由此可以推出：

2.松弛模型的最优解如果是整数解，则必然也是整数规划的最优解。

3.松弛问题的最优解如果不是整数解，则如果问题是求最大值的，松弛问题最优解的目标函数值是整数规划最优解目标函数值的一个上界；如果问题是求最小值的，则松弛问题最优解的目标函数值是整数规划最优解目标函数值的一个下界。

如果设A为求最大值的整数规划问题，同时设与它相对应的线性规划为问题—松弛问题B，现在先来求解问题B，如果它的最优解不符合A的整数条件，那么此时B的最优目标函数值就必定是A的最优目标函数值z*的上界，记作z；而A的任意可行解的目标函数值都可以作为z*的一个下界z。分支定界法就是一种将B的可行域分成子区域（分支），然后在新的可行域再次求最优解的方法，通过逐步减小z和增大z来求得z*。现在将通过一个例子来说明。