随机规划第一节：Two-Stage、Scenario Tree、EVPI 与 VSS

学习目标：理解“在不确定性下如何做决策”，并能把一个简单的电力采购问题从业务语言翻译成 two-stage stochastic programming 模型。

1. 随机规划到底解决什么问题

随机规划不是主要回答：

“未来会是多少？”

而是回答：

“未来还不知道是多少时，我现在应该怎么决策；未来信息揭晓后，我又应该如何补救？”

最基本的时间顺序是：

\boxed{x \rightarrow \xi \rightarrow y}

其中：

$x$ ：第一阶段决策（First-stage decision），在不确定性揭晓前做；
$\xi$ ：之后才揭晓的随机信息；
$y$ ：第二阶段决策（Second-stage decision / Recourse），在看到 $\xi$ 后做。

最重要的判断规则：

能不能由我决定？

能决定，而且必须在随机信息揭晓前决定 → $x$

不能决定，是未来世界给出的结果 → $\xi$

在看到未来结果后还能采取的调整动作 → $y$

2. 我们建立的电力采购 Two-Stage 模型

2.1 业务设定

今天需要提前采购明天的电量：

提前采购价格：400 元/MWh；
明天实际负荷 $\xi$ 不确定；
若采购不足，第二阶段可以按 700 元/MWh 补买；
若采购过多，第二阶段可以按 200 元/MWh 卖出。

假设：

\xi= \begin{cases} 80,&p=0.5\\ 120,&p=0.5 \end{cases}

2.2 第一阶段决策

定义：

\boxed{x=\text{今天提前采购的电量}}

注意：

x\neq \xi

因为真实用电量不是交易员能决定的。

2.3 随机变量

定义：

\boxed{\xi=\text{明天实际用电量}}

它在决定 $x$ 时尚未揭晓。

2.4 第二阶段补救决策

定义：

y^{buy}\ge0

表示负荷揭晓后补买的电量；

y^{sell}\ge0

表示负荷揭晓后卖出的多余电量。

电量平衡：

\boxed{x+y^{buy}-y^{sell}=\xi}

等价地：

\boxed{y^{buy}-y^{sell}=\xi-x}

这里：

\xi-x

是第一阶段决策留下的净电量缺口；

而 $y$ 是第二阶段如何处理这个缺口的动作。

3. Recourse 和 Recourse Cost 不要混淆

Recourse 是：

\boxed{\text{看到随机结果以后采取的补救动作}}

例如：

$x=100,\xi=120$ → 补买 20；
$x=100,\xi=80$ → 卖出 20。

Recourse cost 是这些动作产生的经济结果。

在我们的例子中：

\boxed{700y^{buy}-200y^{sell}}

为什么卖出项是负号？

因为我们定义的是“净成本”：

买入增加成本： $+700y^{buy}$
卖出产生收入，抵减成本： $-200y^{sell}$

4. $Q(x,\xi)$ 到底是什么

给定：

第一阶段决策 $x$ ；
已经实现的随机状态 $\xi$ ；

第二阶段不会随便选择一个可行的 $y$ ，而会选择成本最低的补救方案。

因此：

\boxed{ Q(x,\xi) = \min_{y^{buy},y^{sell}\ge0} \left\{ 700y^{buy}-200y^{sell} : y^{buy}-y^{sell}=\xi-x \right\} }

4.1 为什么 $Q$ 里面需要一个 $\min$

例如：

x=100,\quad\xi=120

约束：

y^{buy}-y^{sell}=20

可行解不止一个：

(20,0),(30,10),(120,100),\dots

但它们成本不同。

所有可行解都可写成：

y^{buy}=20+t,\qquad y^{sell}=t,\qquad t\ge0

第二阶段成本：

700(20+t)-200t = 14000+500t

所以 $t=0$ 最优：

y^{buy*}=20,\qquad y^{sell*}=0

于是：

\boxed{Q(100,120)=14000}

另一种情景：

x=100,\quad\xi=80

最优补救：

y^{buy*}=0,\qquad y^{sell*}=20

所以：

\boxed{Q(100,80)=-4000}

负成本表示第二阶段净收入 4000 元。

4.2 $q$ 和 $Q$ 的区别

不要混：

$q$ ：第二阶段目标函数的成本系数；
$Q(x,\xi)$ ：第二阶段优化问题的最优值。

在这个例子中可以理解为：

q= \begin{bmatrix} 700\\ -200 \end{bmatrix}

而：

Q(x,\xi)=\min_y q^Ty

5. 从 $Q(x,\xi)$ 到 $E[Q(x,\xi)]$

当：

x=100

两个场景下：

Q(100,80)=-4000

Q(100,120)=14000

因此：

E[Q(100,\xi)] = 0.5(-4000)+0.5(14000) = \boxed{5000}

经济含义：

在第一阶段已经选择 $x=100$ 的前提下，考虑所有未来情景及概率，并在每个情景下采取最优补救后，第二阶段的平均净成本为 5000 元。

6. 完整 Two-Stage 目标函数

第一阶段采购本身也要付钱。

提前采购价格为 400 元/MWh，所以：

\text{First-stage cost}=400x

完整问题：

\boxed{ \min_x \left[ 400x+E[Q(x,\xi)] \right] }

一般形式：

\boxed{ \min_x \left[ c^Tx+E[Q(x,\xi)] \right] }

含义：

\boxed{ \text{现在的决策成本} + \text{未来最优补救的期望成本} }

一起最小化。

7. 为什么最优 $x^*$ 不一定等于 $E[\xi]$

我们的负荷均值：

E[\xi]=100

但在最初价格设定下：

提前买：400
以后补买：700
多余卖出：200

比较三个策略：

第一阶段 $x$	总期望成本
80	46000
100	45000
120	44000

因此：

\boxed{x^*=120}

虽然：

E[\xi]=100

7.1 原因：错误方向的边际代价不对称

少买 1 MWh：

700-400=300

多买 1 MWh：

400-200=200

所以：

\text{少买损失}>\text{多买损失}

模型自然向更高采购量倾斜。

最重要的结论：

\boxed{ x^* \text{ 由概率分布和决策成本结构共同决定，而不是只由 }E[\xi]\text{ 决定} }

7.2 改变成本结构，最优决策会翻转

若第二阶段补买价从 700 降到 500：

少买 1 MWh 的损失变成：

500-400=100

多买 1 MWh 的损失仍然：

400-200=200

此时：

\text{少买损失}<\text{多买损失}

模型会更倾向少买。

这说明：

\boxed{ \text{同一份概率预测，在不同市场价格结构下，可能产生完全不同的最优决策} }

8. Scenario Formulation

有限情景下：

E[Q(x,\xi)] = \sum_{s=1}^{S}p_sQ(x,\xi_s)

我们的两个场景：

\xi_1=80,\quad p_1=0.5

\xi_2=120,\quad p_2=0.5

为每个 scenario 分别建立 second-stage decision：

y_1^{buy},y_1^{sell}

y_2^{buy},y_2^{sell}

完整 scenario formulation：

\min \left[ 400x + 0.5(700y_1^{buy}-200y_1^{sell}) + 0.5(700y_2^{buy}-200y_2^{sell}) \right]

subject to

x+y_1^{buy}-y_1^{sell}=80

x+y_2^{buy}-y_2^{sell}=120

以及所有决策变量非负。

关键结构：

\boxed{\text{有多个 scenario-specific }y_s,\text{ 但第一阶段只有一个共同的 }x}

原因：

做 $x$ 时还不知道最终会进入哪个 scenario。

9. Scenario Tree

Scenario Tree 不只是“画很多未来”。

真正含义：

\boxed{\text{描述信息什么时候被揭示}}

例如：

                    今天
                     |
                    x1
               /           \
          需求高             需求低
            |                  |
           x2                 x2
          /  \               /  \
       价高  价低          价高  价低
        A     B             C     D

节点：当前的信息状态；
路径：一个完整 scenario；
分叉：新的信息被揭示；
边上的概率：条件概率；
根到叶子的路径概率：沿途条件概率连乘。

例如：

P(A) = P(\text{需求高}) P(\text{价高}\mid\text{需求高})

10. Non-anticipativity：非预见性约束

核心原则：

\boxed{ \text{决策只能利用当前已经知道的信息，不能偷看未来} }

更严格：

如果两个 scenarios 到当前阶段拥有完全相同的信息历史，那么当前阶段的决策必须相同。

假设最终 scenarios 为 A、B、C、D：

A：需求高 → 价高
B：需求高 → 价低
C：需求低 → 价高
D：需求低 → 价低

Stage 1

所有随机信息都尚未揭示：

\boxed{ x_1^A=x_1^B=x_1^C=x_1^D }

Stage 2

需求已经揭晓，价格尚未揭晓：

\boxed{x_2^A=x_2^B}

\boxed{x_2^C=x_2^D}

但“需求高”和“需求低”已经可以区分，所以 AB 组与 CD 组之间可以采取不同决策。

Stage 3

需求和价格都已经揭晓：

x_3^A,x_3^B,x_3^C,x_3^D

可以全部不同，不再需要跨 scenario 绑定。

最实用的判断规则：

\boxed{ \text{先按当前可见信息把 scenarios 分组；同组决策必须相同，不同组才允许不同。} }

一般代数形式可写成：

Mx=0

本质上就是很多：

x_i-x_j=0

11. EVPI：完美信息的期望价值

EVPI 衡量：

\boxed{\text{如果在做决策前就知道真实未来，能省多少钱？}}

正常随机规划：

\min_xE[F(x,\omega)]

顺序：

先选共同的 $x$ → 再面对未来。

完美信息：

E\left[\min_xF(x,\omega)\right]

顺序：

先知道是哪种未来 → 每个未来分别选择最优 $x$ → 最后站回事前角度求期望。

因此对于成本最小化问题：

\boxed{ \min_xE[F(x,\omega)] \ge E[\min_xF(x,\omega)] }

定义：

\boxed{ EVPI=RP-WS }

其中：

$RP$ ：正常随机规划的最优期望成本；
$WS$ ：Wait-and-See，拥有完美未来信息时的期望成本。

11.1 我们例子中的 EVPI

正常随机规划：

RP=44000

如果提前知道：

$\xi=80$ → 直接 $x=80$ ，成本 32000；
$\xi=120$ → 直接 $x=120$ ，成本 48000。

所以：

WS = 0.5(32000)+0.5(48000) = 40000

于是：

\boxed{ EVPI=44000-40000=4000 }

经济含义：

在这个模型里，“提前完美知道未来负荷”的能力，事前最多值 4000 元。

11.2 一个曾经容易混淆的点

如果完美信息已经告诉你：

\xi=80

那么情景树确实会收缩，只剩一条路径。

之所以计算 WS 时仍然对 80/120 求期望，是因为我们在信息尚未揭晓的事前时点给“拥有完美信息的能力”定价。

所以：

\boxed{ EVPI=\text{事前信息价值} }

信息一旦已经完全揭晓，就没有必要再计算 EVPI。

12. VSS：随机规划解的价值

VSS 衡量：

\boxed{ \text{相比只用均值做确定性决策，完整考虑随机性到底值多少钱？} }

假设有人不用 stochastic programming，而直接：

\xi\rightarrow E[\xi]=100

然后按确定性问题得到：

x_{EV}=100

但现实仍然是：

\xi=80\quad\text{或}\quad120

所以必须把 $x_{EV}=100$ 放回真实随机世界评价。

我们已经算过：

EEV=45000

而真正 stochastic programming：

RP=44000

因此：

\boxed{ VSS=EEV-RP=1000 }

经济含义：

在预测信息完全相同的情况下，仅仅把决策方法从“用均值”升级为“使用完整概率分布进行随机优化”，可以节省 1000 元。

所以：

\boxed{ VSS=\text{随机决策/随机建模本身的价值} }

而不是预测准确率本身的价值。

13. EVPI 和 VSS 的区别

对于成本最小化问题：

\boxed{ WS\le RP\le EEV }

在我们的例子里：

\boxed{ 40000<44000<45000 }

对应：

\text{完美信息} \quad \overset{EVPI}{\longleftrightarrow} \quad \text{随机规划} \quad \overset{VSS}{\longleftrightarrow} \quad \text{均值确定性决策}

公式：

\boxed{ EVPI=RP-WS }

\boxed{ VSS=EEV-RP }

含义：

指标	问的是什么	更接近哪一层
EVPI	如果提前知道真实未来，还能改善多少？	信息 / 预测层
VSS	如果信息不变，只把均值决策升级为随机规划，能改善多少？	决策 / 优化层

二者是同一家族的“价值衡量”，但不是同一个价值。

14. 本节完整知识链

最终可以压缩成：

\boxed{ x \rightarrow \xi \rightarrow y \rightarrow Q(x,\xi) \rightarrow E[Q(x,\xi)] \rightarrow \min_x[c^Tx+E(Q)] }

再扩展到多情景：

\boxed{ Scenario \rightarrow Scenario\ Tree \rightarrow Non\text{-}anticipativity }

最后衡量信息和随机决策的价值：

\boxed{ EVPI=\text{信息价值} }

\boxed{ VSS=\text{随机优化价值} }

15. 复习时最应该检查的 8 个问题

如果下面 8 个问题都能脱稿回答，这一节就基本掌握了。

为什么真实负荷 $\xi$ 不能是 first-stage decision $x$ ？
Recourse 和 recourse cost 有什么区别？
为什么 $Q(x,\xi)$ 里面存在一个 $\min$ ，而不是单纯写成一个成本公式？
为什么最优 $x^*$ 不一定等于 $E[\xi]$ ？
为什么 finite-scenario 模型里可以有多个 $y_s$ ，但第一阶段 $x$ 必须共享？
Non-anticipativity 最核心的一句话是什么？
为什么拥有完美信息后场景树会收缩，但计算 EVPI 时仍然要对不同未来求期望？
EVPI 和 VSS 分别衡量哪一层的价值？

16. 最小记忆版

如果过几天忘了细节，只需要先恢复下面这几行：

\boxed{x=\text{不确定性揭晓前的决策}}

\boxed{\xi=\text{之后才知道的随机信息}}

\boxed{y=\text{信息揭晓后的补救决策}}

\boxed{ Q(x,\xi)=\text{给定 }x,\xi\text{ 后最优 second-stage cost} }

\boxed{ \min_x[c^Tx+E(Q)] }

\boxed{ Non\text{-}anticipativity: \text{同一信息历史 → 同一决策} }

\boxed{ EVPI=RP-WS }

\boxed{ VSS=EEV-RP }

资料依据

本笔记以以下材料中的术语和框架为依据，并结合我们本轮对话构造的电力采购教学例子整理：

John R. Birge & François Louveaux, Introduction to Stochastic Programming
- Two-Stage Program with Fixed Recourse
- Multistage Stochastic Programs with Recourse
- Expected Value of Perfect Information
- Value of the Stochastic Solution
Alexander Shapiro, Darinka Dentcheva & Andrzej Ruszczyński, Lectures on Stochastic Programming
- Two-stage stochastic programming
- Scenario-tree formulation
- Nonanticipativity constraints
- Wait-and-see solution / EVPI
Alexander Shapiro & Andy Philpott, A Tutorial on Stochastic Programming
- Scenario-tree construction
- Multistage decision structure

注：本文中的“400 元提前采购、700 元补买、200 元卖出、80/120 MWh 两情景”是本轮学习中为理解概念而构造的教学算例，不是上述教材原例。

1. 随机规划到底解决什么问题

2. 我们建立的电力采购 Two-Stage 模型

2.1 业务设定

2.2 第一阶段决策

2.3 随机变量

2.4 第二阶段补救决策

3. Recourse 和 Recourse Cost 不要混淆

4. Q(x,ξ)Q(x,\xi)Q(x,ξ) 到底是什么

4.1 为什么 QQQ 里面需要一个 min⁡\minmin

4.2 qqq 和 QQQ 的区别

5. 从 Q(x,ξ)Q(x,\xi)Q(x,ξ) 到 E[Q(x,ξ)]E[Q(x,\xi)]E[Q(x,ξ)]

6. 完整 Two-Stage 目标函数

7. 为什么最优 x∗x^*x∗ 不一定等于 E[ξ]E[\xi]E[ξ]

7.1 原因：错误方向的边际代价不对称

7.2 改变成本结构，最优决策会翻转

8. Scenario Formulation

9. Scenario Tree

10. Non-anticipativity：非预见性约束

Stage 1

Stage 2

Stage 3

11. EVPI：完美信息的期望价值

11.1 我们例子中的 EVPI

11.2 一个曾经容易混淆的点

12. VSS：随机规划解的价值

13. EVPI 和 VSS 的区别

14. 本节完整知识链

15. 复习时最应该检查的 8 个问题

16. 最小记忆版

资料依据

4. $Q(x,\xi)$ 到底是什么

4.1 为什么 $Q$ 里面需要一个 $\min$

4.2 $q$ 和 $Q$ 的区别

5. 从 $Q(x,\xi)$ 到 $E[Q(x,\xi)]$

7. 为什么最优 $x^*$ 不一定等于 $E[\xi]$