分支定界法：什么意思、基本思想、求解步骤、例子例题

分支定界法是在20世纪60年代初由Land Doig和Dakin等人提出的，由于该方法灵活，便于计算机求解，所以它是现在求解整数规划的重要方法。

它的基本思想是，先不考虑原整数规划问题中的整数性约束，去解其相应的松弛问题。对于最大化问题，松弛问题的最优值就是原问题最优值的上界。如果松弛问题的最优解满足整数性约束，则它就是原问题的最优解。

否则，就在不满足整数约束的变量中，任意选择 x i= b i ，设[ b i ]是不超过 b i 的最大整数，将新的约束条件 x i ≤[ b i ]和 x i ≥[ b i ]+1分别加入原问题中，把原问题分支为两个子问题，并分别求解子问题的松弛问题。

若子问题的松弛问题的最优解满足整数约束，则不再分支，其相应的目标函数值就是原问题目标函数值的一个下界。对不满足整数约束的子问题，如果需要，继续按上述方法进行新的分支，并分别求解其对应的松弛问题，直至求得原问题的最优解为止。

因此，我们总结 分支定界法的求解步骤 如下。

（1）先不考虑整数约束，求解整数规划的松弛问题，可能得到以下情况之一：

① 若松弛问题没有可行解，则整数规划也没有可行解，停止计算；

② 若松弛问题有最优解，并符合整数规划的整数条件，则线性规划的最优解即为整数规划的最优解，停止计算；

③ 若松弛问题有最优解，但不符合整数规划的整数条件，转入下一步。

（2） 分支 ：从不满足整数条件的基变量中任选一个 x i 进行分支，它必须满足 xi ≤[ x i ]或 x i ≥[ x i ]+1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题。

（3） 定界 ：把满足整数条件各分支的最优目标函数值作为上（下）界，用它来判断分支是保留还是剪支。

（4） 剪支 ：把那些子问题的最优值与界值比较，凡不优或不能更优的分支全剪掉，直到每个分支都查清为止。

例3-2-1 用分支定界法求解。

（1）用单纯形法可解得相应的松弛问题的最优解（1.2，2.1）， z =11.1，很明显，这个最优解不符合整数条件，我们需要继续分支，并把这个最优值定为各分支的上界。

（2）选择 x 1 =1.2来进行分支，加入条件 x 1 ≤1和 x 1 ≥2，得到两个子问题。

（3）用单纯形法求得 P 1 的最优解（1，2.25）， z =10.75， P 2 的最优解（2，0.5）， z =9.5。没有得到整数解，继续分支。对 P 1 进行分支，加入条件 x 2≤2和 x 2 ≥3，生出两个子问题。

（4）用单纯形法可解得相应的 P 3 的最优解（1，2）， z =10， P 4 的最优解（0，3）， z =9。 P 3 和 P 4 的解都是整数，比较它们对应的目标函数值，显然 P 3的目标函数值大于 P 4 ，剪去 P 4 一支，把 P 3 中 z =10作为目标函数的下界。

（5）我们回头看 P 2 ，在这一支中，可以继续分支以求得整数解。但这一支现在的最优值 z =9.5，也就是说，不管再怎么分，在这一支中求得的目标函数值不可能超过9.5，因此，也不可能超过 P 3 中求得的 z =10，因此将此支剪去。至此，我们得到了该整数规划的最优解 x 1 =1， x 2 =2， z =10。

用树形图（见图3-2-1）表示求解这个问题的全过程。