基于线性规划的零一背包问题的分支定界法求解示例

我将为您讲解如何使用基于线性规划的分支定界法求解经典的0-1背包问题。这是一个组合优化问题，在资源分配、投资决策等领域有广泛应用。

问题描述

0-1背包问题：给定n个物品，每个物品i有重量w_i和价值v_i，以及一个容量为C的背包。目标是从n个物品中选择一个子集放入背包，使得总重量不超过容量C，且总价值最大。

数学建模：

• 决策变量：x_i = 1表示选择物品i，x_i = 0表示不选择
• 目标函数：最大化总价值 ∑_{i=1}^n v_i x_i
• 约束条件：∑_{i=1}^n w_i x_i ≤ C
• 变量类型：x_i ∈ {0, 1}

这是一个NP-hard问题，但我们可以用基于线性规划的分支定界法有效求解。

解题过程详解

步骤1：线性规划松弛

分支定界法的核心思想是“分而治之”，但需要一个好的界限来剪枝。我们首先求解问题的线性规划松弛：

• 将整数约束x_i ∈ {0,1}松弛为连续约束0 ≤ x_i ≤ 1
• 求解这个线性规划得到最优解x^LP和目标值Z_LP
• 由于松弛后可行域变大，Z_LP是原整数规划最优值Z*的上界

重要性质：对于0-1背包问题，线性规划松弛的最优解有一个特殊结构：

• 将物品按单位价值v_i/w_i降序排列
• 按此顺序依次将物品装满背包，直到某个物品无法完全放入
• 最后一个物品可能取分数值（称为“断裂物品”或“临界物品”）

证明思路：
线性规划松弛等价于允许部分选取物品。显然，我们会优先选取单位价值高的物品，直到背包装满。这可以通过单纯形法或简单的贪心算法求解。

步骤2：分支定界框架

分支定界法需要维护：

1. 活跃节点列表：每个节点代表一个子问题（带有额外的约束）
2. 当前最优整数解（上界）和对应的目标值（下界）
3. 全局上界：所有活跃节点上界的最大值

算法流程：

初始化：将原问题（无额外约束）作为根节点加入活跃列表
当前最优解 = 空集，当前最优值 = -∞

while 活跃列表非空:
    1. 从活跃列表中选择一个节点（子问题）
    2. 求解该节点的线性规划松弛
    3. 如果松弛无可行解，剪枝（不可行剪枝）
    4. 如果松弛最优值 ≤ 当前最优值，剪枝（界限剪枝）
    5. 如果松弛解是整数解：
        如果其值 > 当前最优值，更新当前最优解和最优值
        剪枝（找到整数解）
    6. 否则（松弛解有分数变量）：
        选择一个分数变量x_j进行分支：
        创建两个子节点：
        左子节点：添加约束 x_j = 0
        右子节点：添加约束 x_j = 1
        将子节点加入活跃列表

步骤3：关键技术与优化

1. 变量选择策略（分支规则）：

   • 常用策略：选择分数值最接近0.5的变量
   • 对于背包问题，通常选择断裂物品或与之相邻的物品

2. 节点选择策略：

   • 深度优先：节省内存，快速找到可行解
   • 最佳上界优先：优先处理有希望的分支

3. 界限收紧：

   • 在分支前可以添加有效不等式（割平面）
   • 对于背包问题，可以添加覆盖不等式、背包覆盖不等式等

4. 预处理：

   • 去除明显无效的物品（w_i > C）
   • 合并相同性质的物品
   • 计算简单的上界和下界

步骤4：具体实例演示

考虑一个简单实例：

• 背包容量 C = 10
• 物品1：重量4，价值40
• 物品2：重量7，价值42
• 物品3：重量5，价值25
• 物品4：重量3，价值12

步骤4.1：计算单位价值并排序
物品1：40/4=10
物品2：42/7=6
物品3：25/5=5
物品4：12/3=4
排序：物品1 > 物品2 > 物品3 > 物品4

步骤4.2：求解根节点线性规划松弛

1. 选物品1：占用4，价值40
2. 选物品2：占用4+7=11>10，只能选部分
   剩余容量=10-4=6
   物品2可取分数6/7≈0.857
   价值增加42×(6/7)=36
3. 总价值=40+36=76
4. 松弛解：x₁=1, x₂=6/7, x₃=0, x₄=0
5. 上界=76

步骤4.3：分支过程

• 选择分数变量x₂进行分支

• 左分支：x₂=0

  • 解线性规划：选物品1(4,40)，剩余容量6
  • 选物品3(5,25)，但只能取6/5=1.2>1，实际只能取1
  • 但实际上x₃≤1，所以只能选物品3的1单位
  • 但物品3单位价值5<物品4单位价值4，这里需要重新计算：
    正确计算：x₂=0时，按单位价值排序：物品1→物品3→物品4→物品2
    选物品1后剩余6，物品3重5>6? 5<6，可以全选
    价值=40+25=65，剩余容量1
    物品4重3>1，只能取分数1/3
    价值增加12×(1/3)=4
    总价值=65+4=69
    解：x₁=1, x₂=0, x₃=1, x₄=1/3
    上界=69
  • 继续分支：选x₄（分数）

• 右分支：x₂=1

  • 已用重量7，剩余3
  • 只能选物品4（重量3，价值12）
  • 解：x₁=0, x₂=1, x₃=0, x₄=1
  • 总价值=42+12=54
  • 这是整数解！更新当前最优解：价值=54

步骤4.4：继续搜索
从x₂=0分支的节点继续：
当前节点上界=69>当前最优值54，继续
选择x₄分支：

• 左左分支：x₂=0, x₄=0

  • 已用：物品1(4)，剩余6
  • 选物品3(5)，价值25，剩余1
  • 物品2重7>1，不能选
  • 解：x₁=1, x₂=0, x₃=1, x₄=0
  • 总价值=40+25=65
  • 整数解，更新当前最优值=65>54

• 左右分支：x₂=0, x₄=1

  • 已用：物品1(4)+物品4(3)=7，剩余3
  • 物品3重5>3，不能选
  • 物品2重7>3，不能选
  • 解：x₁=1, x₂=0, x₃=0, x₄=1
  • 总价值=40+12=52
  • 整数解，但52<65，不更新

此时，所有节点要么被剪枝，要么已得整数解。最优解为x₁=1, x₂=0, x₃=1, x₄=0，总价值65。

算法分析

1. 时间复杂度：最坏情况是指数级的，但实际中分支定界法通常比穷举搜索高效得多
2. 空间复杂度：与活跃节点数成正比，通常用深度优先搜索控制
3. 优化效果：
   • 好的上界（线性规划松弛）能有效剪枝
   • 分支策略影响搜索树大小
   • 预处理能减小问题规模

实际应用中的扩展

1. 大规模问题：结合列生成（分支定价）或行生成（分支切割）
2. 近似解：在可接受时间内找到接近最优的解
3. 启发式：用贪心算法等快速得到好的下界
4. 并行化：不同分支可以在不同处理器上并行求解

这种基于线性规划的分支定界法是求解0-1背包问题最有效的方法之一，特别适合中等规模的问题。对于大规模问题，通常采用动态规划（当重量为整数且范围不大时）或近似算法。