®§2分枝定界法 分枝定界法是求解整数规划的常用算法，既可用来解全部变量 取值都要求为整数的纯整数规划，又可用以求解混合整数规划 该算法的基本思路是：先不考虑整数限制，求出相应的线性规 划的最优解，若此解不符合整数要求，则去掉不包含整数解的部分 可行域，将可行域D分成D1、D2两部分（分枝），然后分别求解这 两部分可行域对应的线性规划，如果它们的解仍不是整数解，则继 续去掉不包含整数解的部分可行域，将可行域D1或D2分成D3与D4两 部分，再求解D,与D4对应的线性规划，.，在计算中若已得到一 个整数可行解X,则以该解的目标函数值乙作为分枝的界限，如果 某线性规划的目标值Z≤Z。，就没有必要继续分枝，因为分枝 (增加约束)的结果所得的最优解只能比乙，更差。反之若乙>Z, 则该线性规划分枝后，有可能产生比乙，更好的整数解，一旦真的产 生了一个更好的整数解，则以这个更好的整数解目标值作为新的界 限，六继续进行分枝，直至产生不出更好的整数解为止。 下面以实例来说明算法的步骤。 §2 分枝定界法 分枝定界法是求解整数规划的常用算法，既可用来解全部变量 取值都要求为整数的纯整数规划，又可用以求解混合整数规划。 该算法的基本思路是：先不考虑整数限制，求出相应的线性规 划的最优解，若此解不符合整数要求，则去掉不包含整数解的部分 可行域，将可行域D分成D1、D2两部分（分枝） ，然后分别求解这 两部分可行域对应的线性规划，如果它们的解仍不是整数解，则继 续去掉不包含整数解的部分可行域，将可行域D1或D2分成D3与D4两 部分，再求解D3与D4对应的线性规划，……，在计算中若已得到一 个整数可行解X 0 ，则以该解的目标函数值Z0作为分枝的界限，如果 某一线性规划的目标值Z≤ Z0 ，就没有必要继续分枝，因为分枝 （增加约束）的结果所得的最优解只能比Z0 更差。反之若Z＞ Z0 ， 则该线性规划分枝后，有可能产生比Z0 更好的整数解，一旦真的产 生了一个更好的整数解，则以这个更好的整数解目标值作为新的界 限，继续进行分枝，直至产生不出更好的整数解为止。 下面以实例来说明算法的步骤