基于线性规划的随机规划样本平均近似法求解示例
字数 2870 2025-12-09 14:48:26

基于线性规划的随机规划样本平均近似法求解示例

我将为您讲解随机规划中一种重要的求解方法——样本平均近似法。这个方法通过采样将复杂的随机优化问题转化为确定性问题，然后利用线性规划等技术求解。

一、问题描述

随机规划处理的是包含随机参数的优化问题。考虑一个经典的两阶段随机线性规划问题：

第一阶段决策：在观察到随机变量ξ的实际值之前，我们先做出决策x，满足约束：
Ax = b, x ≥ 0

第二阶段：随机变量ξ（服从某个概率分布）的实际值被观察到后，我们需要做出第二阶段决策y(ξ)，使得在给定x和ξ的情况下，最小化第二阶段成本q(ξ)ᵀy(ξ)，并满足约束：
T(ξ)x + W(ξ)y(ξ) = h(ξ), y(ξ) ≥ 0

总目标：最小化第一阶段成本cᵀx加上第二阶段成本的期望值E[Q(x,ξ)]，其中Q(x,ξ)是给定x和ξ时的第二阶段最优值。

这个问题难以直接求解，因为期望E[Q(x,ξ)]通常涉及复杂的多重积分，特别是当ξ是连续随机变量时。

二、样本平均近似法核心思想

SAA的基本思想是：用经验平均值代替难以计算的期望值。

  1. 从ξ的分布中独立抽取N个样本ξ¹, ξ², ..., ξᴺ
  2. 用样本均值(1/N) Σᵢ Q(x,ξⁱ)近似期望E[Q(x,ξ)]
  3. 求解得到的近似确定性问题

三、详细求解步骤

步骤1：原问题形式化表达

原始随机规划问题为：
min cᵀx + E[Q(x,ξ)]
s.t. Ax = b, x ≥ 0
其中Q(x,ξ) = min{q(ξ)ᵀy | T(ξ)x + W(ξ)y = h(ξ), y ≥ 0}

期望E[·]是对随机变量ξ的分布取的。

步骤2：生成随机样本

假设随机变量ξ包含以下随机元素：

  • 随机需求d（假设服从正态分布N(μ, σ²)）
  • 随机成本系数q（假设均匀分布U[q_min, q_max]）

我们从ξ的联合分布中抽取N个独立同分布样本：
ξ¹, ξ², ..., ξᴺ
其中每个ξⁱ = (dⁱ, qⁱ)，包含了第i个场景下的具体实现值。

在数值实验中，常取N=100, 500, 1000等，N越大近似精度越高，但计算量也越大。

步骤3：构建样本平均近似问题

用样本均值代替期望，得到SAA问题：

min cᵀx + (1/N) Σᵢ₌₁ᴺ qⁱᵀyⁱ
s.t.
第一阶段约束：Ax = b, x ≥ 0
第二阶段约束（对每个场景i=1,...,N）：
Tⁱx + Wⁱyⁱ = hⁱ, yⁱ ≥ 0

这本质上是一个大型的确定性线性规划问题：

  • 决策变量：x和y¹, y², ..., yᴺ
  • 约束个数：第一阶段约束数 + N × 第二阶段约束数
  • 变量个数：x的维度 + N × y的维度

步骤4：求解SAA问题的线性规划

将SAA问题写成标准线性规划形式：

设原始变量维度：x ∈ ℝⁿ, yⁱ ∈ ℝᵐ
设第一阶段约束：A ∈ ℝᵖ×ⁿ, b ∈ ℝᵖ
第二阶段约束：Tⁱ ∈ ℝʳ×ⁿ, Wⁱ ∈ ℝʳ×ᵐ, hⁱ ∈ ℝʳ

SAA问题的线性规划形式为：

min cᵀx + (1/N) Σᵢ qⁱᵀyⁱ
s.t.
Ax = b
T¹x + W¹y¹ = h¹
T²x + W²y² = h²
...
Tᴺx + Wᴺyᴺ = hᴺ
x ≥ 0, yⁱ ≥ 0 (i=1,...,N)

这是一个具有特殊块状结构的线性规划，可以用以下方法求解：

子步骤4.1：直接使用单纯形法

将问题输入到线性规划求解器中。由于问题规模随N增大而快速增长，当N很大时可能需要专门的分解算法。

子步骤4.2：利用问题结构的分解法

SAA问题具有如下结构：

  • 连接约束：Ax = b
  • 场景约束：每个场景i独立，但通过x耦合

这适合用L形分解法（Benders分解）求解：

  1. 固定x，问题分解为N个独立的子问题
  2. 求解子问题得到最优值和割（可行性割或最优性割）
  3. 用割构造主问题，更新x
  4. 迭代直到收敛

步骤5：评估解的质量

设xᴺ*为SAA问题的最优解，我们需要评估它在原问题中的质量。

子步骤5.1：计算目标值估计

计算vᴺ = cᵀxᴺ* + (1/N) Σᵢ Q(xᴺ*, ξⁱ)
这是目标值的有偏估计，通常低估了真实的最优值。

子步骤5.2：计算上界估计

独立生成M个新的测试样本（M很大，如M=10000）：
ξ¹, ..., ξᴸ
计算：v̄ᴸ = cᵀxᴺ* + (1/L) Σⱼ Q(xᴺ*, ξʲ)
这提供了原问题目标值的统计上界。

子步骤5.3：计算最优性间隙估计

最优性间隙估计 = v̄ᴸ - vᴺ
这个间隙的95%置信区间可以通过重复SAA过程得到。

步骤6：多次运行SAA（可选但推荐）

为获得更可靠的解，通常：

  1. 运行SAA多次（如K=10次），每次用不同的随机样本
  2. 得到K个候选解xᴺ*(1), ..., xᴺ*(K)
  3. 用大量测试样本评估每个候选解
  4. 选择评估最好的解作为最终解

四、数值示例

考虑一个简单的生产-库存问题：

第一阶段：决定生产量x，成本c=2/单位
约束：x ≥ 0

第二阶段：随机需求d~Uniform[80, 120]

  • 如果x ≥ d，则出售d单位，收益p=3/单位
  • 如果x < d，则出售x单位，缺货无惩罚
    目标：最大化期望利润 = -2x + E[min(x,d)×3]

转化为最小化问题：
min 2x - 3E[min(x,d)]

用SAA求解：

  1. 生成N=100个d的样本，从Uniform[80,120]中抽取

  2. SAA问题：min 2x - (3/100) Σᵢ min(x, dⁱ)

  3. 等价线性规划形式（引入辅助变量yⁱ）：
    min 2x - (3/100) Σᵢ yⁱ
    s.t. yⁱ ≤ x, i=1,...,100
    yⁱ ≤ dⁱ, i=1,...,100
    x ≥ 0, yⁱ ≥ 0

  4. 求解这个LP，得到最优解x*

  5. 用M=10000个新样本评估解的质量

五、理论性质与注意事项

  1. 收敛性：当N→∞时，SAA问题的最优解和最优值以概率1收敛到原问题的最优解和最优值。

  2. 样本量选择：N需要足够大以保证解的质量，但计算复杂度随N线性增长。实践中可以通过增加N并观察解的变化来决定。

  3. 方差估计：可以通过重复SAA过程估计最优值的方差。

  4. 处理整数变量：如果第一阶段或第二阶段包含整数变量，SAA仍然适用，但需要求解混合整数规划，计算更复杂。

  5. 场景缩减：当N很大时，可以使用场景缩减技术减少场景数，同时保持近似质量。

六、优缺点分析

优点：

  • 将复杂的随机问题转化为确定性优化问题
  • 可以利用成熟的线性规划求解器
  • 理论上具有良好的收敛性质
  • 实现相对简单

缺点：

  • 问题规模随样本数线性增长
  • 样本量不足时可能得到次优解
  • 对于某些问题，可能需要大量样本才能获得高质量解
  • 对稀有事件可能采样不足

这种方法在实际应用广泛，特别适合那些期望值难以解析计算但可以高效采样的问题。

基于线性规划的随机规划样本平均近似法求解示例 我将为您讲解随机规划中一种重要的求解方法——样本平均近似法。这个方法通过采样将复杂的随机优化问题转化为确定性问题，然后利用线性规划等技术求解。 一、问题描述 随机规划处理的是包含随机参数的优化问题。考虑一个经典的两阶段随机线性规划问题： 第一阶段决策 ：在观察到随机变量ξ的实际值之前，我们先做出决策x，满足约束： Ax = b, x ≥ 0 第二阶段 ：随机变量ξ（服从某个概率分布）的实际值被观察到后，我们需要做出第二阶段决策y(ξ)，使得在给定x和ξ的情况下，最小化第二阶段成本q(ξ)ᵀy(ξ)，并满足约束： T(ξ)x + W(ξ)y(ξ) = h(ξ), y(ξ) ≥ 0 总目标 ：最小化第一阶段成本cᵀx加上第二阶段成本的期望值E[ Q(x,ξ) ]，其中Q(x,ξ)是给定x和ξ时的第二阶段最优值。 这个问题难以直接求解，因为期望E[ Q(x,ξ) ]通常涉及复杂的多重积分，特别是当ξ是连续随机变量时。 二、样本平均近似法核心思想 SAA的基本思想是：用经验平均值代替难以计算的期望值。 从ξ的分布中独立抽取N个样本ξ¹, ξ², ..., ξᴺ 用样本均值(1/N) Σᵢ Q(x,ξⁱ)近似期望E[ Q(x,ξ) ] 求解得到的近似确定性问题 三、详细求解步骤 步骤1：原问题形式化表达 原始随机规划问题为： min cᵀx + E[ Q(x,ξ) ] s.t. Ax = b, x ≥ 0 其中Q(x,ξ) = min{q(ξ)ᵀy | T(ξ)x + W(ξ)y = h(ξ), y ≥ 0} 期望E[ · ]是对随机变量ξ的分布取的。 步骤2：生成随机样本 假设随机变量ξ包含以下随机元素： 随机需求d（假设服从正态分布N(μ, σ²)） 随机成本系数q（假设均匀分布U[ q_ min, q_ max ]） 我们从ξ的联合分布中抽取N个独立同分布样本： ξ¹, ξ², ..., ξᴺ 其中每个ξⁱ = (dⁱ, qⁱ)，包含了第i个场景下的具体实现值。 在数值实验中，常取N=100, 500, 1000等，N越大近似精度越高，但计算量也越大。 步骤3：构建样本平均近似问题 用样本均值代替期望，得到SAA问题： min cᵀx + (1/N) Σᵢ₌₁ᴺ qⁱᵀyⁱ s.t. 第一阶段约束：Ax = b, x ≥ 0 第二阶段约束（对每个场景i=1,...,N）： Tⁱx + Wⁱyⁱ = hⁱ, yⁱ ≥ 0 这本质上是一个大型的确定性线性规划问题： 决策变量：x和y¹, y², ..., yᴺ 约束个数：第一阶段约束数 + N × 第二阶段约束数 变量个数：x的维度 + N × y的维度 步骤4：求解SAA问题的线性规划 将SAA问题写成标准线性规划形式： 设原始变量维度：x ∈ ℝⁿ, yⁱ ∈ ℝᵐ 设第一阶段约束：A ∈ ℝᵖ×ⁿ, b ∈ ℝᵖ 第二阶段约束：Tⁱ ∈ ℝʳ×ⁿ, Wⁱ ∈ ℝʳ×ᵐ, hⁱ ∈ ℝʳ SAA问题的线性规划形式为： min cᵀx + (1/N) Σᵢ qⁱᵀyⁱ s.t. Ax = b T¹x + W¹y¹ = h¹ T²x + W²y² = h² ... Tᴺx + Wᴺyᴺ = hᴺ x ≥ 0, yⁱ ≥ 0 (i=1,...,N) 这是一个具有特殊块状结构的线性规划，可以用以下方法求解： 子步骤4.1：直接使用单纯形法 将问题输入到线性规划求解器中。由于问题规模随N增大而快速增长，当N很大时可能需要专门的分解算法。 子步骤4.2：利用问题结构的分解法 SAA问题具有如下结构： 连接约束：Ax = b 场景约束：每个场景i独立，但通过x耦合 这适合用L形分解法（Benders分解）求解： 固定x，问题分解为N个独立的子问题 求解子问题得到最优值和割（可行性割或最优性割） 用割构造主问题，更新x 迭代直到收敛 步骤5：评估解的质量 设xᴺ* 为SAA问题的最优解，我们需要评估它在原问题中的质量。 子步骤5.1：计算目标值估计 计算vᴺ = cᵀxᴺ* + (1/N) Σᵢ Q(xᴺ* , ξⁱ) 这是目标值的 有偏估计 ，通常低估了真实的最优值。 子步骤5.2：计算上界估计 独立生成M个新的测试样本（M很大，如M=10000）： ξ¹, ..., ξᴸ 计算：v̄ᴸ = cᵀxᴺ* + (1/L) Σⱼ Q(xᴺ* , ξʲ) 这提供了原问题目标值的 统计上界 。 子步骤5.3：计算最优性间隙估计 最优性间隙估计 = v̄ᴸ - vᴺ 这个间隙的95%置信区间可以通过重复SAA过程得到。 步骤6：多次运行SAA（可选但推荐） 为获得更可靠的解，通常： 运行SAA多次（如K=10次），每次用不同的随机样本 得到K个候选解xᴺ* (1), ..., xᴺ* (K) 用大量测试样本评估每个候选解 选择评估最好的解作为最终解 四、数值示例 考虑一个简单的生产-库存问题： 第一阶段 ：决定生产量x，成本c=2/单位 约束：x ≥ 0 第二阶段 ：随机需求d~Uniform[ 80, 120 ] 如果x ≥ d，则出售d单位，收益p=3/单位 如果x < d，则出售x单位，缺货无惩罚 目标：最大化期望利润 = -2x + E[ min(x,d)×3 ] 转化为最小化问题 ： min 2x - 3E[ min(x,d) ] 用SAA求解： 生成N=100个d的样本，从Uniform[ 80,120 ]中抽取 SAA问题：min 2x - (3/100) Σᵢ min(x, dⁱ) 等价线性规划形式（引入辅助变量yⁱ）： min 2x - (3/100) Σᵢ yⁱ s.t. yⁱ ≤ x, i=1,...,100 yⁱ ≤ dⁱ, i=1,...,100 x ≥ 0, yⁱ ≥ 0 求解这个LP，得到最优解x* 用M=10000个新样本评估解的质量 五、理论性质与注意事项 收敛性 ：当N→∞时，SAA问题的最优解和最优值以概率1收敛到原问题的最优解和最优值。 样本量选择 ：N需要足够大以保证解的质量，但计算复杂度随N线性增长。实践中可以通过增加N并观察解的变化来决定。 方差估计 ：可以通过重复SAA过程估计最优值的方差。 处理整数变量 ：如果第一阶段或第二阶段包含整数变量，SAA仍然适用，但需要求解混合整数规划，计算更复杂。 场景缩减 ：当N很大时，可以使用场景缩减技术减少场景数，同时保持近似质量。 六、优缺点分析 优点 ： 将复杂的随机问题转化为确定性优化问题 可以利用成熟的线性规划求解器 理论上具有良好的收敛性质 实现相对简单 缺点 ： 问题规模随样本数线性增长 样本量不足时可能得到次优解 对于某些问题，可能需要大量样本才能获得高质量解 对稀有事件可能采样不足 这种方法在实际应用广泛，特别适合那些期望值难以解析计算但可以高效采样的问题。