列生成算法在背包问题中的应用示例

字数 2131 2025-10-26 21:06:54

列生成算法在背包问题中的应用示例

题目描述：考虑一个多重背包问题的变种，假设有5种物品，每种物品的数量无限，但背包容量有限（总容量为10）。每种物品的重量和价值如下表所示。目标是选择物品放入背包，使得总价值最大，且总重量不超过背包容量。

物品类型	重量	价值
1	2	5
2	3	8
3	4	10
4	5	12
5	6	15

这个问题可以建模为整数规划，但列生成算法通过将其松弛为线性规划，并动态生成列（即物品的装载模式）来高效求解。

解题过程：

问题建模：
定义决策变量 \(x_j\) 为使用物品类型 j 的次数。模型为：

\[ \begin{align} \max \quad & 5x_1 + 8x_2 + 10x_3 + 12x_4 + 15x_5 \\ \text{s.t.} \quad & 2x_1 + 3x_2 + 4x_3 + 5x_4 + 6x_5 \leq 10 \\ & x_j \geq 0, \quad x_j \in \mathbb{Z} \quad \text{（整数约束，但在列生成中先松弛为连续）} \end{align} \]

由于列生成适用于大规模问题，我们将其视为模式生成问题：每一列代表一个装载模式（即一组物品的组合）。

主问题与子问题：
- 主问题（Master Problem, MP）：选择最优的装载模式。设模式 p 的重量为 \(a_p\)，价值为 \(c_p\)，决策变量 \(\lambda_p\) 表示使用模式 p 的次数。模型为：

\[ \begin{align} \max \quad & \sum_p c_p \lambda_p \\ \text{s.t.} \quad & \sum_p a_p \lambda_p \leq 10 \\ & \lambda_p \geq 0 \end{align} \]

 初始模式可设为单个物品（如仅物品1、仅物品2等）。

子问题（Pricing Problem）：生成新模式。通过求解一个背包问题来找到 reduced cost 最大的模式。 reduced cost 公式为 \(\bar{c}_p = c_p - \pi a_p\)，其中 \(\pi\) 是主问题容量约束的对偶变量。

初始求解：
从简单模式开始，例如只包含一个物品的模式：
- 模式1: 物品1（重量2，价值5）
- 模式2: 物品2（重量3，价值8）
- 模式3: 物品3（重量4，价值10）
- 模式4: 物品4（重量5，价值12）
- 模式5: 物品5（重量6，价值15）
  求解主问题（线性规划松弛）：

\[ \begin{align} \max \quad & 5\lambda_1 + 8\lambda_2 + 10\lambda_3 + 12\lambda_4 + 15\lambda_5 \\ \text{s.t.} \quad & 2\lambda_1 + 3\lambda_2 + 4\lambda_3 + 5\lambda_4 + 6\lambda_5 \leq 10 \\ & \lambda_p \geq 0 \end{align} \]

最优解：选择模式5（价值15），但重量6小于10，剩余容量4。可加入模式3（价值10），总价值25。但需通过列生成优化。

迭代生成列：
- 第一次迭代：
  - 求解主问题得对偶变量 \(\pi\)（容量约束的影子价格）。假设初始解为仅使用模式5，则对偶值 \(\pi = 15/6 = 2.5\)。
  - 子问题：最大化 reduced cost \(\bar{c}_p = \sum_j (v_j - \pi w_j) y_j\)，其中 \(y_j\) 表示物品 j 在新模式中的数量。计算价值密度：
    - 物品1: \(5 - 2.5 \times 2 = 0\)
    - 物品2: \(8 - 2.5 \times 3 = 0.5\)
    - 物品3: \(10 - 2.5 \times 4 = 0\)
    - 物品4: \(12 - 2.5 \times 5 = -0.5\)
    - 物品5: \(15 - 2.5 \times 6 = 0\)
      最大 reduced cost 为物品2的0.5 > 0，故生成包含物品2的模式（重量3，价值8）。
  - 添加新模式到主问题，重新求解。新模式可能改善解。
收敛与终止：
重复步骤4，直到子问题中所有 reduced cost 非正（无改善模式）。最终主问题的解给出上界（对于最大化问题），若需整数解，可通过分支定界进一步处理。

通过列生成，仅生成少数模式即可逼近最优解，避免枚举所有组合，特别适合物品类型多的大规模问题。

列生成算法在背包问题中的应用示例题目描述：考虑一个多重背包问题的变种，假设有5种物品，每种物品的数量无限，但背包容量有限（总容量为10）。每种物品的重量和价值如下表所示。目标是选择物品放入背包，使得总价值最大，且总重量不超过背包容量。 | 物品类型 | 重量 | 价值 | |---------|------|------| | 1 | 2 | 5 | | 2 | 3 | 8 | | 3 | 4 | 10 | | 4 | 5 | 12 | | 5 | 6 | 15 | 这个问题可以建模为整数规划，但列生成算法通过将其松弛为线性规划，并动态生成列（即物品的装载模式）来高效求解。解题过程：问题建模：定义决策变量 \( x_ j \) 为使用物品类型 j 的次数。模型为： \[ \begin{align} \max \quad & 5x_ 1 + 8x_ 2 + 10x_ 3 + 12x_ 4 + 15x_ 5 \\ \text{s.t.} \quad & 2x_ 1 + 3x_ 2 + 4x_ 3 + 5x_ 4 + 6x_ 5 \leq 10 \\ & x_ j \geq 0, \quad x_ j \in \mathbb{Z} \quad \text{（整数约束，但在列生成中先松弛为连续）} \end{align} \] 由于列生成适用于大规模问题，我们将其视为模式生成问题：每一列代表一个装载模式（即一组物品的组合）。主问题与子问题：主问题（Master Problem, MP）：选择最优的装载模式。设模式 p 的重量为 \( a_ p \)，价值为 \( c_ p \)，决策变量 \( \lambda_ p \) 表示使用模式 p 的次数。模型为： \[ \begin{align} \max \quad & \sum_ p c_ p \lambda_ p \\ \text{s.t.} \quad & \sum_ p a_ p \lambda_ p \leq 10 \\ & \lambda_ p \geq 0 \end{align} \] 初始模式可设为单个物品（如仅物品1、仅物品2等）。子问题（Pricing Problem）：生成新模式。通过求解一个背包问题来找到 reduced cost 最大的模式。 reduced cost 公式为 \( \bar{c}_ p = c_ p - \pi a_ p \)，其中 \( \pi \) 是主问题容量约束的对偶变量。初始求解：从简单模式开始，例如只包含一个物品的模式：模式1: 物品1（重量2，价值5）模式2: 物品2（重量3，价值8）模式3: 物品3（重量4，价值10）模式4: 物品4（重量5，价值12）模式5: 物品5（重量6，价值15）求解主问题（线性规划松弛）： \[ \begin{align} \max \quad & 5\lambda_ 1 + 8\lambda_ 2 + 10\lambda_ 3 + 12\lambda_ 4 + 15\lambda_ 5 \\ \text{s.t.} \quad & 2\lambda_ 1 + 3\lambda_ 2 + 4\lambda_ 3 + 5\lambda_ 4 + 6\lambda_ 5 \leq 10 \\ & \lambda_ p \geq 0 \end{align} \] 最优解：选择模式5（价值15），但重量6小于10，剩余容量4。可加入模式3（价值10），总价值25。但需通过列生成优化。迭代生成列：第一次迭代：求解主问题得对偶变量 \( \pi \)（容量约束的影子价格）。假设初始解为仅使用模式5，则对偶值 \( \pi = 15/6 = 2.5 \)。子问题：最大化 reduced cost \( \bar{c}_ p = \sum_ j (v_ j - \pi w_ j) y_ j \)，其中 \( y_ j \) 表示物品 j 在新模式中的数量。计算价值密度：物品1: \( 5 - 2.5 \times 2 = 0 \) 物品2: \( 8 - 2.5 \times 3 = 0.5 \) 物品3: \( 10 - 2.5 \times 4 = 0 \) 物品4: \( 12 - 2.5 \times 5 = -0.5 \) 物品5: \( 15 - 2.5 \times 6 = 0 \) 最大 reduced cost 为物品2的0.5 > 0，故生成包含物品2的模式（重量3，价值8）。添加新模式到主问题，重新求解。新模式可能改善解。收敛与终止：重复步骤4，直到子问题中所有 reduced cost 非正（无改善模式）。最终主问题的解给出上界（对于最大化问题），若需整数解，可通过分支定界进一步处理。通过列生成，仅生成少数模式即可逼近最优解，避免枚举所有组合，特别适合物品类型多的大规模问题。