第二节 分枝定界法     (1) (2)
    问题L3的解已是整数解，它的目标值Z3=340，大于问题L4的目标值，所以问题L4已无必要再分枝。但由于问题L2的目标值Z2大于Z3，分解L2还有可能产生更好的整数解，因此继续对L2分枝。增加约束X2≤1，X2≥2 将L2分解成问题L5与L6，并求解，结果如下：
        
    问题L5的Z5=308<Z3=340，所以不必分解了；问题L6无可行解，于是可以断定问题L3的解：
    X1=4.00，X2=2.00即为最优整数解。
    整个分枝定界过程如下图所示：
        
    用分枝定界法求解整数规划的步骤可总结如下：
    步骤1：求解与整数规划相对应的线性规划L，若L无可行解，则整数规划也没有可行解，计算停；若L的最优解是整数解，则该解即为整数规划的最优解，计算停；若L的最优解不是整数解，则转步骤2。
    步骤2（分枝）在L的最优解中任选一个不符合整数条件的变量，其值为为小于的最大整数，构造两个约束条件
    将这两个约束条件分别加在问题L的约束条件上，形成两个子问题和，并求解和 。
    步骤3（定界）取整数解中最大目标值为界限值Z(下界)，如果计算中尚无整数解，则取Z=-∞。检查分枝Li，若它的最优解不是整数解，且Zi＞Z，则重复步骤2，若Zi≤Z，则不再分枝。
    重复步骤2、步骤3，直至所有分枝都不能再分解为止，这时界限值Z对应的整数解即为原问题的最优解。用分枝定界法可解纯整数规划问题和混合整数规划问题。它比穷举法优越，因为它仅在一部分可行的整数解中寻求最优解，计算量比穷举法小。若变量数目很大，其计算工作量也是相当可观的。