列生成算法在切割库存问题中的应用示例
字数 3130 2025-10-26 09:00:43

列生成算法在切割库存问题中的应用示例

题目描述
假设一家造纸厂生产宽度为200厘米的原料纸卷，客户需要订购以下尺寸的小纸卷：

  • 40厘米：30卷
  • 50厘米：50卷
  • 70厘米：20卷

小纸卷需通过切割大纸卷（200厘米）得到，目标是最小化使用的大纸卷数量。一种切割方案需满足：

  1. 切割后的小纸卷总宽度不超过200厘米；
  2. 每种小纸卷的切割数量为非负整数。

这是经典的一维切割库存问题，可转化为线性规划模型，并通过列生成算法高效求解。

解题过程

1. 问题建模

设所有可行的切割方案构成集合 \(S\)，每种方案 \(j \in S\) 对应一个向量 \(a_j = (a_{1j}, a_{2j}, a_{3j})\)，其中 \(a_{ij}\) 表示在方案 \(j\) 中切割出第 \(i\) 种小纸卷的数量（\(i=1,2,3\) 分别对应40cm、50cm、70cm）。
决策变量 \(x_j\) 表示采用方案 \(j\) 的大纸卷数量。模型为：

\[\begin{align} \min \quad & \sum_{j \in S} x_j \\ \text{s.t.} \quad & \sum_{j \in S} a_{ij} x_j \geq d_i, \quad i=1,2,3 \\ & x_j \geq 0, \quad x_j \in \mathbb{Z} \quad (\text{整数约束暂缓，先解线性松弛}) \end{align} \]

其中 \(d = (30, 50, 20)\) 是需求量。
难点：\(S\) 的规模可能极大（例如200cm可切割出多种组合），无法枚举所有列。

2. 列生成算法框架

列生成将问题分解为：

  • 主问题（Master Problem, MP）：包含部分初始列的线性规划。
  • 子问题（Pricing Problem）：生成负检验数的列（即可能改善目标的新切割方案）。

步骤流程：

  1. 构造初始可行列集合（如简单切割方案）。
  2. 求解主问题的线性松弛。
  3. 通过子问题判断是否存在可改善目标的列：
    • 若存在，添加该列到主问题，返回步骤2。
    • 若不存在，当前解即松弛最优解。
  4. 对解取整（需结合分支定界，此处仅讨论线性松弛）。

3. 初始主问题的构建

初始列应保证主问题可行。例如：

  • 方案1：仅切割40cm卷，最多切 \(\lfloor 200/40 \rfloor = 5\) 卷，即 \(a_1 = (5,0,0)\)
  • 方案2：仅切割50cm卷，\(a_2 = (0,4,0)\)
  • 方案3：仅切割70cm卷，\(a_3 = (0,0,2)\)
    初始主问题为：

\[\begin{align} \min \quad & x_1 + x_2 + x_3 \\ \text{s.t.} \quad & 5x_1 + 0x_2 + 0x_3 \geq 30 \\ & 0x_1 + 4x_2 + 0x_3 \geq 50 \\ & 0x_1 + 0x_2 + 2x_3 \geq 20 \\ & x_1, x_2, x_3 \geq 0 \end{align} \]

4. 第一次迭代

求解主问题得：

  • 最优解 \(x_1 = 6, x_2 = 12.5, x_3 = 10\)，目标值 \(= 28.5\)
  • 对偶变量值 \(\pi_1 = 0.2, \pi_2 = 0.25, \pi_3 = 0.5\)（由约束的边际成本得出）。

子问题：寻找检验数为负的列，即求新方案 \(a = (a_1, a_2, a_3)\) 使得：

\[\text{检验数} = 1 - \sum_{i=1}^3 \pi_i a_i < 0 \quad \Rightarrow \quad \sum_{i=1}^3 \pi_i a_i > 1 \]

同时满足切割可行性：

\[40a_1 + 50a_2 + 70a_3 \leq 200, \quad a_i \in \mathbb{Z}^+ \]

子问题转化为整数背包问题：最大化 \(0.2a_1 + 0.25a_2 + 0.5a_3\)。
枚举可能组合（或动态规划求解），例如：

  • 方案 \(a = (0,0,2)\)：价值 \(0.5 \times 2 = 1.0\)，不满足 \(>1\)
  • 方案 \(a = (1,0,2)\)：宽度 \(40+140=180 \leq 200\)，价值 \(0.2+1.0=1.2 > 1\)
    检验数 \(1 - 1.2 = -0.2 < 0\)，故此为可改善的列。

5. 第二次迭代

添加列 \(a_4 = (1,0,2)\) 到主问题：

\[\begin{align} \min \quad & x_1 + x_2 + x_3 + x_4 \\ \text{s.t.} \quad & 5x_1 + 0x_2 + 0x_3 + 1x_4 \geq 30 \\ & 0x_1 + 4x_2 + 0x_3 + 0x_4 \geq 50 \\ & 0x_1 + 0x_2 + 2x_3 + 2x_4 \geq 20 \\ & x_j \geq 0 \end{align} \]

求解得 \(x_1 = 5, x_2 = 12.5, x_3 = 0, x_4 = 5\)，目标值 \(= 22.5\)。
对偶变量 \(\pi_1 = 0.2, \pi_2 = 0.25, \pi_3 = 0.4\)。

子问题：最大化 \(0.2a_1 + 0.25a_2 + 0.4a_3\)。
尝试方案 \(a = (0,4,0)\)：价值 \(1.0\)（已有）；
方案 \(a = (3,1,1)\)：宽度 \(120+50+70=240 > 200\) 不可行；
方案 \(a = (1,2,1)\)：宽度 \(40+100+70=210 > 200\) 不可行；
方案 \(a = (0,2,1)\)：宽度 \(100+70=170 \leq 200\)，价值 \(0.25 \times 2 + 0.4 = 0.9 < 1\)，无改善列。

6. 第三次迭代

继续搜索：方案 \(a = (2,0,1)\)：宽度 \(80+70=150 \leq 200\)，价值 \(0.4+0.4=0.8 < 1\)；
方案 \(a = (0,1,2)\)：宽度 \(50+140=190 \leq 200\)，价值 \(0.25+0.8=1.05 > 1\)，检验数 \(-0.05\)。
添加列 \(a_5 = (0,1,2)\) 到主问题，求解得目标值 \(\approx 22.37\)。

重复子问题直到无负检验数列，最终松弛最优解约需 \(22.2\) 个大卷（实际需取整）。

7. 算法总结

  • 优势：避免枚举所有列，通过动态生成列处理大规模问题。
  • 应用：切割库存、航班调度等组合优化问题。
  • 扩展：得到松弛解后，需结合分支定界得到整数解（即分支定价算法）。

本例中，列生成通过求解子问题不断改进主问题，逐步逼近最优解，展示了如何用线性规划处理整数规划问题的高效技巧。

列生成算法在切割库存问题中的应用示例 题目描述 假设一家造纸厂生产宽度为200厘米的原料纸卷，客户需要订购以下尺寸的小纸卷： 40厘米：30卷 50厘米：50卷 70厘米：20卷 小纸卷需通过切割大纸卷（200厘米）得到，目标是最小化使用的大纸卷数量。一种切割方案需满足： 切割后的小纸卷总宽度不超过200厘米； 每种小纸卷的切割数量为非负整数。 这是经典的 一维切割库存问题 ，可转化为线性规划模型，并通过列生成算法高效求解。 解题过程 1. 问题建模 设所有可行的切割方案构成集合 \( S \)，每种方案 \( j \in S \) 对应一个向量 \( a_ j = (a_ {1j}, a_ {2j}, a_ {3j}) \)，其中 \( a_ {ij} \) 表示在方案 \( j \) 中切割出第 \( i \) 种小纸卷的数量（\( i=1,2,3 \) 分别对应40cm、50cm、70cm）。 决策变量 \( x_ j \) 表示采用方案 \( j \) 的大纸卷数量。模型为： \[ \begin{align} \min \quad & \sum_ {j \in S} x_ j \\ \text{s.t.} \quad & \sum_ {j \in S} a_ {ij} x_ j \geq d_ i, \quad i=1,2,3 \\ & x_ j \geq 0, \quad x_ j \in \mathbb{Z} \quad (\text{整数约束暂缓，先解线性松弛}) \end{align} \] 其中 \( d = (30, 50, 20) \) 是需求量。 难点：\( S \) 的规模可能极大（例如200cm可切割出多种组合），无法枚举所有列。 2. 列生成算法框架 列生成将问题分解为： 主问题（Master Problem, MP） ：包含部分初始列的线性规划。 子问题（Pricing Problem） ：生成负检验数的列（即可能改善目标的新切割方案）。 步骤流程 ： 构造初始可行列集合（如简单切割方案）。 求解主问题的线性松弛。 通过子问题判断是否存在可改善目标的列： 若存在，添加该列到主问题，返回步骤2。 若不存在，当前解即松弛最优解。 对解取整（需结合分支定界，此处仅讨论线性松弛）。 3. 初始主问题的构建 初始列应保证主问题可行。例如： 方案1：仅切割40cm卷，最多切 \( \lfloor 200/40 \rfloor = 5 \) 卷，即 \( a_ 1 = (5,0,0) \) 方案2：仅切割50cm卷，\( a_ 2 = (0,4,0) \) 方案3：仅切割70cm卷，\( a_ 3 = (0,0,2) \) 初始主问题为： \[ \begin{align} \min \quad & x_ 1 + x_ 2 + x_ 3 \\ \text{s.t.} \quad & 5x_ 1 + 0x_ 2 + 0x_ 3 \geq 30 \\ & 0x_ 1 + 4x_ 2 + 0x_ 3 \geq 50 \\ & 0x_ 1 + 0x_ 2 + 2x_ 3 \geq 20 \\ & x_ 1, x_ 2, x_ 3 \geq 0 \end{align} \] 4. 第一次迭代 求解主问题得： 最优解 \( x_ 1 = 6, x_ 2 = 12.5, x_ 3 = 10 \)，目标值 \( = 28.5 \) 对偶变量值 \( \pi_ 1 = 0.2, \pi_ 2 = 0.25, \pi_ 3 = 0.5 \)（由约束的边际成本得出）。 子问题 ：寻找检验数为负的列，即求新方案 \( a = (a_ 1, a_ 2, a_ 3) \) 使得： \[ \text{检验数} = 1 - \sum_ {i=1}^3 \pi_ i a_ i < 0 \quad \Rightarrow \quad \sum_ {i=1}^3 \pi_ i a_ i > 1 \] 同时满足切割可行性： \[ 40a_ 1 + 50a_ 2 + 70a_ 3 \leq 200, \quad a_ i \in \mathbb{Z}^+ \] 子问题转化为 整数背包问题 ：最大化 \( 0.2a_ 1 + 0.25a_ 2 + 0.5a_ 3 \)。 枚举可能组合（或动态规划求解），例如： 方案 \( a = (0,0,2) \)：价值 \( 0.5 \times 2 = 1.0 \)，不满足 \( >1 \) 方案 \( a = (1,0,2) \)：宽度 \( 40+140=180 \leq 200 \)，价值 \( 0.2+1.0=1.2 > 1 \) 检验数 \( 1 - 1.2 = -0.2 < 0 \)，故此为可改善的列。 5. 第二次迭代 添加列 \( a_ 4 = (1,0,2) \) 到主问题： \[ \begin{align} \min \quad & x_ 1 + x_ 2 + x_ 3 + x_ 4 \\ \text{s.t.} \quad & 5x_ 1 + 0x_ 2 + 0x_ 3 + 1x_ 4 \geq 30 \\ & 0x_ 1 + 4x_ 2 + 0x_ 3 + 0x_ 4 \geq 50 \\ & 0x_ 1 + 0x_ 2 + 2x_ 3 + 2x_ 4 \geq 20 \\ & x_ j \geq 0 \end{align} \] 求解得 \( x_ 1 = 5, x_ 2 = 12.5, x_ 3 = 0, x_ 4 = 5 \)，目标值 \( = 22.5 \)。 对偶变量 \( \pi_ 1 = 0.2, \pi_ 2 = 0.25, \pi_ 3 = 0.4 \)。 子问题 ：最大化 \( 0.2a_ 1 + 0.25a_ 2 + 0.4a_ 3 \)。 尝试方案 \( a = (0,4,0) \)：价值 \( 1.0 \)（已有）； 方案 \( a = (3,1,1) \)：宽度 \( 120+50+70=240 > 200 \) 不可行； 方案 \( a = (1,2,1) \)：宽度 \( 40+100+70=210 > 200 \) 不可行； 方案 \( a = (0,2,1) \)：宽度 \( 100+70=170 \leq 200 \)，价值 \( 0.25 \times 2 + 0.4 = 0.9 < 1 \)，无改善列。 6. 第三次迭代 继续搜索：方案 \( a = (2,0,1) \)：宽度 \( 80+70=150 \leq 200 \)，价值 \( 0.4+0.4=0.8 < 1 \)； 方案 \( a = (0,1,2) \)：宽度 \( 50+140=190 \leq 200 \)，价值 \( 0.25+0.8=1.05 > 1 \)，检验数 \( -0.05 \)。 添加列 \( a_ 5 = (0,1,2) \) 到主问题，求解得目标值 \( \approx 22.37 \)。 重复子问题直到无负检验数列，最终松弛最优解约需 \( 22.2 \) 个大卷（实际需取整）。 7. 算法总结 优势 ：避免枚举所有列，通过动态生成列处理大规模问题。 应用 ：切割库存、航班调度等组合优化问题。 扩展 ：得到松弛解后，需结合分支定界得到整数解（即分支定价算法）。 本例中，列生成通过求解子问题不断改进主问题，逐步逼近最优解，展示了如何用线性规划处理整数规划问题的高效技巧。