Ch4IntegerProgramming 4.3分枝定界法 BranchandBoundMethod Page1of8 分枝定界法的步骤： 1.求整数规划的松弛问题最优解； 2.若松弛问题的最优解满足整数要求，得到整数规划的最 优解，否则转下一步； 3.任意选一个非整数解的变量x i ，在松弛问题中加上约束x i x i 及 x i x i +1 组成两个新的松弛问题，称为分枝。新的松弛问题具有特 征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题 是求最小值时，目标值是分枝问题的下界； 4.检查所有分枝的解及目标函数值，若某分枝的解是整数并且目 标函数值大于（max ）等于其它分枝的目标值，则将其它分枝剪去 不再计算，若还存在非整数解并且目标值大于（max ）整数解的目 标值，需要继续分枝，再检查，直到得到最优解。 DateCh4IntegerProgramming 4.3分枝定界法 BranchandBoundMethod Page2of8 从上所述可知，分枝定界法本质上还是枚举 法，只是在搜索整数解时是分区域搜索，即 所谓的分枝，对求最大值的问题，如果在某 个区域已经找
