分支定界法的算法步骤

答案:1 悬赏:0 手机版

解决时间 2021-03-25 06:45

提问者网友：疯子也有疯子的情调
2021-03-24 12:23

分支定界法的算法步骤

最佳答案

五星知识达人网友：醉吻情书
2021-03-24 12:44

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

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息