基于线性规划的鲁棒优化中椭球不确定集下最坏情况优化问题的求解示例
题目描述
我们考虑一个在生产计划中常见的资源分配问题。假设一家工厂用两种原料 \(M_1\) 和 \(M_2\) 生产两种产品 \(P_1\) 和 \(P_2\)，每件产品的利润是固定的，但原料的供应量不确定。在传统的线性规划中，原料供应量是精确已知的常数。但在现实中，由于供应链波动，实际供应量可能在一定范围内变化。鲁棒优化的思想是，在不确定参数属于一个已知的“不确定集”时，寻找一个解，使得在最坏情况下的目标值尽可能好。
本题具体模型如下：
决策变量：\(x_1, x_2 \geq 0\)，分别表示产品 \(P_1, P_2\) 的产量。
每件 \(P_1\) 需要消耗原料 \(M_1\) 为 2 单位，\(M_2\) 为 1 单位；每件 \(P_2\) 需要消耗 \(M_1\) 为 1 单位，\(M_2\) 为 3 单位。
每件 \(P_1\) 利润为 3 元，\(P_2\) 利润为 5 元，目标是最大化总利润 \(3x_1 + 5x_2\)。
原料供应量是不确定的：
- 原料 \(M_1\) 的名义供应量是 100 单位，但实际供应量 \(b_1\) 可能偏离名义值，其不确定集描述为一个椭球：
\((b_1 - 100)^2 + (b_2 - 150)^2 \leq r^2\)，其中 \(r = 20\) 是给定的半径。 - 原料 \(M_2\) 的名义供应量是 150 单位，实际供应量 \(b_2\) 与 \(b_1\) 一起满足上述椭球约束。
我们希望在任意满足 \((b_1 - 100)^2 + (b_2 - 150)^2 \leq 400\) 的 \((b_1, b_2)\) 出现时，生产计划 \((x_1, x_2)\) 都能满足资源约束，并在此基础上最大化最坏情况下的利润。于是鲁棒优化模型为：
\[\begin{aligned} \max_{x_1, x_2 \geq 0} \quad & 3x_1 + 5x_2 \\ \text{s.t.} \quad & 2x_1 + x_2 \leq b_1, \quad \forall (b_1, b_2) \in U,\\ & x_1 + 3x_2 \leq b_2, \quad \forall (b_1, b_2) \in U,\\ \text{其中 } U = \{ (b_1, b_2) \mid (b_1 - 100)^2 + (b_2 - 150)^2 \leq 400 \}. \end{aligned} \]
要求将这个鲁棒线性规划转化为一个确定性的可求解的凸优化问题，并求出最优解。
解题过程
第一步：理解鲁棒约束的处理思路
鲁棒约束要求“对所有不确定参数在不确定集内，约束都成立”。对于线性约束 \(a^T x \leq b\) 且 \(b\) 不确定，可以等价为 \(a^T x \leq \min_{b \in U} b\)，但这里 \(b\) 是向量，且不同约束涉及 \(b\) 的不同分量。更一般地，对第 \(i\) 个约束 \(a_i^T x \leq b_i\)，它应对所有 \((b_1, b_2) \in U\) 成立，这意味着：
\[a_i^T x \leq \min_{(b_1, b_2) \in U} b_i. \]
因为只要 \(x\) 满足小于等于 \(b_i\) 的最小可能值，那么对任意更大的 \(b_i\) 自然也满足。于是问题转化为求 \(b_i\) 在椭球 \(U\) 上的最小值。
第二步：计算每个约束的最坏情况右端项
对第一个约束 \(2x_1 + x_2 \leq b_1\)，需要 \(\min_{(b_1, b_2) \in U} b_1\)。椭球 \(U: (b_1-100)^2 + (b_2-150)^2 \leq 400\)。
最小值点在椭球上沿着 \(b_1\) 减小的方向达到，即取 \(b_1 = 100 - 20 = 80\)（因为半径 \(r=20\)，且椭球是圆，在 \(b_2=150\) 时 \(b_1\) 最小）。验证：\((80-100)^2 + (150-150)^2 = 400\)，满足。所以 \(\min b_1 = 80\)。
对第二个约束 \(x_1 + 3x_2 \leq b_2\)，需要 \(\min_{(b_1, b_2) \in U} b_2\)。类似地，最小 \(b_2 = 150 - 20 = 130\)。验证：\((100-100)^2 + (130-150)^2 = 400\)，满足。
于是鲁棒约束等价于确定性约束：
\[\begin{aligned} 2x_1 + x_2 &\leq 80,\\ x_1 + 3x_2 &\leq 130. \end{aligned} \]
第三步：求解确定性线性规划
问题变为：
\[\begin{aligned} \max \quad & 3x_1 + 5x_2 \\ \text{s.t.} \quad & 2x_1 + x_2 \leq 80,\\ & x_1 + 3x_2 \leq 130,\\ & x_1, x_2 \geq 0. \end{aligned} \]
这是一个简单的线性规划，可以用图解法或单纯形法。
第四步：图解法求最优解
画出可行域：
- 直线 \(2x_1 + x_2 = 80\) 过点 (0,80) 和 (40,0)。
- 直线 \(x_1 + 3x_2 = 130\) 过点 (0,130/3≈43.33) 和 (130,0)。
两条直线的交点：
\[\begin{cases} 2x_1 + x_2 = 80,\\ x_1 + 3x_2 = 130. \end{cases} \]
第一式乘以3：\(6x_1 + 3x_2 = 240\)，减去第二式：\(5x_1 = 110 \Rightarrow x_1 = 22\)，代入得 \(x_2 = 80 - 2\times 22 = 36\)。交点为 (22,36)。
检查交点是否满足非负：满足。
目标函数在交点处值：\(3\times 22 + 5\times 36 = 66 + 180 = 246\)。
再检查其他顶点：
- (0,0): 目标值 0。
- (40,0): 目标值 120。
- (0,130/3≈43.33): 目标值 216.67。
显然 (22,36) 最优。
因此最优解为 \(x_1^* = 22, x_2^* = 36\)，最坏情况下利润为 246。
第五步：解释鲁棒解的含义
我们得到的解保证：即使原料供应量在椭球不确定集内任意波动，生产计划 (22,36) 都不会超出实际供应量。此时，如果实际供应量恰好是最坏情况 \((b_1,b_2)=(80,130)\)，那么原料刚好用完，利润为246；如果实际供应量更大，利润仍为246（因为产量已固定），但原料有剩余。这种解是保守的，但确保了可行性不受不确定性的影响。
第六步：扩展讨论
如果椭球不确定集不是标准的圆，而是形如 \((b-\hat{b})^T \Sigma^{-1} (b-\hat{b}) \leq r^2\)，其中 \(\Sigma\) 是正定矩阵，则求 \(\min b_i\) 需要在椭球上求解一个二次约束线性优化问题，结果可解析得到（利用拉格朗日乘子法）。更一般的鲁棒线性规划中，如果约束矩阵 \(A\) 也存在不确定性，处理会复杂得多，但椭球不确定集通常可转化为二阶锥约束，从而可用凸优化求解。
总结
本题展示了椭球不确定集下的鲁棒线性规划的求解思路：将每个鲁棒约束转化为以右端项在最坏情况下的取值为界的确定性约束，从而将原问题转化为一个普通线性规划。这里的关键是椭球上的最小分量计算简单，最终得到一个保守但保证鲁棒可行的生产计划。