列生成算法在资源分配问题中的应用示例

题目描述：考虑一个资源分配问题，某公司有5个项目需要完成，每个项目需要不同数量的三种资源（人力、设备、资金）。公司拥有有限资源总量，目标是在资源限制下选择项目组合使得总收益最大。具体数据如下：

收益向量：c = [10, 15, 12, 8, 20]（单位：万元）
资源消耗矩阵：

项目1: [2, 1, 3]  // 人力2单位，设备1单位，资金3单位
项目2: [1, 2, 2]
项目3: [3, 1, 2]
项目4: [1, 1, 1]
项目5: [2, 3, 1]

资源总量：b = [7, 6, 8]（单位：各资源的总量）

这是一个0-1整数规划问题，但我们可以用列生成求解其线性松弛。

解题步骤：

1. 构建主问题（Master Problem）
   初始主问题只包含少数变量（比如前2个项目）：
   max 10x₁ + 15x₂
   s.t. 2x₁ + x₂ ≤ 7 // 人力约束
   x₁ + 2x₂ ≤ 6 // 设备约束
   3x₁ + 2x₂ ≤ 8 // 资金约束
   0 ≤ x₁, x₂ ≤ 1

2. 构建限制主问题（Restricted Master Problem, RMP）
   求解上述RMP得到对偶变量值：
   假设初始解为x₁=1, x₂=1，对偶变量π=[π₁, π₂, π₃]（对应三个资源约束）

3. 定价子问题（Pricing Subproblem）
   检查剩余项目（3,4,5）是否应该加入主问题：
   计算简约成本rcⱼ = cⱼ - π·Aⱼ（Aⱼ是项目j的资源消耗向量）
   子问题：max{ cⱼ - π·Aⱼ | j=3,4,5 }
   如果所有rcⱼ ≤ 0，当前解最优；否则将rcⱼ最大的项目加入主问题。

4. 迭代过程示例：
   第一次迭代后，发现项目5的简约成本最大（假设rc₅=8>0），将项目5加入主问题：
   max 10x₁ + 15x₂ + 20x₅
   s.t. 2x₁ + x₂ + 2x₅ ≤ 7
   x₁ + 2x₂ + 3x₅ ≤ 6
   3x₁ + 2x₂ + x₅ ≤ 8
   0 ≤ x₁, x₂, x₅ ≤ 1

重新求解RMP，更新对偶变量，继续定价步骤，直到所有简约成本非正。

5. 收敛与结果
   经过2-3次迭代后，所有项目的简约成本都≤0，得到线性松弛最优解。最终解可能包含分数值（如x₁=0.6, x₂=1, x₅=0.7），总收益约30.2万元。

关键点说明：

• 列生成通过动态添加变量避免枚举所有变量
• 定价子问题识别最有潜力改善目标函数的列
• 对偶变量提供资源边际价值的信息
• 该方法特别适合变量数量巨大的问题