列生成算法在多重背包问题中的应用示例
字数 2697 2025-11-01 09:19:03

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

题目描述
考虑一个多重背包问题：有 \(n\) 类物品，第 \(i\) 类物品的价值为 \(p_i\)，重量为 \(w_i\)，且数量为 \(b_i\)（即最多可选取 \(b_i\) 个）。背包容量为 \(C\)。目标是在不超过背包容量的前提下，选择若干物品（每类物品可选多个），使得总价值最大。

该问题可建模为整数规划：

\[\max \sum_{i=1}^n p_i x_i \]

\[\text{s.t.} \quad \sum_{i=1}^n w_i x_i \leq C, \quad 0 \leq x_i \leq b_i, \quad x_i \in \mathbb{Z}^+ \]

其中 \(x_i\) 表示选择第 \(i\) 类物品的数量。当 \(n\) 或 \(b_i\) 较大时，直接求解计算成本高。列生成算法通过将问题分解为主问题（限制主问题）和子问题（定价问题），动态生成有价值的列（即变量）来高效求解其线性松弛。

解题过程

步骤1：构建主问题与初始列集合

  1. 主问题的线性松弛形式为：

\[ \max \sum_{i=1}^n \sum_{k=1}^{b_i} p_i y_{ik} \]

\[ \text{s.t.} \quad \sum_{i=1}^n \sum_{k=1}^{b_i} w_i y_{ik} \leq C, \quad \sum_{k=1}^{b_i} y_{ik} \leq 1 \ (\forall i), \quad 0 \leq y_{ik} \leq 1 \]

其中 \(y_{ik}\) 表示是否选择第 \(i\) 类物品的第 \(k\) 个副本（\(k=1,\dots,b_i\)）。此模型包含大量变量（尤其当 \(b_i\) 大时），因此采用列生成法仅维护部分变量（列）的集合。

  1. 初始列集合：为每类物品添加一个“空列”（即 \(y_{i1}=0\)），或选择一组可行初始解（如每类物品选0个）。

步骤2：求解限制主问题

  1. 限制主问题（RMP）是主问题仅考虑当前列集合的简化版本。
  2. 使用单纯形法求解RMP的线性松弛，得到最优解和对应的对偶变量：
    • 设容量约束的对偶变量为 \(\pi\)（标量）。
    • 每类物品的数量约束 \(\sum_{k} y_{ik} \leq 1\) 的对偶变量为 \(\sigma_i\)（共 \(n\) 个）。

步骤3：子问题（检验列是否可进基）

  1. 子问题目标：寻找减少成本（reduced cost）为负的列。对于第 \(i\) 类物品，若新增一个副本 \(k\)，其减少成本为：

\[ \bar{c}_{ik} = p_i - \pi w_i - \sigma_i \]

由于同类物品的副本同质，可简化为对每类物品 \(i\)，计算其单位减少成本：

\[ \bar{c}_i = p_i - \pi w_i \]

但需注意 \(\sigma_i\) 已隐含在RMP的约束中，实际子问题需求解：

\[ \max_i \left\{ \bar{c}_i - \sigma_i \right\} \]

更精确地，子问题是寻找使 \(\bar{c}_i - \sigma_i > 0\) 的物品 \(i\)。若存在多个，选择最大正值对应的物品。

  1. 子问题求解：
    • 遍历所有物品 \(i=1,\dots,n\)，计算 \(\bar{c}_i = p_i - \pi w_i\)。
    • 若 \(\bar{c}_i - \sigma_i > 0\)，则表明新增第 \(i\) 类物品的副本可能改善目标函数。
    • 选择使 \(\bar{c}_i - \sigma_i\) 最大的物品 \(i^*\)，将其对应的列（即增加一个该物品的副本）加入RMP。

步骤4：迭代与终止

  1. 将新列加入RMP，重新求解RMP，更新对偶变量 \(\pi\) 和 \(\sigma_i\)。
  2. 重复步骤3，直到所有物品满足 \(\bar{c}_i - \sigma_i \leq 0\)（即无减少成本为正的列）。此时得到原问题线性松弛的最优解。
  3. 若解为整数，则即为整数最优解；否则需结合分支定界法（生成整数解）。

示例演示
假设 \(n=2\)，背包容量 \(C=10\)，物品参数：

  • 物品1：\(p_1=5, w_1=3, b_1=2\)
  • 物品2：\(p_2=4, w_2=2, b_2=3\)

迭代1：

  • 初始RMP仅包含空列（\(x_1=0, x_2=0\)），解为 \(y_{11}=0, y_{21}=0\)，目标值=0，对偶变量 \(\pi=0, \sigma_1=0, \sigma_2=0\)。
  • 子问题：计算 \(\bar{c}_1 = 5-0=5\)，\(\bar{c}_2=4-0=4\)。选择物品1（\(\bar{c}_1-\sigma_1=5>0\)），添加其列到RMP。

迭代2：

  • RMP解为选1个物品1（价值5，重量3），对偶变量 \(\pi=5/3, \sigma_1=0\)。
  • 子问题：\(\bar{c}_1=5-(5/3)×3=0\)，\(\bar{c}_2=4-(5/3)×2=2/3>0\)。选择物品2，添加其列。

迭代3：

  • RMP解为选1个物品1和1个物品2（总价值9，重量5），对偶变量更新。
  • 子问题：计算所有 \(\bar{c}_i-\sigma_i \leq 0\)，终止。线性松弛最优解为 \(x_1=1, x_2=1\)，剩余容量可继续添加物品2（但受 \(\sigma_i\) 约束限制）。

最终整数解可通过调整得到：容量10可容纳 \(x_1=2, x_2=2\)（总价值18），但需验证是否满足数量约束（\(x_1 \leq 2, x_2 \leq 3\)），此处为可行解。

关键点

  • 列生成通过动态添加列避免枚举所有变量，特别适合 \(b_i\) 大的场景。
  • 子问题利用对偶信息识别有潜力的物品，减少计算量。
  • 最终需结合整数规划方法得到精确整数解。
列生成算法在多重背包问题中的应用示例 题目描述 考虑一个多重背包问题：有 \( n \) 类物品，第 \( i \) 类物品的价值为 \( p_ i \)，重量为 \( w_ i \)，且数量为 \( b_ i \)（即最多可选取 \( b_ i \) 个）。背包容量为 \( C \)。目标是在不超过背包容量的前提下，选择若干物品（每类物品可选多个），使得总价值最大。 该问题可建模为整数规划： \[ \max \sum_ {i=1}^n p_ i x_ i \] \[ \text{s.t.} \quad \sum_ {i=1}^n w_ i x_ i \leq C, \quad 0 \leq x_ i \leq b_ i, \quad x_ i \in \mathbb{Z}^+ \] 其中 \( x_ i \) 表示选择第 \( i \) 类物品的数量。当 \( n \) 或 \( b_ i \) 较大时，直接求解计算成本高。列生成算法通过将问题分解为 主问题（限制主问题） 和 子问题（定价问题） ，动态生成有价值的列（即变量）来高效求解其线性松弛。 解题过程 步骤1：构建主问题与初始列集合 主问题的线性松弛形式为： \[ \max \sum_ {i=1}^n \sum_ {k=1}^{b_ i} p_ i y_ {ik} \] \[ \text{s.t.} \quad \sum_ {i=1}^n \sum_ {k=1}^{b_ i} w_ i y_ {ik} \leq C, \quad \sum_ {k=1}^{b_ i} y_ {ik} \leq 1 \ (\forall i), \quad 0 \leq y_ {ik} \leq 1 \] 其中 \( y_ {ik} \) 表示是否选择第 \( i \) 类物品的第 \( k \) 个副本（\( k=1,\dots,b_ i \)）。此模型包含大量变量（尤其当 \( b_ i \) 大时），因此采用列生成法仅维护部分变量（列）的集合。 初始列集合：为每类物品添加一个“空列”（即 \( y_ {i1}=0 \)），或选择一组可行初始解（如每类物品选0个）。 步骤2：求解限制主问题 限制主问题（RMP）是主问题仅考虑当前列集合的简化版本。 使用单纯形法求解RMP的线性松弛，得到最优解和对应的对偶变量： 设容量约束的对偶变量为 \( \pi \)（标量）。 每类物品的数量约束 \( \sum_ {k} y_ {ik} \leq 1 \) 的对偶变量为 \( \sigma_ i \)（共 \( n \) 个）。 步骤3：子问题（检验列是否可进基） 子问题目标：寻找减少成本（reduced cost）为负的列。对于第 \( i \) 类物品，若新增一个副本 \( k \)，其减少成本为： \[ \bar{c}_ {ik} = p_ i - \pi w_ i - \sigma_ i \] 由于同类物品的副本同质，可简化为对每类物品 \( i \)，计算其 单位减少成本 ： \[ \bar{c}_ i = p_ i - \pi w_ i \] 但需注意 \( \sigma_ i \) 已隐含在RMP的约束中，实际子问题需求解： \[ \max_ i \left\{ \bar{c}_ i - \sigma_ i \right\} \] 更精确地，子问题是寻找使 \( \bar{c}_ i - \sigma_ i > 0 \) 的物品 \( i \)。若存在多个，选择最大正值对应的物品。 子问题求解： 遍历所有物品 \( i=1,\dots,n \)，计算 \( \bar{c}_ i = p_ i - \pi w_ i \)。 若 \( \bar{c}_ i - \sigma_ i > 0 \)，则表明新增第 \( i \) 类物品的副本可能改善目标函数。 选择使 \( \bar{c}_ i - \sigma_ i \) 最大的物品 \( i^* \)，将其对应的列（即增加一个该物品的副本）加入RMP。 步骤4：迭代与终止 将新列加入RMP，重新求解RMP，更新对偶变量 \( \pi \) 和 \( \sigma_ i \)。 重复步骤3，直到所有物品满足 \( \bar{c}_ i - \sigma_ i \leq 0 \)（即无减少成本为正的列）。此时得到原问题线性松弛的最优解。 若解为整数，则即为整数最优解；否则需结合分支定界法（生成整数解）。 示例演示 假设 \( n=2 \)，背包容量 \( C=10 \)，物品参数： 物品1：\( p_ 1=5, w_ 1=3, b_ 1=2 \) 物品2：\( p_ 2=4, w_ 2=2, b_ 2=3 \) 迭代1 ： 初始RMP仅包含空列（\( x_ 1=0, x_ 2=0 \)），解为 \( y_ {11}=0, y_ {21}=0 \)，目标值=0，对偶变量 \( \pi=0, \sigma_ 1=0, \sigma_ 2=0 \)。 子问题：计算 \( \bar{c}_ 1 = 5-0=5 \)，\( \bar{c}_ 2=4-0=4 \)。选择物品1（\( \bar{c}_ 1-\sigma_ 1=5>0 \)），添加其列到RMP。 迭代2 ： RMP解为选1个物品1（价值5，重量3），对偶变量 \( \pi=5/3, \sigma_ 1=0 \)。 子问题：\( \bar{c}_ 1=5-(5/3)×3=0 \)，\( \bar{c}_ 2=4-(5/3)×2=2/3>0 \)。选择物品2，添加其列。 迭代3 ： RMP解为选1个物品1和1个物品2（总价值9，重量5），对偶变量更新。 子问题：计算所有 \( \bar{c}_ i-\sigma_ i \leq 0 \)，终止。线性松弛最优解为 \( x_ 1=1, x_ 2=1 \)，剩余容量可继续添加物品2（但受 \( \sigma_ i \) 约束限制）。 最终整数解可通过调整得到：容量10可容纳 \( x_ 1=2, x_ 2=2 \)（总价值18），但需验证是否满足数量约束（\( x_ 1 \leq 2, x_ 2 \leq 3 \)），此处为可行解。 关键点 列生成通过动态添加列避免枚举所有变量，特别适合 \( b_ i \) 大的场景。 子问题利用对偶信息识别有潜力的物品，减少计算量。 最终需结合整数规划方法得到精确整数解。