第二节 分枝定界法     (1) (2)
    分枝定界法是求解整数规划的常用算法，既可用来解全部变量取值都要求为整数的纯整数规划，又可用以求解混合整数规划。
    该算法的基本思路是：先不考虑整数限制，求出相应的线性规划的最优解，若此解不符合整数要求，则去掉不包含整数解的部分可行域，将可行域D分成D1、D2两部分（分枝） ，然后分别求解这两部分可行域对应的线性规划，如果它们的解仍不是整数解，则继续去掉不包含整数解的部分可行域，将可行域D1或D2分成D3与D4两部分，再求解D3与D4对应的线性规划，……，在计算中若已得到一个整数可行解X0，则以该解的目标函数值Z0作为分枝的界限，如果某一线性规划的目标值Z≤Z0 ，就没有必要继续分枝，因为分枝（增加约束）的结果所得的最优解只能比 Z0更差。反之若Z＞Z0 ，则该线性规划分枝后，有可能产生比Z0 更好的整数解，一旦真的产生了一个更好的整数解，则以这个更好的整数解目标值作为新的界限，继续进行分枝，直至产生不出更好的整数解为止。
    下面以实例来说明算法的步骤。
    例2 求解下面整数规划
        
    解：先不考虑条件⑸，求解相应的线性规划问题L，得最优解X1=4.81，X2=1.82，Z0=356（见图）
        
    该解不是整数解。选择其中一个非整数变量，如X1=4.81，对问题L分别增加约束条件：
    X1≤4，X1≥5 将问题L分解为两个子问题L1，L2（分枝），也就是去掉问题L不含整数解的一部分可行域，将原可行域D变为D1、D2两部分（如图）
        
    因为没有得到整数解，所以继续对L1进行分解，增加约束： X1≤2，X2≥3 将L1分解成问题L3与L4，并求得最优解如下：