第二节分枝定界法

分枝定界法可用于求解一般的纯整数规划或混合整数规划问题，它是在20世纪60年代初由Land、Doig和Dakin等人提出的。由于该方法灵活且便于用计算机求解，所以现在已成为求解整数规划的重要方法。

分枝定界法的基本思路为：设有最大化的整数规划问题，与其对应的松弛问题为，先求解问题，若其最优解不符合的整数条件，那么的最优目标函数必是的最优目标函数的上界，记为，而的任意可行解的目标函数值将是的一个下界，分枝定界法就是通过将的可行域分成子区域即分枝，逐步减小和增大即定界，最终可求得。

分支定界法的求解步骤(目标函数为型)：

    (1)解松驰问题

先不考虑整数约束，解整数规划(IP)对应的松弛问题(LP)，可能得到以下情况之一：

①若(LP)没有可行解，则(IP)也没有可行解，停止计算。

②若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。

③若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。

    (2)定界

记(IP)的目标函数最优值为，以(LP)的最优目标函数值作为的上界，记为。再用观察法找(IP)的任一个整数可行解(一般可取)，并以其相应的目标函数值作为的下界，记为，则有：。

    (3)分枝

在(LP)的最优解中任选一个不符合整数条件的变量，例如(不为整数)，以[]表示不超过的最大整数。构造两个约束条件

和

将这两个约束条件分别加入问题(LP)，形成两个子问题(LP1)和(LP2)，并求解。

    (4)修改上、下界

按照以下两点规则进行修改：

①在各分枝问题中，找出目标函数值最大者作为新的上界；

②从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。

    (5)比较与剪枝

各分枝的目标函数值中，若有小于者，则剪掉此枝，表明此子问题已经探清，不必再分枝了；否则继续分枝。

如此反复进行，直到得到为止，即已得最优解。下面举例说明。

【例3.1】试用分支分界法求解下列整数规划。

解：先解对应的松弛问题为(LP)，先求解

运用单纯形法求得最优解，，对应的目标函数值。显然它不符合整数条件。这时是所求整数规划(IP)的最优目标函数值的上界，记作。而当显然是(IP)的一个整数可行解，这时，是的一个下界，记作，即。

选择(LP)的最优解中的一个分量进行分支(也可选择第二个分量)，对原问题增加两个约束条件和，可将原规划问题(LP)分为两个子问题(LP1)和(LP2)，给每枝增加一个约束条件。

解两个分支(LP1)和(LP2)，得到最优解为：

(LP1)的最优解：

(LP2)的最优解：

(LP1)的最优解符合整数条件，将其目标函数值“6”作为新的下界，将(LP2)的目标函数值“7.5”作为新的上界，至此，。

(LP1)已得整数解，即(IP1)在这一支的解已求出，所以无需再分支。继续对子问题(LP2)进行分枝，增加约束条件和，分为(LP3)和(LP4)。

解(IP3)和(IP4)对应的松驰问题(LP3)和(LP4)，得到的最优解为：

(LP3)的最优解：

(LP4)的最优解：无可行解。

两个分支中无符合整数条件的解，所以下界不变，(LP3)的目标函数值“7.33”小于已有的上界，因此将“7.33”作为新的上界。至此，。

因(LP4)无可行解，所以对(IP4)在这一支也无可行解，无需再分支。继续对子问题(IP3)进行分枝，增加约束条件和，分为(LP5)和(LP6)。

解(LP5)和(LP6)，得到的最优解为：

(LP5)的最优解：

(LP6)的最优解：无可行解。

(LP5)的最优解符合整数条件，将其目标函数值“7”作为新的下界，两支中没有比“7.5”大的目标函数值，所以原上界不变，至此，。

(LP5)已得整数解，即(IP5)在这一支的解已求出，所以无需再分支。因(LP6)无可行解，所以对(IP6)在这一支也无可行解，无需再分支。至此，所有分支均已结束，所以(LP5)的最优解为原整数规划的最优解，。上述分支定界求解的过程可用图3-1的分支树来表示。

图3-1 例3-1的分支树