分支定界法的算法

Ⅰ 分支定界法算法步骤

分支定界法的算法过程分为以下几步:

首先，第1步是放宽或取消原问题的部分限制条件，例如针对整数解的搜索。如果由此求得的最优解仍符合原问题的可行性，那么它即为原问题的最优解，算法至此结束。否则，这个解的函数值将成为原问题最优解的上界。

接着，进入第2步，将放宽限制后的问题分解为多个子问题，确保这些子问题的解集合包含原问题的所有可能解。对于每个子问题，寻找其最优解。如果子问题的最优解是原问题的可行解，那么找到了原问题的最优解，算法结束。否则，子问题的最优解函数值成为原问题的新上界。此外，还需关注子问题中与原问题有可行解的部分，取其最大目标函数值作为下界。

第3步，对于目标函数值小于下界的问题，由于其无原问题最优解的可能性，可以舍弃。而对于目标函数值大于下界的子问题，仍然保留，进入下一轮循环。

最后，第4步是选择所有保留子问题中目标函数值最大的一个，回到第1步，继续执行放宽限制和子问题分解。如果找到子问题的最优可行解，将其目标函数值与所有保留子问题中最大值比较，更新下界，然后返回第3步，直到找到原问题的最优解。

Ⅱ 特征选择 分支定界法

分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法.但与回溯算法不同,分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树。

分枝界限法也能够使用在混合整数规划问题上，其为一种系统化的解法，以一般线性规划之单形法解得最佳解后。

将非整数值之决策变量分割成为最接近的两个整数，分列条件，加入原问题中，形成两个子问题(或分枝)分别求解，如此便可求得目标函数值的上限（上界）或下限（下界），从其中寻得最佳解。

分支定界法算法分析：

1、算法优点：可以求得最优解、平均速度快。

因为从最小下界分支，每次算完限界后，把搜索树上当前所有的叶子结点的限界进行比较，找出限界最小的结点，此结点即为下次分支的结点。这种决策的优点是检查子问题较少，能较快的求得最佳解。

2、缺点：要存储很多叶子结点的限界和对应的耗费矩阵。花费很多内存空间。

存在的问题：分支定界法可应用于大量组合优化问题。其关键技术在于各结点权值如何估计，可以说一个分支定界求解方法的效率基本上由值界方法决定，若界估计不好，在极端情况下将与穷举搜索没多大区别。

Ⅲ 分支定界法的算法步骤

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