分支定界法

求解整数规划时，如果可行域是有界的,首先容易想到的方法就是穷举变量的所有可行的整数组合，对于变量数较小的情况，这种方法是可行的，也是有效的。对于大型问题,可行的整数组合数是很大的，穷举法是不可取的。我们一般仅检查可行的整数组合的一部分,就能定出最优的整数解。分支定界法(branch and bound method)就是其中一种。分支定界法可用于解纯整数或混合的整数规划问题。在20世纪60年代由Land Dakin和Dakin等人提出。由于这方法灵活且便于计算机求解，所以现在它已是解整数规划的重要方法。

设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界,记作z;而A的任意可行解的目标函数值将是z*的一个下界

Z。分枝定界法就是将B的可行域分成子区域(称为分支)的方法，逐步减小

z和

增大Z, 最终求到z。

下面以实例来说明算法的步骤：

*例1 求解下面整数规划

解：先不考虑条件⑸，求解相应的线性规划问题L，得最优解

x1=4.81，x2 =1.82，z0 =356（见图）

该解不是整数解。选择其中一个非整数变量，如x1=4.81，对问题L分别增加约束条件： ≤4，

≥5 将问题L分解为两个子问题

、

，

（分枝），也就是去掉问题L不含整数解的一部分可

行域，将原可行域D变为两部分（如图）

因为没有得到整数解，所以继续对L1进行分解，增加约束： 并求得最优解如下：

≤2，≥3 将分解成问题与，

问题的解已是整数解，它的目标值

的目标值≥2 将

大于

，分解

与

分解成问题

=340，大于问题L4的目标值，所以问题，并求解，结果如下：

已无必要再分枝。但

分枝。增加约束

由于问题≤1，

还有可能产生更好的整数解，因此继续对

问题的，所以不必分解了；问题

=2.00即为最优整数解。

无可行解，于是可以断定问题的解：

=4.00，

整个分枝定界过程如下图所示：

用分枝定界法求解整数规划的步骤可总结如下：

步骤1：求解与整数规划相对应的线性规划L，若L无可行解，则整数规划也没有可行解，计算停；若L的最优解是整数解，则该解即为整数规划的最优解，计算停；若L的最优解不是整数解，则转步骤2。

步骤2（分枝）在L的最优解中任选一个不符合整数条件的变量

的最大整数，构造两个约束条件

将这两个约束条件分别加在问题L的约束条件上，形成两个子问题枝

，若它的最优解不是整数解，且

＞Z，则重复步骤2，若

，其值为

和

，并求解

和

为小于

。

步骤3（定界 ）取整数解中最大目标值为界限值Z(下界)，如果计算中尚无整数解，则取Z=-∞。检查分

≤Z，则

不再分枝。重复步骤2、

步骤3，直至所有分枝都不能再分解为止，这时界限值Z对应的整数解即为原问题的最优解。 用分枝定界法可解纯整数规划问题和混合整数规划问题。它比穷举法优越，因为它仅在一部分可行的整数解中寻求最优解，计算量比穷举法小。若变量数目很大，其计算工作量也是相当可观的。