列生成算法在钢铁生产计划问题中的应用示例
问题描述
某钢铁厂生产多种宽度的钢卷（如1000mm、1500mm等），但客户订单需求的宽度规格多样（如400mm、600mm等）且数量不等。为了减少浪费，工厂需要将大卷切割成小卷以满足订单，目标是用最少的原材料（即总钢卷长度最小）完成所有订单。这种问题属于切割库存问题（Cutting Stock Problem）的变种，但在此我们聚焦于钢铁生产计划中的多规格订单分配优化。
假设：
- 原材料钢卷宽度固定为 \(W = 2000\text{mm}\)；
- 订单需求：宽度 \(w_i\) 和数量 \(d_i\)（\(i=1,2,...,m\)）；
- 一种切割模式（cutting pattern） 定义为一种可行的原材料切割方式，需满足所用宽度总和不超过 \(W\)，且切出的小卷宽度为订单宽度。
数学模型
设 \(x_j\) 表示采用第 \(j\) 种切割模式的原材料数量，\(a_{ij}\) 表示模式 \(j\) 中切出宽度 \(w_i\) 的数量。模型为：
\[\min \sum_j x_j \]
\[\text{s.t. } \sum_j a_{ij} x_j \geq d_i \quad (\forall i), \quad x_j \in \mathbb{Z}^+ \]
由于切割模式数量可能爆炸式增长，直接求解不可行，需使用列生成算法。
解题步骤
1. 构造限制主问题（Restricted Master Problem, RMP）
初始时仅包含少量可行切割模式（如每种订单单独成卷的浪费模式）。RMP的线性松弛形式为：
\[\min \sum_{j \in J} x_j \]
\[\text{s.t. } \sum_{j \in J} a_{ij} x_j \geq d_i \quad (\forall i), \quad x_j \geq 0 \]
其中 \(J\) 为当前模式集合。
2. 对偶问题与定价子问题
RMP的对偶变量为 \(\pi_i \geq 0\)（对应每个订单约束）。定价子问题的目标是找到负检验数的列，即求解：
\[\min \left\{1 - \sum_i \pi_i a_i \right\} \]
其中 \(a_i\) 表示新模式中宽度 \(w_i\) 的切出数量，需满足：
\[\sum_i a_i w_i \leq W, \quad a_i \in \mathbb{Z}^+ \]
这等价于求解一个背包问题：最大化 \(\sum_i \pi_i a_i\)，约束为 \(\sum_i a_i w_i \leq W\)。若最优值 \(>1\)，则当前模式可改进RMP。
3. 迭代过程
- 步骤1：求解RMP的线性松弛，得到对偶变量 \(\pi_i\)；
- 步骤2：求解背包问题，若最优值 \(\sum_i \pi_i a_i^* > 1\)，则将新模式 \(a^*\) 加入RMP；否则当前解已最优；
- 步骤3：重复直至无改进模式。
4. 整数解处理
得到线性松弛最优解后，若 \(x_j\) 非整数，需结合分支定界法或启发式（如向下取整后贪心补足需求）得到整数解。
实例演示
设 \(W=2000\)，订单需求如下：
| 宽度 \(w_i\) (mm) | 需求 \(d_i\) |
|---|---|
| 400 | 5 |
| 600 | 4 |
| 800 | 3 |
初始模式：简单模式（每卷只切一种宽度）：
- 模式1：\(a_1=(5,0,0)\)（切5份400mm，浪费0mm）
- 模式2：\(a_2=(0,3,0)\)（切3份600mm，浪费200mm）
- 模式3：\(a_3=(0,0,2)\)（切2份800mm，浪费400mm）
第一次迭代：
- 求解RMP得 \(\pi_1=0.2, \pi_2=0.333, \pi_3=0.5\)；
- 背包问题：最大化 \(0.2a_1 + 0.333a_2 + 0.5a_3\)，约束 \(400a_1+600a_2+800a_3 \leq 2000\)；
- 最优解：\(a=(1,2,0)\)（400mm切1份，600mm切2份），价值 \(0.2+0.666=0.866 <1\)，无改进。
- 继续尝试其他组合，发现 \(a=(0,2,1)\)（600mm切2份，800mm切1份）价值 \( 0.333\times2 + 0.5 =1.166>1 \），加入新列。
后续迭代：重复直至收敛，最终得线性松弛最优解。
关键点说明
- 列生成通过动态生成列避免枚举所有模式；
- 定价子问题是整数背包问题，可用动态规划快速求解；
- 在钢铁生产中，此方法显著减少原材料浪费，适用于大规模订单场景。