3.2 分支定界法

在20世纪60年代初，Land Doig和Dakin等人提出了分支定界法。由于该方法灵活且便于用计算机求解，所以目前已成为解整数规划的重要方法之一。分支定界法既可用来解纯整数规划，也可用来解混合整数规划。

分支定界法的主要思路是首先求解整数规划的伴随规划，如果求得的最优解不符合整数条件，则增加新约束——缩小可行域；将原整数规划问题分支——分为两个子规划，再解子规划的伴随规划。通过求解一系列子规划的伴随规划及不断地定界，最后得到原整数规划问题的整数最优解。

3.2.1 分支定界的主要思路

下面结合一个例题来介绍分支定界法的主要思路。

例3.2 某公司计划建筑两种类型的宿舍。甲种每幢占地0.25 m×103 m，乙种每幢占地0.4 m×103 m。该公司拥有土地3 m×103 m。计划甲种宿舍不超过8幢，乙种宿舍不超过4幢。甲种宿舍每幢利润为10万元，乙种宿舍每幢利润为20万元。问该公司应计划甲、乙两种类型宿舍各建多少幢时能使公司获利最大？

解：设计划甲种宿舍建 x ₁ 幢，乙种宿舍建 x ₂ 幢。

本题数学模型为：

将其记为 A ，求解伴随问题 B （去掉 A 中的变量取整限定），得到：

若问题 B 无可行解，则问题 A 也无可行解，停止计算。若问题 B 的最优解 满足问题 A 的整数条件，则 也是问题 A 的最优解，停止计算。

（1）计算原问题 A 目标函数值的初始上界 。

因为问题 B 的最优解不满足整数条件，因此 不是问题的最优解， A 的可行域 K ₀ 和问题 B ₀ 的可行域 （见图3.1）的关系为 ，故问题 A 的最优值不会超过问题 B 的最优值，即有 。因此，可令 作为 z ^＊ 的初始上界 ，即 。

（2）计算原问题 A 目标函数值的初始下界 。

若能从问题 A 的约束条件中观察到一个整数可行解，则可将其目标函数值作为问题 A 目标函数值的初始下界，否则可令初始下界 。给定下界的目的，是希望在求解过程中寻找比当前 更好的原问题的目标函数值。

对于本例，很容易得到一个明显的可行解 X ＝（0，0） ^T ， z ＝0。问题 A 的最优目标函数值决不会比它小，故可令 。

（3）增加约束条件将原问题分支。

当 不满足整数条件时，在 中任选一个不符合整数条件的变量，如本例选 x ₁ ＝5.6，显然问题 A 的整数最优解只能是 x ₁ ≤5或 x ₂ ≥6，而绝不会在5与6之间。因此当将可行域 K ₀ 切去5＜ x ₁ ＜6部分时，并没有切去 A 的整数可行解。可以用分别增加约束条件 x ₁ ≤5及 x ₂ ≥6后， 分为 及 两部分，切去了5＜ x ₁ ＜6部分。问题 A ₀ 分为问题 A ₁ 及问题 A ₂ 两个子规划。

同一问题分解出的两个分支问题称为“一对分支”。做出问题 A ₁ ， A ₂ 的伴随规划 B ₁ ， B ₂ ，则问题 B ₁ ， B ₂ 的可行域为 K ₁ ， K ₂ ，如图3.2所示。

（4）分别求解一对分支。

在一般情况下，对某个分支问题（伴随规划）求解时，可能出现以下几种可能：

①无可行解。

若无可行解，说明该枝情况已查明，不需要由此分支再继续分支，称该分支为“树叶”。

②得到整数最优解。

若求得整数最优解，则该枝情况已查明，不需要再对此继续分支，该分支也是“树叶”。

③得到非整数最优解。

若求得某个分支问题得到的是不满足整数条件的最优解，还要区分两种情况：

a。该最优解的目标函数值 z 小于当前的下界 ，则该分支内不可能含有原问题的整数最优解，称为“枯枝”，需剪掉。

b。该最优解的目标函数值 z 大于当前的下界 ，则仍需对该枝继续分支，以查明该分支内是否有目标函数值比当前的 更好的整数最优解。

本例中问题 B ₁ 及问题 B ₂ 的模型及求解结果如下：

问题 B ₁ ， ， 的解是整数最优解，它也是问题 A 的整数可行解，故 A 的整数最优解 ，此时可将 修改为130，同时问题 B ₁ 也被查清，成为“树叶”。

问题 B ₂ ， ，不满足整数条件，故问题 A ₂ 分别增加约束条件： x ₂ ≤3及 x ₂ ≥4.$2.分为 A ₂₃ 与 A ₂₄ 两枝，建立相应的伴随规划 B ₂₁ 与 B ₂₂ 。

问题 B ₂₁ 的最优解 ， 问题 B ₂₂ 无可行解，此问题已是“树叶”，已被查清。

（5）修改上、下界 与 。

①修改下界

修改下界的时机是：每求出一个整数可行解时，都要做修改下界 的工作。修改下界 的原则：在至今所有计算出的整数可行解中，选目标函数值最大的那个作为最新下界。

因此在用分支定界法的求解全过程中，下界 是不断增大的。

本例中，未出现目标函数值大于原来的下界 。

②修改上界 。

上界 的修改时机是：每求解完一对分支，都要考虑修改上界。修改上界 的原则是：挑选在迄今为止所有未被分支的问题的目标函数值中最大的一个作为新的上界。新的上界 应该小于原来的上界。

本例中，因为 ，所以新的上界 。

在分支定界法的整个求解过程中，上界的值在不断减小。

因为 不满足整数条件，故问题 B ₂₁ 继续增加约束条件： x ₁ ≤7及 x ₁ ≥8，得 B ₂₁₁ 与 B ₂₁₂ 。

结果为 。

因为此时 B ₂₁₁ 的解为整数解，因此修改下界为 ，而此时所有未被分支的问题的目标函数值中最大的为 ，故修改上界 。

（6）结束准则。

当所有分支均已查明（或为无可行解“枯叶”，或为整数可行解“树叶”，或其目标函数值不大于下界 的“枯枝”），且此时 ，则已得到了原问题的整数最优解，即目标函数值为下界 的那个整数解。

在本例中， ，又 B ₂₁₁ 是“树叶”， B ₂₁₂ 为“枯枝”，因此所有分支均已查明。故已得到问题 A 的最优解： X ^＊ ＝（7，3） ^T 或（5，4） ^T ， z ^＊ ＝130。

故该公司应建甲种宿舍7幢，乙种宿舍3幢；或甲种5幢、乙种4幢时，获利最大，获利为130万元。

可将本例的求解过程与结果用图3.3来描述。

3.2.2 分支定界法的计算步骤

下面将分支定界法求解混合型整数规划的计算步骤归纳如下：

第1步：将原整数线性规划问题称为问题 A ₀ 。去掉问题 A ₀ 的整数条件，得到伴随规划问题 B ₀ 。

第2步：求解问题 B ₀ ，有以下几种可能：

（1） B ₀ 没有可行解，则 A ₀ 也没有可行解，停止计算。

（2）得到 B ₀ 的最优解，且满足问题 A ₀ 的整数条件，则 B ₀ 的最优解也是 A ₀ 的最优解，停止计算。

（3）得到不满足问题 A ₀ 的整数条件的 B ₀ 的最优解，记它的目标函数值为 ，这时需要对问题 A ₀ （从而对问题 B ₀ ）进行分支，转下一步。

第3步：确定初始上下界 与 。

以 作为上界 ，观察出问题 A ₀ 的一个整数可行解，将其目标函数值记为下界 若观察不到，则可记 ，转下一步。

第4步：将问题 B ₀ 分支。

在 B ₀ 的最优解 X ₀ 中，任选一个不符合整数条件的变量 x _j ，其值为 a _j ，以［ a _j ］表示小于 a _j 的最大整数。构造两个约束条件：

将这两个约束条件分别加到问题 B ₀ 的约束条件集中，得到 B ₀ 的两个分支：问题 B ₁ 与 B ₂ 。

对每个分支问题求解，得到以下几种可能：

（1）分支无可行解——该分支是“树叶”。

（2）求得该分支的最优解，且满足 A ₀ 的整数条件。将该最优解的目标函数值作为新的下界 ，该分支也是“树叶”。

（3）求得该分支的最优解，且不满足 A ₀ 的整数条件，但其目标函数值不大于当前下界 ，则该分支是“枯枝”，需要剪枝。

（4）求得不满足 A ₀ 整数条件的该分支的最优解，且其目标函数值大于当前下界 ，则该分支需要继续进行分支。

若得到的是前三种情形之一，表明该分支情况已探明，不需要继续分支。

若求解一对分支的结果表明这一对分支都需要继续分支，则可先对目标函数值大的那个分支进行分支计算，且沿着该分支一直继续进行下去，直到全部探明情况为止，再返过来求解目标函数值较小的那个分支。

第5步：修改上、下界。

（1）修改下界 ：每求出一次符合整数条件的可行解时，都要考虑修改下界 选择迄今为止最好的整数可行解相应的目标函数值作下界 。

（2）修改上界 ：每求解完一对分支，都要考虑修改上界 z ，上界的值应是迄今为止所有未被分支的问题的目标函数值中最大的一个。

在每解完一对分支、修改完上下界 和 后，若已有 ，此时所有分支均已查明，即得到了问题 A ₀ 的最优值 ，求解结束。若仍 ，则说明仍有分支没查明，需要继续分支，回到第4步。

习题

3.1 试用图解法讨论下列线性规划问题的最优解和最优整数解。

3.2 用分支定界法求解。