分支定界算法流程图

A. 分支定界法的算法步骤

(1)求整数规划的松弛问题最优解。
(2)若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步。
(3)任意选一个非整数解的变量 ，在松弛问题中加上约束 及 +1组成两个新的松弛问题，称为分支。新的松弛问题具有如下特征：当原问题是求最大值时，目标值是分支问题的上界；当原问题足求最小值时，目标值是分支问题的下界。
(4)检查所有分支的解及目标函数值，若某分支的解是整数并且目标函数值大于(max)等于其他分支的目标值，则将其他分支剪去不再计算，若还存在非整数解并且目标值大于( max)整数解的目标值，需要继续分支，再检查，直到得到最优解。