线性规划的列生成算法示例

题目描述
考虑一个资源分配问题：某工厂生产3种产品（A、B、C），需要2种原料（X、Y）。产品利润和原料消耗如下：

• 产品A：利润4元，消耗X原料3单位，Y原料1单位
• 产品B：利润5元，消耗X原料2单位，Y原料4单位
• 产品C：利润6元，消耗X原料1单位，Y原料3单位
  原料限制：X原料总量100单位，Y原料总量80单位。

由于产品组合可能很多，我们采用列生成方法求解。

解题过程

第一步：建立主问题和受限主问题
主问题的数学模型：

max 4x_A + 5x_B + 6x_C
s.t. 3x_A + 2x_B + 1x_C ≤ 100  (原料X约束)
     1x_A + 4x_B + 3x_C ≤ 80   (原料Y约束)
     x_A, x_B, x_C ≥ 0

由于变量数量可能很大，我们初始只考虑部分变量（子集）。建立受限主问题（RMP）：

初始RMP：只包含产品A和B
max 4x_A + 5x_B
s.t. 3x_A + 2x_B ≤ 100
     1x_A + 4x_B ≤ 80
     x_A, x_B ≥ 0

第二步：求解受限主问题
使用单纯形法求解初始RMP：

• 引入松弛变量s1, s2 ≥ 0
• 最优解：x_A = 24, x_B = 14, 目标函数值 = 4×24 + 5×14 = 166
• 对偶变量值：原料X的影子价格π_X = 1.1，原料Y的影子价格π_Y = 0.7

第三步：构建定价子问题
定价子问题用于检验是否存在能改善目标函数的新列（产品）：

max (c_j - π·a_j)
其中c_j是新产品的利润，a_j是其资源消耗系数

具体化：寻找新产品P，其利润为c_P，消耗资源向量a_P
子问题：max c_P - (π_X·a_PX + π_Y·a_PY)

第四步：求解定价子问题
假设新产品C的参数：利润6元，消耗(1,3)
计算检验数：6 - (1.1×1 + 0.7×3) = 6 - (1.1 + 2.1) = 2.8 > 0

由于检验数为正，说明引入产品C能改善目标函数。

第五步：更新受限主问题
将产品C加入RMP：

新的RMP：
max 4x_A + 5x_B + 6x_C
s.t. 3x_A + 2x_B + 1x_C ≤ 100
     1x_A + 4x_B + 3x_C ≤ 80
     x_A, x_B, x_C ≥ 0

第六步：迭代求解
重新求解新的RMP：

• 最优解：x_A = 20, x_B = 0, x_C = 20, 目标函数值 = 4×20 + 6×20 = 200
• 对偶变量：π_X = 1.0, π_Y = 1.0

再次求解定价子问题，检验是否还有其他改善产品。如果没有（所有检验数≤0），则当前解为最优。

最终结果
最优生产方案：生产产品A 20单位，产品C 20单位，不生产产品B
最大利润：200元
原料使用：X原料 = 3×20 + 1×20 = 80单位，Y原料 = 1×20 + 3×20 = 80单位