基于线性规划的鲁棒优化中鲁棒对等（Robust Counterpart）的线性化与求解示例
我将为您讲解一个鲁棒线性优化中鲁棒对等模型线性化的典型问题。这个问题在许多工程和经济领域有广泛应用，例如在参数不确定下的生产计划、投资组合优化等场景。
问题描述
考虑一个生产计划问题。某工厂生产两种产品，需要消耗三种原材料。每种原材料的供应量存在不确定性，但已知其可能的波动范围。目标是最大化利润，同时确保在所有可能的不确定参数实现下，约束条件都能得到满足。
原始确定性问题：
决策变量：
- \(x_1\): 产品1的产量
- \(x_2\): 产品2的产量
目标函数：最大化利润
\[\max \; 4x_1 + 5x_2 \]
约束条件（原材料消耗不超过供应）：
\[\begin{aligned} 2x_1 + 3x_2 &\le b_1 \quad &\text{(原材料1)} \\ 4x_1 + 2x_2 &\le b_2 \quad &\text{(原材料2)} \\ 3x_1 + 4x_2 &\le b_3 \quad &\text{(原材料3)} \\ x_1, x_2 &\ge 0 \end{aligned} \]
不确定参数：
原材料供应量 \(b_1, b_2, b_3\) 是不确定的。它们的标称值（名义值）为：
\[\bar{b}_1 = 100,\quad \bar{b}_2 = 120,\quad \bar{b}_3 = 130 \]
每个实际供应量在其标称值附近独立波动，波动幅度不超过标称值的10%。即：
\[b_i \in [\bar{b}_i - \delta_i, \;\bar{b}_i + \delta_i], \quad \delta_i = 0.1 \bar{b}_i \]
换句话说：
\[b_1 \in [90, 110],\; b_2 \in [108, 132],\; b_3 \in [117, 143] \]
在鲁棒优化框架下，我们要求决策 \((x_1, x_2)\) 必须对于所有可能的 \(b_i\) 取值（在上述区间内）都满足约束条件。
第一步：建立鲁棒对等（Robust Counterpart）模型
对于具有不确定右端项 \(b_i\) 的约束 \(a_i^T x \le b_i\)，其鲁棒对等要求：
\[a_i^T x \le b_i,\quad \forall b_i \in [\bar{b}_i - \delta_i, \bar{b}_i + \delta_i] \]
这等价于要求在最坏情况下（即 \(b_i\) 取最小值时）约束仍成立：
\[a_i^T x \le \min_{b_i \in [\bar{b}_i - \delta_i, \bar{b}_i + \delta_i]} b_i \]
因为约束是“小于等于”，所以最坏情况是 \(b_i\) 尽可能小。因此：
\[\min_{b_i} b_i = \bar{b}_i - \delta_i \]
于是鲁棒对等约束直接变为：
\[a_i^T x \le \bar{b}_i - \delta_i \]
应用到我们的问题：
\[\begin{aligned} 2x_1 + 3x_2 &\le 100 - 10 = 90 \\ 4x_1 + 2x_2 &\le 120 - 12 = 108 \\ 3x_1 + 4x_2 &\le 130 - 13 = 117 \\ x_1, x_2 &\ge 0 \end{aligned} \]
目标函数不变：\(\max \; 4x_1 + 5x_2\)。
这是一个简单的线性规划，可直接求解。
第二步：求解线性化的鲁棒对等问题
我们用单纯形法（或任何LP求解器）求解上述LP。
- 标准化为等式形式：
引入松弛变量 \(s_1, s_2, s_3 \ge 0\)：
\[\begin{aligned} 2x_1 + 3x_2 + s_1 &= 90 \\ 4x_1 + 2x_2 + s_2 &= 108 \\ 3x_1 + 4x_2 + s_3 &= 117 \\ x_1, x_2, s_1, s_2, s_3 &\ge 0 \end{aligned} \]
目标：\(\max \; z = 4x_1 + 5x_2\)。
- 初始单纯形表：
初始基变量为松弛变量 \((s_1, s_2, s_3)\)。
| 基 | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | 右端项 |
|---|---|---|---|---|---|---|
| \(s_1\) | 2 | 3 | 1 | 0 | 0 | 90 |
| \(s_2\) | 4 | 2 | 0 | 1 | 0 | 108 |
| \(s_3\) | 3 | 4 | 0 | 0 | 1 | 117 |
| \(z\) | -4 | -5 | 0 | 0 | 0 | 0 |
- 迭代1：
检验数中 \(x_2\) 系数 -5 最小（负最多），选 \(x_2\) 入基。
比值测试：
- 行1: \(90/3 = 30\)
- 行2: \(108/2 = 54\)
- 行3: \(117/4 = 29.25\)
最小正值是29.25，因此 \(s_3\) 出基。主元为4。
进行行运算，使 \(x_2\) 列变为单位向量 [0,0,1,0]^T（相对于基变量行）。
新表计算后（过程略，为标准单纯形法行变换），得到：
| 基 | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | 右端项 |
|---|---|---|---|---|---|---|
| \(s_1\) | 2 - 3*(3/4)=2 - 2.25= -0.25 | 0 | 1 | 0 | -3/4 | 90 - 3*(117/4)=90 - 87.75=2.25 |
| \(s_2\) | 4 - 2*(3/4)=4 - 1.5= 2.5 | 0 | 0 | 1 | -2/4=-0.5 | 108 - 2*(117/4)=108 - 58.5=49.5 |
| \(x_2\) | 3/4=0.75 | 1 | 0 | 0 | 1/4=0.25 | 117/4=29.25 |
| \(z\) | -4 - (-5)*(3/4)= -4 + 3.75= -0.25 | 0 | 0 | 0 | 5/4=1.25 | 0 + 5*(117/4)=146.25 |
- 迭代2：
检验数中 \(x_1\) 系数 -0.25 仍为负，选 \(x_1\) 入基。
比值测试（只考虑正系数行）：
- 行1：系数为负，跳过
- 行2：\(49.5 / 2.5 = 19.8\)
- 行3：\(29.25 / 0.75 = 39\)
最小为19.8，因此 \(s_2\) 出基。主元为2.5。
行变换后得到新表（过程略）：
| 基 | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | 右端项 |
|---|---|---|---|---|---|---|
| \(s_1\) | 0 | 0 | 1 | 0.1 | -0.8 | 2.25 + 0.25*(19.8)=7.2 |
| \(x_1\) | 1 | 0 | 0 | 0.4 | -0.2 | 19.8 |
| \(x_2\) | 0 | 1 | 0 | -0.3 | 0.4 | 29.25 - 0.75*(19.8)=14.4 |
| \(z\) | 0 | 0 | 0 | 0.1 | 1.2 | 146.25 + 0.25*(19.8)=151.2 |
所有检验数非负，达到最优。
最优解：
\[x_1^* = 19.8,\quad x_2^* = 14.4 \]
最优值：
\[z^* = 4 \times 19.8 + 5 \times 14.4 = 79.2 + 72 = 151.2 \]
第三步：鲁棒性验证与解释
- 鲁棒性验证：
在最坏情况下，每个供应量取最小值：\(b_1=90, b_2=108, b_3=117\)。
检查约束：
- 原材料1: \(2 \times 19.8 + 3 \times 14.4 = 39.6 + 43.2 = 82.8 \le 90\)
- 原材料2: \(4 \times 19.8 + 2 \times 14.4 = 79.2 + 28.8 = 108 \le 108\)（紧约束）
- 原材料3: \(3 \times 19.8 + 4 \times 14.4 = 59.4 + 57.6 = 117 \le 117\)（紧约束）
所有约束在最坏情况下满足，因此解是鲁棒的。
-
与确定性最优解比较：
若使用标称值 \(b_i = \bar{b}_i\) 求解，得到的最优解为 \(x_1=20, x_2=20\)，利润为 \(4 \times 20 + 5 \times 20 = 180\)。但此解在 \(b_3\) 取最小值117时，约束3：\(3 \times 20 + 4 \times 20 = 140 > 117\)，违反约束，不可行。
鲁棒优化牺牲了部分利润（从180降至151.2），换取了面对不确定性时的可行性保证。 -
线性化本质：
由于不确定性仅出现在右端项且为区间型，鲁棒对等可直接转化为对 \(b_i\) 取下界。这是鲁棒线性优化中“盒式不确定集（Box Uncertainty Set）”的典型处理方式，最终模型仍是线性规划。
总结与拓展
- 核心思想：鲁棒优化要求解对所有可能的不确定参数实现都可行，通过将约束加强到最坏情况下满足来实现。
- 线性化关键：对于区间不确定的右端项，鲁棒对等直接退化为使用下界值。
- 应用：该方法可推广到系数矩阵A或左端项也含不确定性的情况，此时可能需要引入对偶理论或额外变量来线性化，但基本原理相似——将无限多约束（\(\forall\) 不确定参数）转化为有限个线性约束。
- 优点：模型最终为线性规划，计算简便，且解具有鲁棒性保证。
- 缺点：可能因过度保守而损失性能，可通过调整不确定集（如预算不确定集）来平衡鲁棒性与性能。
通过以上步骤，我们完成了一个基于区间不确定集的鲁棒线性优化问题的建模、线性化、求解与验证的全过程。