** 线性规划的分支定价算法求解示例
题目描述
考虑一个资源分配问题：某工厂有3台机器，需要生产4种产品。每种产品在不同机器上的加工时间、利润以及机器可用工时如下表所示。目标是最大化总利润。
| 产品 | 机器1工时 | 机器2工时 | 机器3工时 | 利润（元/件） |
|---|---|---|---|---|
| P1 | 2 | 1 | 3 | 10 |
| P2 | 1 | 3 | 2 | 15 |
| P3 | 3 | 2 | 1 | 12 |
| P4 | 2 | 2 | 2 | 8 |
机器可用工时：
- 机器1：80小时
- 机器2：60小时
- 机器3：100小时
问题建模
首先建立整数规划模型：
- 决策变量：\(x_j\) 表示产品 \(j\) 的生产数量（整数）
- 目标函数：最大化总利润 \(\max 10x_1 + 15x_2 + 12x_3 + 8x_4\)
- 约束条件：
\[ \begin{align*} 2x_1 + x_2 + 3x_3 + 2x_4 &\leq 80 \quad \text{(机器1)} \\ x_1 + 3x_2 + 2x_3 + 2x_4 &\leq 60 \quad \text{(机器2)} \\ 3x_1 + 2x_2 + x_3 + 2x_4 &\leq 100 \quad \text{(机器3)} \\ x_j &\geq 0, \quad \text{整数}, \ j=1,\dots,4 \end{align*} \]
由于问题规模较小，直接求解整数规划可行，但我们将使用分支定价算法演示其原理。
分支定价算法步骤
步骤1：松弛主问题（RMP）
先求解线性松弛问题（去掉整数约束）：
\[\begin{align*} \max \ & 10x_1 + 15x_2 + 12x_3 + 8x_4 \\ \text{s.t.} \ & 2x_1 + x_2 + 3x_3 + 2x_4 \leq 80 \\ & x_1 + 3x_2 + 2x_3 + 2x_4 \leq 60 \\ & 3x_1 + 2x_2 + x_3 + 2x_4 \leq 100 \\ & x_j \geq 0, \quad j=1,\dots,4 \end{align*} \]
使用单纯形法求解得最优解：
\[x_1 = 20, \ x_2 = 13.33, \ x_3 = 0, \ x_4 = 0, \ \text{最优值} = 400 \]
由于 \(x_2\) 非整数，需要分支。
步骤2：定价子问题（生成列）
在分支定价中，主问题通常包含部分列（变量），子问题生成新列。本例中，我们直接将所有变量纳入主问题，但演示定价过程：
假设当前RMP的对偶变量为 \(\pi_1, \pi_2, \pi_3\)（对应三个约束），则子问题为：
\[\max \ (c_j - \pi A_j) \]
其中 \(A_j\) 是产品 \(j\) 的资源消耗向量。若子问题目标值 > 0，则添加对应列到RMP。
步骤3：分支策略
选择非整数变量分支，例如 \(x_2 = 13.33\)：
- 分支1：\(x_2 \leq 13\)
- 分支2：\(x_2 \geq 14\)
步骤4：求解分支节点
分支1（\( x_2 \leq 13 \）：
添加约束后求解线性松弛，得：
\[x_1 = 20, \ x_2 = 13, \ x_3 = 1.33, \ x_4 = 0, \ \text{值} = 386 \]
分支2（\( x_2 \geq 14 \）：
求解得：
\[x_1 = 18, \ x_2 = 14, \ x_3 = 0, \ x_4 = 0, \ \text{值} = 390 \]
分支2的解为整数，更新当前最优整数解。
步骤5：继续分支
分支1的解仍有非整数 \(x_3\)，继续分支：
- 分支1.1：\(x_3 \leq 1\)
- 分支1.2：\(x_3 \geq 2\)
求解分支1.1得整数解 \((x_1=20, x_2=13, x_3=1, x_4=0)\)，值=383；
分支1.2无可行解。最终最优解为分支2的解：
\[x_1=18, \ x_2=14, \ x_3=0, \ x_4=0, \ \text{最大利润}=390 \]
算法总结
分支定价结合了分支定界和列生成，通过动态添加变量（列）避免枚举所有可能解。本例简化了列生成过程，但展示了核心思想：通过分支处理整数性，通过定价寻找改进列。