（三） 分支定界法课件

学习重难点：分支定界法算法步骤

①分枝定界法分枝和定界的依据以及如何分枝和如何定界

分支定界法步骤：

1）求整数规划的松弛问题最优解；

  若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步；

2）分支与定界：

  任意选一个非整数解的变量xi，在松弛问题中加上约束：

xi≤[xi]   和   xi≥[xi]+1

组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。

  检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝，再检查，直到得到最优解。

整数规划-分支定界法

注：上述视频片段剪辑来源于哔哩哔哩睿智课堂发布

完成实验作业四，并上传至对应作业模块。