一、 两阶段随机规划的一般形式

两阶段随机规划通常以最小化成本为目标。其核心思想是：首先做出第一阶段决策 $x$，随后随机事件 $\xi$ 发生，基于 $x$ 和 $\xi$，我们再做出第二阶段（补救/追索）决策 $y$。

（1）数学模型

$$ \begin{aligned} \min_{x} \quad & c^T x + \mathbb{E}_{\xi}[Q(x, \xi)] \\ \text{s.t.} \quad & Ax = b \\ & x \ge 0 \end{aligned} $$

其中，$Q(x, \xi)$ 是第二阶段的最优值函数（Recourse Function），定义为：

$$ \begin{aligned} Q(x, \xi) = \min_{y} \quad & q(\xi)^T y \\ \text{s.t.} \quad & W(\xi)y = h(\xi) - T(\xi)x \\ & y \ge 0 \end{aligned} $$

（2）符号解释说明

  • 第一阶段（Here-and-Now）变量与参数：

    • $x$：第一阶段决策变量。是在不确定性揭晓之前必须做出的决定（例如：建厂选址、初始库存量）。
    • $c$：第一阶段决策的成本系数向量。
    • $A$：第一阶段约束条件的系数矩阵。
    • $b$：第一阶段约束条件的右端项向量。
    • $Ax = b, x \ge 0$：第一阶段的可行域。

  • 随机参数：

    • $\xi$：随机向量（Random Vector），代表不确定性（例如：未来的需求、天气、价格）。它包含了所有随机参数 $(q, h, T, W)$ 的实现值。
    • $\mathbb{E}_{\xi}[\cdot]$：关于随机变量 $\xi$ 的数学期望算子。

  • 第二阶段（Wait-and-See）变量与参数：

    • $y$：第二阶段决策变量（Recourse Variables）。是在观察到 $\xi$ 的具体数值后，为了修正或补充第一阶段决策而做出的决定（例如：紧急采购量、外包量）。
    • $q(\xi)$：第二阶段的成本系数向量（可能依赖于 $\xi$）。
    • $W(\xi)$：补救矩阵（Recourse Matrix），定义了第二阶段变量之间的约束关系。
    • $T(\xi)$：技术矩阵（Technology Matrix），定义了第一阶段决策 $x$ 如何影响第二阶段的约束。
    • $h(\xi)$：第二阶段约束的右端项（通常代表随机需求或资源限制）。

二、随机性价值分析（Value of Stochasticity）

2.1 核心概念：RP, EV, EEV

在评估随机规划模型的价值时，我们通常会对比三种不同的解或目标值。假设我们的目标是最小化（Minimization）。

（1）RP (Recourse Problem / Stochastic Solution)

  • 含义：这是真正的随机规划问题的最优解。即直接求解上述"一般形式"模型得到的目标函数值。
  • 解释：RP 考虑了所有可能的情景及其概率，寻找一个综合表现最好的 $x^*$。
  • 符号表示：$z_{RP}$

（2）EV (Expected Value Problem / Mean Value Problem)

  • 含义：这是期望值问题（或均值问题）。它是一种"偷懒"的做法，即把所有的随机变量 $\xi$ 替换为它们的期望值 $\bar{\xi} = \mathbb{E}[\xi]$，然后求解一个确定性的优化问题。
  • 解释：这相当于假设未来只会发生一种"平均情况"。
  • 模型： $$ \min \{ c^T x + q(\bar{\xi})^T y \mid Ax=b, W(\bar{\xi})y = h(\bar{\xi}) - T(\bar{\xi})x \} $$ 我们称这个确定性问题的最优解为 $\bar{x}_{EV}$。
  • 注意：这里的 EV 通常指求解这个简化问题本身，或者该简化问题的最优值 $z_{EV}$。但在后续计算中，更重要的是拿到它的解 $\bar{x}_{EV}$。

（3）WS (Wait-and-See)

  • 含义：完全信息解（或"等待-观察"解）。假设我们拥有"上帝视角"，在做决策 $x$ 之前就已经准确预知了 $\xi$ 会取什么值。
  • 计算方法：对每一种可能的场景 $\xi$，分别求解最优的 $x(\xi)$ 和 $y(\xi)$，然后计算这些最优值的期望。 $$ z_{WS} = \mathbb{E}_{\xi} \left[ \min_{x,y} \{ c^T x + q(\xi)^T y \mid \dots \} \right] $$
  • 解释：这是理论上的成本下界，现实中无法达到，因为我们无法预知未来。

（4）EEV (Expected result of using the EV solution)

  • 含义：期望值解的期望结果。这是衡量"如果我们无视随机性，只按平均情况做决策，最终在现实（随机）环境中的平均表现会怎样"。
  • 计算方法：
    1. 先解 EV 问题，得到决策 $\bar{x}_{EV}$。
    2. 将 $\bar{x}_{EV}$ 固定，代入到原本的随机规划模型中计算真实成本。 $$ z_{EEV} = c^T \bar{x}_{EV} + \mathbb{E}_{\xi}[Q(\bar{x}_{EV}, \xi)] $$
  • 解释：EEV 反映了"盲目相信平均值"所带来的真实后果。通常 $z_{EEV} \ge z_{RP}$（因为 $z_{RP}$ 是全局最优的，任何其他解都不会比它更好）。

2.2 直观比喻

场景：明天要出门，天气预报说可能下雨。你有一件怕淋湿的贵重衣服，需要决定明天穿不穿。

EV — “赌徒”

“下雨概率 50%，我就当不下雨。”

把随机性拍平成平均值，假装只有一种确定情况。闭着眼做一个决定，然后祈祷。

EEV — “赌徒的代价”

赌徒按"不下雨"出了门，结果真下雨了，衣服淋坏了。

EV 拍脑袋做的决定，放到真实世界里跑一遍的平均代价。也就是"无视随机性，现实会打你多疼"。

RP — “理性人”

“我提前想好了：下雨怎么办，不下雨怎么办，综合权衡后做个最优决定。”

把所有可能情景都考虑进去，找整体期望最优的策略。比如带一把小折叠伞——不下雨时有点累赘，但下了雨也不至于太惨。RP 就是你能做的最好。

WS — “上帝”

“我提前知道明天一定下雨。”

拥有完美预测，针对每个具体情景做出该情景下最完美的决策。现实中做不到，但给出了理论下界——再怎么努力也不可能比上帝做得更好。

一句话总结：

概念一句话成本
EV假装不确定性不存在$z_{EV}$
EEV用 EV 的决定去面对真实世界$z_{EEV}$（最贵）
RP考虑所有可能性，理性决策$z_{RP}$（你能做到的最好）
WS上帝视角，提前知道一切$z_{WS}$（最便宜）

关系：上帝 ≤ 理性人 ≤ 赌徒的代价，即 $z_{WS} \le z_{RP} \le z_{EEV}$。

  • VSS = 赌徒的代价 − 理性人 = 你因为"用了随机规划"省了多少钱
  • EVPI = 理性人 − 上帝 = 你愿意花多少钱买一份"完美天气预报"

三、 经典基准值与评价指标

除了上述三个概念，还有两个非常著名的概念用于衡量随机规划的价值和信息的价值：WS、VSS 和 EVPI。

2. VSS (Value of the Stochastic Solution)

  • 含义：随机解的价值。它衡量了使用复杂的随机规划模型（RP）比使用简单的均值模型（EV）能节省多少成本。
  • 公式： $$ VSS = z_{EEV} - z_{RP} $$
  • 解释：
    • 如果 $VSS$ 很大，说明随机性对结果影响巨大，必须使用随机规划。
    • 如果 $VSS \approx 0$，说明用平均值代替随机变量造成的损失很小，也许没必要用复杂的随机规划。

3. EVPI (Expected Value of Perfect Information)

  • 含义：完全信息的期望价值。它衡量了"如果我们能提前预知未来"，我们愿意为此支付多少钱。
  • 公式： $$ EVPI = z_{RP} - z_{WS} $$
  • 解释：
    • $z_{RP}$ 是我们在不确定环境下能做到的最好结果。
    • $z_{WS}$ 是拥有完美情报下的结果。
    • 两者的差值就是不确定性带来的"信息成本"。

总结：不等式关系

对于最小化问题，上述概念之间存在如下经典的链式不等式关系：

$$ z_{WS} \le z_{RP} \le z_{EEV} $$
  1. $z_{WS} \le z_{RP}$：拥有完美信息（WS）永远比在不确定下做决策（RP）成本更低（或相等）。
  2. $z_{RP} \le z_{EEV}$：随机规划的最优解（RP）永远比盲目使用均值解（EEV）成本更低（或相等）。

四、示例

我们使用一个经典的**“报童问题”（Newsvendor Problem）或者简单的工厂生产问题**作为例子。这是一个典型的两阶段随机规划问题。

1. 场景设定与符号定义

假设你经营一家工厂，生产某种特定零件。

第一阶段（决策阶段）：

  • 决策变量 $x$：今天决定生产多少个零件。
  • 参数 $c$：单位生产成本（例如：10元/个）。

随机事件（不确定性）：

  • 随机变量 $\xi$：明天的客户需求量（记为 $d$）。
  • 情景（Scenarios）：假设我们预测明天需求有三种可能：
    1. 情景 1（低需求）：需求 $d_1 = 100$，发生概率 $p_1 = 0.25$
    2. 情景 2（中需求）：需求 $d_2 = 200$，发生概率 $p_2 = 0.50$
    3. 情景 3（高需求）：需求 $d_3 = 300$，发生概率 $p_3 = 0.25$

第二阶段（补救/追索阶段）： 明天需求 $d$ 揭晓后，你的生产量 $x$ 可能不匹配，需要补救：

  • 情况 A（生产过多 $x > d$）：产生库存积压。
    • 变量 $y^+$：积压数量。
    • 参数 $h$：单位库存持有成本（例如：2元/个）。
  • 情况 B（生产过少 $x < d$）：产生缺货，需要紧急外包购买。
    • 变量 $y^-$：缺货数量。
    • 参数 $q$：单位紧急外包成本（通常很高，例如：20元/个）。

2. 求解 EV (Expected Value Problem) 的流程

核心思想：无视需求的波动，假设明天需求一定会是"平均值"。

  1. 计算平均需求： 计算随机变量的期望值 $\bar{d}$。 $$ \bar{d} = (100 \times 0.25) + (200 \times 0.50) + (300 \times 0.25) = 200 $$
  2. 建立确定性模型： 假设需求固定为 200，建立优化模型： $$ \min \quad 10x + (\text{基于需求是200的第二阶段成本}) $$
  3. 求解： 在这个确定性模型中，为了不产生库存也不缺货，最优决策显然是生产量等于平均需求。 得到 EV问题的解：$\bar{x}_{EV} = 200$。
  4. 得到 EV 值： 计算该模型下的目标函数值（通常参考意义不大，重点是拿到了 $\bar{x}_{EV}$ 这个决策）。

3. 求解 EEV (Expected result of using the EV solution) 的流程

核心思想：评估"如果我们按平均值生产（$\bar{x}_{EV}=200$），在现实世界中会发生什么？"

  1. 固定第一阶段决策： 强制令生产量 $x = 200$（来自 EV 的解）。
  2. 代入所有情景计算实际后果：
    • 情景 1（需求 100）： 你生产了 200，需求只有 100。 结果：积压 $y^+ = 100$。 成本 $Cost_1 = (生产成本 \times 200) + (库存成本 \times 100)$。
    • 情景 2（需求 200）： 你生产了 200，需求也是 200。 结果：完美匹配。 成本 $Cost_2 = (生产成本 \times 200) + 0$。
    • 情景 3（需求 300）： 你生产了 200，需求是 300。 结果：缺货 $y^- = 100$。 成本 $Cost_3 = (生产成本 \times 200) + (外包成本 \times 100)$。
  3. 计算期望总成本： 将上述三个成本按概率加权求和。 $$ z_{EEV} = p_1 \times Cost_1 + p_2 \times Cost_2 + p_3 \times Cost_3 $$ 这个 $z_{EEV}$ 就是如果你盲目相信平均值，最终平均要付出的代价。

4. 求解 RP (Recourse Problem) 的流程

核心思想：在一开始就考虑到所有可能的情景，寻找一个"最稳健"的生产量 $x$。

  1. 建立随机规划模型： 构建一个包含所有情景的大模型。目标是最小化"第一阶段成本 + 第二阶段的期望成本"。 $$ \min_x \quad 10x + \sum_{s=1}^{3} p_s \times Q(x, d_s) $$ 其中 $Q(x, d_s)$ 是在情景 $s$ 下的最优补救成本。
  2. 展开模型（确定性等价形式）： 实际上，求解器会同时解出 $x$ 以及每种情景下的 $y^+_s, y^-_s$。 目标函数变成： $$ \min \quad 10x + 0.25(2y^+_1 + 20y^-_1) + 0.50(2y^+_2 + 20y^-_2) + 0.25(2y^+_3 + 20y^-_3) $$ 约束条件包括针对每个情景的供需平衡（例如：$x + y^-_1 - y^+_1 = 100$ 等）。
  3. 求解： 使用线性规划求解器求解。 由于外包成本（20元）远高于库存成本（2元），模型通常会倾向于多生产一点，以避免高昂的缺货惩罚。 假设求解得到最优解 $x^* = 240$（这是一个假设值，具体取决于成本参数比例）。
  4. 得到 RP 值： 将 $x^* = 240$ 代入目标函数计算出的总成本，即为 $z_{RP}$。

总结对比

指标含义决策依据流程简述
EV期望值问题假设需求固定为平均值 (200)求平均需求 $\to$ 解确定性模型 $\to$ 得到决策 $\bar{x}_{EV}$
EEV均值解的期望结果使用 EV 的决策 ($\bar{x}_{EV}=200$)固定 $x=200$ $\to$ 放入所有随机情景 $\to$ 算加权平均成本
RP随机规划最优解考虑所有情景分布建立包含所有情景的大模型 $\to$ 直接求出最优 $x^*$ 和期望成本

通常你会发现：$z_{RP} < z_{EEV}$。 这两个值的差值（$VSS = z_{EEV} - z_{RP}$）就是你因为使用了随机规划模型（而不是简单拍脑袋用平均值）而节省下来的钱。

在同一个工厂生产（报童）的例子中，WS (Wait-and-See，等待-观察解/完全信息解) 代表了一种理想化的"上帝视角"。

它的核心假设是：在做第一阶段决策 $x$（生产量）之前，你已经拥有了完美的情报，准确预知了明天具体会发生哪种情景。

以下是求解 WS 的具体流程：

1. 核心思想

既然我已经预知了明天需求是多少，我就不需要去"猜"或者"权衡"风险了。我会针对每一个具体的情景，分别做出那个情景下最完美的决策。

2. 求解流程

我们需要针对三种情景，分别求解三个独立的小问题，最后算期望。

  • 针对情景 1（已知需求 $d_1 = 100$）

    • 情报：上帝告诉你"明天需求绝对是 100"。
    • 决策：为了成本最低，你显然会生产 $x_1 = 100$。
    • 后果：没有库存积压，也没有缺货。
    • 成本：$Cost_1 = 10 \times 100 = 1000$ 元。

  • 针对情景 2（已知需求 $d_2 = 200$）

    • 情报：上帝告诉你"明天需求绝对是 200"。
    • 决策：你会生产 $x_2 = 200$。
    • 后果：完美匹配。
    • 成本：$Cost_2 = 10 \times 200 = 2000$ 元。

  • 针对情景 3（已知需求 $d_3 = 300$）

    • 情报：上帝告诉你"明天需求绝对是 300"。
    • 决策：你会生产 $x_3 = 300$。
    • 后果：完美匹配。
    • 成本：$Cost_3 = 10 \times 300 = 3000$ 元。

3. 计算 WS 值

WS 值就是这些"拥有完美情报下的最优成本"的期望值（加权平均）。

$$ \begin{aligned} z_{WS} &= p_1 \times Cost_1 + p_2 \times Cost_2 + p_3 \times Cost_3 \\ &= 0.25 \times 1000 + 0.50 \times 2000 + 0.25 \times 3000 \\ &= 250 + 1000 + 750 \\ &= 2000 \end{aligned} $$

所以，在这个例子中，$z_{WS} = 2000$。

4. WS 与 RP 的关键区别（直观理解）

  • 在 RP（随机规划）中： 你必须在需求揭晓之前定下一个唯一的 $x$（比如 $x=240$）。这个 $x$ 必须同时应对三种可能，所以它在情景1里会积压，在情景3里会缺货。它是一种妥协的产物。

  • 在 WS（完全信息）中： 你的 $x$ 是动态的（$x$ 依赖于 $\xi$）。情景1来了你产100，情景3来了你产300。你永远不会犯错。

5. 进阶概念：EVPI (完全信息的价值)

通过算出 WS，我们就可以计算 EVPI (Expected Value of Perfect Information)：

$$ EVPI = z_{RP} - z_{WS} $$
  • $z_{RP}$：是你作为凡人，在不确定环境中能做到的最好结果（比如假设算出来是 2300 元）。
  • $z_{WS}$：是上帝的结果（2000 元）。
  • 差值 (300元)：代表了**“不确定性"本身给你带来的成本**。
    • 这也意味着：如果你想去买一份"绝对精准的市场预测报告”，你最多只愿意支付 300 元。如果报告卖 500 元，你就不如直接用 RP 模型去盲猜合算了。