42整数规划的分枝定界法 42.1思路与解题步骤 只解松弛问题 1、在全部可行性城上解松弛问题 若松弛问题最优解为整数解,则其也是整数规划的 最优解 分枝过程 若松弛问题最优解中某个x=b不是整数,令Lb」 为b的整数部分 构造两个新的约束条件xsLb」和xk≥LbkH+1,分 别加于原松弛问题,形成两个新的整数规划 3、求解分枝的松弛问题一定界过程 设两个分枝的松弛问题分别为问题1和问题2,它 们的最优解有如下情况3 4.2 整数规划的分枝定界法 4.2.1 思路与解题步骤 • 只解松弛问题 1、在全部可行性域上解松弛问题 – 若松弛问题最优解为整数解，则其也是整数规划的 最优解 2、分枝过程 – 若松弛问题最优解中某个 xk=bk 不是整数，令  bk  为 bk 的整数部分 – 构造两个新的约束条件 xk  bk  和 xk  bk +1，分 别加于原松弛问题，形成两个新的整数规划 3、求解分枝的松弛问题 — 定界过程 – 设两个分枝的松弛问题分别为问题 1 和问题 2 ，它 们的最优解有如下情况