线性规划的Benders分解算法求解示例
题目描述
考虑一个生产计划与运输的优化问题。某公司有两个工厂（F1、F2）生产产品，需供应三个客户（C1、C2、C3）。每个工厂有最大产能限制（F1: 80单位，F2: 70单位），每个客户有固定需求（C1: 40单位，C2: 60单位，C3: 50单位）。从工厂到客户的单位运输成本如下表（单位：元）：
| C1 | C2 | C3 | |
|---|---|---|---|
| F1 | 4 | 6 | 8 |
| F2 | 7 | 5 | 3 |
每个工厂有固定开设成本（F1: 500元，F2: 400元），若工厂被启用才需支付。目标是最小化总成本（固定成本 + 运输成本）。该问题可建模为包含整数变量（工厂启用决策）和连续变量（运输量）的混合整数线性规划（MILP）。由于问题结构包含复杂变量与简单变量的耦合，适合用Benders分解算法求解。
解题过程
Benders分解将原问题分解为主问题（MP）和子问题（SP）：
- 主问题：处理复杂变量（如整数决策），提供初步解。
- 子问题：在给定主问题解下，优化连续变量，并向主问题反馈可行性或最优性割平面。
步骤1：问题建模
定义决策变量：
- \(y_i \in \{0,1\}\)：工厂 \(i\) 是否启用（\(i = 1,2\)）。
- \(x_{ij} \geq 0\)：从工厂 \(i\) 到客户 \(j\) 的运输量（\(j = 1,2,3\)）。
数学模型：
\[\text{Minimize} \quad 500y_1 + 400y_2 + \sum_{i=1}^2 \sum_{j=1}^3 c_{ij} x_{ij} \]
\[ \text{subject to} \quad \sum_{i=1}^2 x_{ij} = d_j \quad \forall j \quad \text{(需求约束)} \]
\[ \sum_{j=1}^3 x_{ij} \leq M_i y_i \quad \forall i \quad \text{(产能约束， } M_1=80, M_2=70 \text{)} \]
\[ x_{ij} \geq 0, \quad y_i \in \{0,1\} \]
步骤2：分解为Benders主问题和子问题
- 主问题（MP）：仅包含 \(y_i\) 变量和一个下界变量 \(\eta\)：
\[\text{Minimize} \quad 500y_1 + 400y_2 + \eta \]
\[ \text{subject to} \quad \text{可行性/最优性割平面（初始无约束）} \]
\[ y_i \in \{0,1\}, \quad \eta \in \mathbb{R} \]
- 子问题（SP）：固定 \(y_i = \bar{y}_i\) 后，求解运输问题：
\[\text{Minimize} \quad \sum_{i=1}^2 \sum_{j=1}^3 c_{ij} x_{ij} \]
\[ \text{subject to} \quad \sum_{i=1}^2 x_{ij} = d_j \quad \forall j \]
\[ \sum_{j=1}^3 x_{ij} \leq M_i \bar{y}_i \quad \forall i \]
\[ x_{ij} \geq 0 \]
步骤3：初始化主问题
初始主问题无割平面，解为 \(y_1 = y_2 = 0, \eta = -\infty\)，但需避免无界，可设 \(\eta \geq 0\) 或初始化一个简单下界（如0）。
步骤4：第一次迭代
-
求解主问题：
假设初始解为 \(y_1 = 1, y_2 = 1\)（启发式选择），目标值 \(z = 500 + 400 + \eta = 900 + \eta\)，但 \(\eta\) 未定，需子问题反馈。 -
求解子问题：
固定 \(\bar{y}_1 = 1, \bar{y}_2 = 1\)，求解运输问题：
需求约束： \(x_{11} + x_{21} = 40, x_{12} + x_{22} = 60, x_{13} + x_{23} = 50\)
产能约束： \(x_{11} + x_{12} + x_{13} \leq 80, x_{21} + x_{22} + x_{23} \leq 70\)
用运输单纯形法求解得最优解：
\(x_{11} = 40, x_{12} = 0, x_{13} = 40\)（F1运80单位），
\(x_{21} = 0, x_{22} = 60, x_{23} = 10\)（F2运70单位），
运输成本 \(= 40×4 + 40×8 + 60×5 + 10×3 = 160 + 320 + 300 + 30 = 810\)。
子问题最优值 \(SP^* = 810\)，对偶变量：- 需求约束对偶价 \(\pi_j\)：\(\pi_1 = 4, \pi_2 = 5, \pi_3 = 3\)（由运输成本结构推导）。
- 产能约束对偶价 \(\mu_i\)：\(\mu_1 = 0\)（产能未紧），\(\mu_2 = 0\)（产能未紧）。
-
生成最优性割平面：
子问题始终可行（因产能充足），添加最优性割：
\[\eta \geq \sum_{j=1}^3 d_j \pi_j - \sum_{i=1}^2 M_i \mu_i \bar{y}_i \]
代入本次对偶解：
\[\eta \geq 40×4 + 60×5 + 50×3 - (80×0×y_1 + 70×0×y_2) = 160 + 300 + 150 = 610 \]
割平面简化为 \(\eta \geq 610\)。
步骤5：第二次迭代
- 更新主问题：
MP加入割平面 \(\eta \geq 610\)：
\[\text{Minimize} \quad 500y_1 + 400y_2 + \eta \]
\[ \text{subject to} \quad \eta \geq 610, \quad y_i \in \{0,1\} \]
求解得最优解： \(y_1 = 0, y_2 = 1\)（仅开F2），\(\eta = 610\)，目标值 \(z = 400 + 610 = 1010\)。
-
求解子问题：
固定 \(\bar{y}_1 = 0, \bar{y}_2 = 1\)，产能约束变为：
F1关闭（\(x_{1j} = 0\)），F2需满足所有需求：
\(x_{21} = 40, x_{22} = 60, x_{23} = 50\)，但F2产能仅70，需求150 > 70，子问题不可行。 -
生成可行性割平面：
求解可行性子问题（最小化违背约束的松弛变量），得对偶变量 \(\gamma_j, \lambda_i\)。
可行性割：
\[\sum_{j=1}^3 d_j \gamma_j - \sum_{i=1}^2 M_i \lambda_i y_i \leq 0 \]
推导得：需强制至少开一个工厂或调整产能，例如添加割 \(y_1 + y_2 \geq 1\)。
步骤6：第三次迭代
-
更新主问题：加入可行性割 \(y_1 + y_2 \geq 1\)：
求解MP得： \(y_1 = 1, y_2 = 0\)（仅开F1），\(\eta = 610\)，目标值 \(z = 500 + 610 = 1110\)。 -
求解子问题：
固定 \(\bar{y}_1 = 1, \bar{y}_2 = 0\)，F1产能80 < 总需求150，不可行。
添加可行性割：要求总产能 ≥ 150，即 \(80y_1 + 70y_2 \geq 150\)。
步骤7：后续迭代与收敛
- 主问题加入新割后，解为 \(y_1 = 1, y_2 = 1\)，子问题可行，得运输成本810，总成本 \(900 + 810 = 1710\)。
- 比较上下界：主问题目标值（下界）与子问题总成本（上界），当上下界差距小于容差时停止。
- 最终解：两个工厂均启用，运输方案如第一次迭代，总成本1710元。
总结
Benders分解通过迭代切割，将复杂问题分解为简单整数规划和线性子问题，有效处理固定成本与连续决策的耦合。本例中，通过3次迭代逼近最优解，凸显了算法对混合整数规划的适用性。