随机规划中的两阶段规划 两阶段规划是随机规划的一种基本框架，用于处理决策问题中不确定性分阶段呈现的情况。它的核心思想是将决策分为两个阶段： 第一阶段决策 ：在不确定性实现之前做出的决策（例如投资、资源分配），称为“此时此景”决策。 第二阶段决策 ：在不确定性实现后，根据实际场景调整的决策（例如调整生产、应对需求波动），称为“补偿决策”或“recourse action”。 1. 问题背景与典型例子 假设一家公司需在需求不确定前决定生产量（第一阶段），需求实现后若生产不足则需紧急补货（第二阶段）。目标是最小化总期望成本（生产成本+期望补偿成本）。 2. 数学模型 设第一阶段决策变量为 \( x \in \mathbb{R}^n \)，第二阶段决策变量为 \( y \in \mathbb{R}^m \)，随机变量为 \( \xi \)（代表需求、价格等）。两阶段规划的标准形式为： \[ \min_ {x \geq 0} \left\{ c^\top x + \mathbb{E}_ {\xi} [ Q(x, \xi) ] \right\} \] 其中： \( c^\top x \) 为第一阶段成本； \( Q(x, \xi) = \min_ {y \geq 0} \left\{ q(\xi)^\top y \mid W(\xi) y = h(\xi) - T(\xi) x \right\} \) 是第二阶段问题的最优值函数，表示在给定 \( x \) 和 \( \xi \) 下的最小补偿成本。 约束条件 \( W(\xi) y = h(\xi) - T(\xi) x \) 体现了不确定性对资源平衡的影响。 3. 关键特性与假设 补偿可行性 ：需保证对任意 \( x \) 和 \( \xi \)，存在可行的 \( y \)（即问题具有相对完备补偿性，否则需引入可行性约束）。 期望值的计算 ：若 \( \xi \) 是连续随机变量，则 \( \mathbb{E}_ {\xi} [ Q(x, \xi) ] \) 需通过数值积分或抽样（如样本平均近似）近似。 凸性 ：若第二阶段问题是线性或凸的，则 \( Q(x, \xi) \) 是 \( x \) 的凸函数，整体问题为凸优化。 4. 求解方法 确定性等价 ：若 \( \xi \) 是离散分布（有限场景），问题可转化为大规模线性规划，直接求解。 Benders分解 ：将问题分解为主问题（第一阶段）和子问题（第二阶段），通过切割平面逐步逼近期望值函数。 随机梯度法 ：针对连续随机变量，通过随机采样估计次梯度，迭代更新第一阶段决策。 5. 扩展与变体 多阶段规划 ：将两阶段推广到多阶段，决策与不确定性交替出现。 风险厌恶版本 ：用条件风险价值（CVaR）等代替期望值，控制极端损失。 整数补偿决策 ：若 \( y \) 需取整数值，问题变为两阶段随机整数规划，求解难度显著增加。 两阶段规划通过结构化地处理不确定性，在供应链管理、能源规划等领域有广泛应用。