Stochastic programming — 随机规划

随机规划（英语：stochastic programming）是数学规划的一个分支，为不确定性条件下的优化问题开发模型和求解方法。在此类问题中，模型的某些参数并非精确已知，而是被视为具有已知或估计概率分布的随机变量。

与所有数据都视为给定常数的确定性问题不同，随机规划的目标是找到在某种统计意义上最优的解（或决策策略）。这通常意味着最小化或最大化目标函数的数学期望。其核心思想是找到一个在所有随机参数的可能实现中“平均”表现最佳的决策策略，这对于需要在相似条件下重复决策的问题（例如，库存管理或能源系统管理）尤为重要。

问题的数学表述

随机规划问题的一般形式可以表述为： $\underset{x\in X}{\min }\mathbb{𝔼}[f(x,\xi )]$ 其中：

• $x$ — 需要确定的决策变量向量。
• $X$ — 由确定性约束定义的可行解集。
• $\xi$ — 代表问题中不确定参数（如需求、价格、天气状况）的随机向量。
• $f(x,\xi )$ — 目标函数，其值取决于决策 $x$ 和随机向量 $\xi$ 的实现。
• $\mathbb{𝔼}[\cdot ]$ — 数学期望算子，根据向量 $\xi$ 的概率分布进行计算。

多阶段随机模型的一个基本原则是不可预见性原则（英语：non-anticipativity principle）。该原则指出，在任何阶段做出的决策只能依赖于截至该时刻已知的信息，而不能“预见未来”。

带追索权的两阶段问题

最常见的模型是带追索权的两阶段随机规划（英语：two-stage stochastic program with recourse）。决策过程分为两个阶段：

1. 第一阶段： 做出“此时此地”（here-and-now）的决策——确定向量 $x$。该决策必须在随机向量 $\xi$ 的具体实现揭晓之前做出。
2. 第二阶段： 在随机事件发生后，做出一个修正性或补偿性的“追索决策”（recourse decision）——向量 $y(\xi )$，旨在最小化因第一阶段决策 $x$ 和随机结果 $\xi$ 组合而产生的不利后果，或利用出现的有利机会。

带追索权的两阶段随机线性规划问题的数学表达式如下： $\underset{x\in {\mathbb{ℝ}}^{n_1}}{\min }\{c^{T}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]\}$ 满足第一阶段约束条件：$Ax=b,x\ge 0$。 这里 $Q(x,\xi )$ 是追索函数（recourse function），代表第二阶段问题的最优值： $Q(x,\xi )=\underset{y\in {\mathbb{ℝ}}^{n_2}}{\min }\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ 其中 $\xi$ 是一个随机向量，包含参数 $q(\xi ),T(\xi )$ 和 $h(\xi )$；而 $c,A,b$ 和 $W$ 是确定性参数。

关键性质与定理

• 凸性：该理论的一个基本结果是，对于两阶段随机线性规划问题，期望追索函数 $Q(x)={\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$ 是一个凸函数。这一性质至关重要，因为它保证了整个第一阶段问题是一个凸规划问题，存在有效的求解方法，且全局最优解与局部最优解一致。
• 确定性等价形式：如果随机向量 $\xi$ 只有有限数量的可能实现（情景）${\xi }_1,\dots ,{\xi }_K$，其概率分别为 $p_1,\dots ,p_K$，那么该随机规划问题可以被重新表述为一个大型的确定性优化问题。在这种情况下，数学期望被替换为所有情景的加权和。然而，该问题的规模随情景数量线性增长，导致“维度灾难”，使得这种方法在情景数量巨大时计算上不可行。

与鲁棒优化的比较

随机规划是处理不确定性下优化的几种方法之一。它与鲁棒优化的关键区别在于对不确定性的建模方式和最优性准则。

不确定性条件下优化方法的比较

标准	随机优化	鲁棒优化
不确定性的表示	参数是具有已知概率分布的随机变量	参数属于一个给定的不确定性集合，不需要概率分布
最优性准则	优化目标函数的数学期望	优化最坏情况下的结果（极小化极大）
解的性质	“平均”最优的策略，在罕见情景下可能不可行	保证对所有实现都可行的解；可能较为保守

示例

• 报童问题（英语：newsvendor problem）：一个经典的库存管理问题，销售者需要在不确切知道未来需求的情况下，决定采购多少数量的商品。决策旨在平衡库存过剩的损失风险与缺货的错失利润风险。
• 农民问题：农民需要决定在总面积一定的土地上为不同作物分配多少英亩，但并不知道未来会影响产量的天气情况。当天气情况确定后，农民可以采取修正措施（例如，出售多余的收成或在市场上购买短缺的收成）。

参见

• 数学规划
• 运筹学
• 鲁棒优化
• 动态规划
• 控制理论