线性规划的分支定界法求解示例

题目描述：考虑整数线性规划问题：最大化目标函数 z = 3x₁ + 2x₂，约束条件为 2x₁ + x₂ ≤ 6；4x₁ + 5x₂ ≤ 20；x₁, x₂ ≥ 0，且 x₁, x₂ 为整数。

解题过程：

1. 问题理解与放松
   原问题是整数线性规划（ILP），变量需要取整数值。分支定界法的核心思想是，先解决对应的线性规划放松问题（LP relaxation），即暂时忽略整数约束（x₁, x₂ ≥ 0 且为实数）。如果放松问题的最优解自动满足整数条件，则该解也是原问题的最优解；否则，通过“分支”和“定界”逐步搜索整数解。

2. 求解线性规划放松问题
   忽略整数约束，用单纯形法求解放松问题：
   最大化 z = 3x₁ + 2x₂
   约束：
   2x₁ + x₂ ≤ 6
   4x₁ + 5x₂ ≤ 20
   x₁, x₂ ≥ 0
   通过单纯形法计算（过程略），得到最优解：x₁ = 2.5, x₂ = 1, 目标函数值 z = 10.5。
   由于 x₁ = 2.5 不是整数，需要分支。

3. 分支操作
   选择非整数变量 x₁ = 2.5 进行分支，生成两个子问题：

   • 子问题1：原约束 + x₁ ≤ 2（向下取整）
   • 子问题2：原约束 + x₁ ≥ 3（向上取整）
     这两个子问题覆盖了所有整数解的可能，且互斥。

4. 求解子问题1（x₁ ≤ 2）
   约束：2x₁ + x₂ ≤ 6, 4x₁ + 5x₂ ≤ 20, x₁ ≤ 2, x₁, x₂ ≥ 0。
   用单纯形法求解，得最优解：x₁ = 2, x₂ = 2, z = 10。
   该解满足整数约束，记录为当前最优整数解（incumbent），目标值 z = 10。

5. 求解子问题2（x₁ ≥ 3）
   约束：2x₁ + x₂ ≤ 6, 4x₁ + 5x₂ ≤ 20, x₁ ≥ 3, x₁, x₂ ≥ 0。
   将 x₁ ≥ 3 代入第一个约束 2x₁ + x₂ ≤ 6，得 x₂ ≤ 6 - 2×3 = 0，结合 x₂ ≥ 0，有 x₂ = 0。
   代入 x₁ ≥ 3 和 x₂ = 0 到第二个约束：4x₁ ≤ 20 → x₁ ≤ 5。
   取 x₁ = 3（最小整数满足 x₁ ≥ 3），得解 x₁ = 3, x₂ = 0, z = 9。
   该解为整数解，但 z = 9 < 10（当前最优），故被剪枝（不会产生更优解）。

6. 定界与剪枝

   • 子问题1的整数解 z = 10 为当前上界（对于整数解，实际是最优值）。
   • 子问题2的整数解 z = 9 小于 10，被剪枝。
     由于所有分支已探索完毕，算法终止。

7. 最终结果
   最优整数解为 x₁ = 2, x₂ = 2，目标函数最大值 z = 10。
   分支定界法通过系统分割解空间，利用界限排除非优分支，高效找到了整数解。