如何有分枝定界法解指派问题

分枝定界法（branch and bound）是一种求解非线性整数规划问题的常用算法.这种方法不但可以求解纯整数规划,还可以求解混合整数规划问题.

分枝定界法的步骤如下：

Step 1 放宽或取消原问题的某些约束条件,如求整数解的条件.如果这是求出的最优解是原问题的可行解,那么这个解就是原问题的最优解,计算结束.否则这个解的目标函数值是原问题的最优解的上界（求极大值时）.

Step 2 将放宽了某些约束条件的替代问题分成若干子问题,要求各子问题的解集合的并集要包含原问题的所有可行解,然后对每个子问题求最优解.这些子问题的最优解中的最优者若是原问题的可行解,则它就是原问题的最优解,计算结束.否则它的目标函数值就是原问题的一个新的上界.另外,各子问配大题的最优解中,若有为原问题的可行解的,选这些可行解缓裂的最大的目标函数值,它就是原问题最优解的一个下界.

Step 3 对最优解的目标函数值已小于这个下界的问题,其可行解中必无原问题的最优解,可以放弃.对最优解的目标函数值大于这个下界的子问题,都先保留下来,进入Step 4 .

Step 4 在保留下的所有子问题中,选出最扰卖闭优解的目标函数值最大的一个,重复Step 1 和Step 2 .如果已经找到该子问题的最优可行解,那么用其目标函数值与前面保留的其他问题在内的所有子问题的可行解中目标函数值最大者,将它作为新的下界,重复Step 3 ,直到求出最优解.

以上就是分支定界法的主要步骤.

(1)求整数规划的松弛问题最优解。

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

(3)任意选一个非整数解的变量 ，在松弛问题中加上约束 及 +1组成两个新的松弛问题，称为分支。新的松弛问题具有如下特征：当原问题是求最大值时，目标值是分支问题的上界；当原培世问题郑缓足求最小值时，目标值是分支问题的下界。

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

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

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

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

分支定此伍滚界法算法分析：

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

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

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

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

---