基于线性规划的随机规划补偿模型求解示例
字数 1960 2025-10-30 08:32:20

基于线性规划的随机规划补偿模型求解示例

题目描述
考虑一个生产计划问题：某工厂需要决定下个月两种产品A和B的产量（记为\(x_1\)和\(x_2\)），目标为最大化利润。已知每单位A的利润为3元，B为5元。生产受以下约束：

  1. 资源约束：生产A和B需消耗原材料，每单位A消耗2kg，B消耗1kg，原材料总供应量不确定，但服从概率分布（例如均值为10kg的正态分布）。
  2. 需求约束：市场对A的需求至少为2单位，对B的需求至少为3单位。

若实际原材料供应量不足，工厂需以额外成本\(c=4\)元/kg紧急采购补偿缺货。要求以95%概率满足资源约束（即补偿模型下的机会约束）。试建立随机规划模型并求解。

解题过程

1. 模型建立

  • 决策变量：
    \(x_1\)：产品A产量，\(x_2\)：产品B产量。
  • 随机参数：
    原材料供应量\(\xi\)为随机变量，假设\(\xi \sim N(10, 1^2)\)。
  • 补偿机制：
    若实际需求\(2x_1 + x_2\)超过供应量\(\xi\)，缺货量\(y = \max(0, 2x_1 + x_2 - \xi)\)需以成本4元/kg补偿。
  • 目标函数：
    最大化期望利润：

\[ \max \, 3x_1 + 5x_2 - 4 \cdot \mathbb{E}[y] \]

其中\(\mathbb{E}[y]\)为期望补偿成本。

  • 约束条件：
    1. 需求约束：\(x_1 \geq 2\)，\(x_2 \geq 3\)。
    2. 机会约束：\(P(2x_1 + x_2 - y \leq \xi) \geq 0.95\)（即以95%概率保证补偿后不超供）。

2. 机会约束线性化
机会约束等价于：

\[P(2x_1 + x_2 - y \leq \xi) = P(\xi \geq 2x_1 + x_2 - y) \geq 0.95 \]

设\(\Phi\)为标准正态分布函数，因\(\xi \sim N(10,1)\)，有：

\[\frac{(2x_1 + x_2 - y) - 10}{1} \leq \Phi^{-1}(0.05) \]

查表得\(\Phi^{-1}(0.05) \approx -1.645\)，代入得：

\[2x_1 + x_2 - y \leq 10 - 1.645 = 8.355 \]

此即确定性等价约束。

3. 补偿变量处理
缺货量\(y\)需满足：

\[y \geq 2x_1 + x_2 - \xi \]

但\(\xi\)为随机变量，需转化为期望值形式。通过场景法或积分近似（本例采用离散化）：

  • 将\(\xi\)离散为3个场景：\(\xi_1=9\)（概率0.3），\(\xi_2=10\)（概率0.4），\(\xi_3=11\)（概率0.3）。
  • 引入场景依赖的补偿变量\(y_k\)（\(k=1,2,3\)），则目标函数变为：

\[\max \, 3x_1 + 5x_2 - 4 \sum_{k=1}^3 p_k y_k \]

  • 每个场景下补偿约束为：

\[y_k \geq 2x_1 + x_2 - \xi_k, \quad y_k \geq 0 \]

4. 完整线性规划模型

\[\begin{align} \max \quad & 3x_1 + 5x_2 - 4(0.3y_1 + 0.4y_2 + 0.3y_3) \\ \text{s.t.} \quad & x_1 \geq 2, \quad x_2 \geq 3 \\ & 2x_1 + x_2 - y_k \leq 8.355 \quad (\text{机会约束线性化}) \\ & y_k \geq 2x_1 + x_2 - \xi_k, \quad y_k \geq 0 \quad (k=1,2,3) \end{align} \]

5. 求解与结果分析
代入\(\xi_k\)值后，用单纯形法求解得：

  • 最优解：\(x_1^* = 2\)，\(x_2^* = 4.355\)，\(y_1^* = 0.355\)，\(y_2^* = 0\)，\(y_3^* = 0\)。
  • 最大期望利润：\(3 \times 2 + 5 \times 4.355 - 4 \times (0.3 \times 0.355) = 27.775\)。
  • 解释：生产计划优先满足高利润产品B，通过补偿机制平衡风险，95%概率下资源约束成立。

关键点
补偿模型通过引入随机变量的期望值将随机规划转化为确定性线性规划，机会约束的线性化是核心步骤。

基于线性规划的随机规划补偿模型求解示例 题目描述 考虑一个生产计划问题：某工厂需要决定下个月两种产品A和B的产量（记为\(x_ 1\)和\(x_ 2\)），目标为最大化利润。已知每单位A的利润为3元，B为5元。生产受以下约束： 资源约束 ：生产A和B需消耗原材料，每单位A消耗2kg，B消耗1kg，原材料总供应量 不确定 ，但服从概率分布（例如均值为10kg的正态分布）。 需求约束 ：市场对A的需求至少为2单位，对B的需求至少为3单位。 若实际原材料供应量不足，工厂需以额外成本\(c=4\)元/kg紧急采购补偿缺货。要求以 95%概率 满足资源约束（即补偿模型下的机会约束）。试建立随机规划模型并求解。 解题过程 1. 模型建立 决策变量 ： \(x_ 1\)：产品A产量，\(x_ 2\)：产品B产量。 随机参数 ： 原材料供应量\(\xi\)为随机变量，假设\(\xi \sim N(10, 1^2)\)。 补偿机制 ： 若实际需求\(2x_ 1 + x_ 2\)超过供应量\(\xi\)，缺货量\(y = \max(0, 2x_ 1 + x_ 2 - \xi)\)需以成本4元/kg补偿。 目标函数 ： 最大化期望利润： \[ \max \, 3x_ 1 + 5x_ 2 - 4 \cdot \mathbb{E}[ y ] \] 其中\(\mathbb{E}[ y ]\)为期望补偿成本。 约束条件 ： 需求约束：\(x_ 1 \geq 2\)，\(x_ 2 \geq 3\)。 机会约束：\(P(2x_ 1 + x_ 2 - y \leq \xi) \geq 0.95\)（即以95%概率保证补偿后不超供）。 2. 机会约束线性化 机会约束等价于： \[ P(2x_ 1 + x_ 2 - y \leq \xi) = P(\xi \geq 2x_ 1 + x_ 2 - y) \geq 0.95 \] 设\(\Phi\)为标准正态分布函数，因\(\xi \sim N(10,1)\)，有： \[ \frac{(2x_ 1 + x_ 2 - y) - 10}{1} \leq \Phi^{-1}(0.05) \] 查表得\(\Phi^{-1}(0.05) \approx -1.645\)，代入得： \[ 2x_ 1 + x_ 2 - y \leq 10 - 1.645 = 8.355 \] 此即确定性等价约束。 3. 补偿变量处理 缺货量\(y\)需满足： \[ y \geq 2x_ 1 + x_ 2 - \xi \] 但\(\xi\)为随机变量，需转化为期望值形式。通过 场景法 或 积分近似 （本例采用离散化）： 将\(\xi\)离散为3个场景：\(\xi_ 1=9\)（概率0.3），\(\xi_ 2=10\)（概率0.4），\(\xi_ 3=11\)（概率0.3）。 引入场景依赖的补偿变量\(y_ k\)（\(k=1,2,3\)），则目标函数变为： \[ \max \, 3x_ 1 + 5x_ 2 - 4 \sum_ {k=1}^3 p_ k y_ k \] 每个场景下补偿约束为： \[ y_ k \geq 2x_ 1 + x_ 2 - \xi_ k, \quad y_ k \geq 0 \] 4. 完整线性规划模型 \[ \begin{align} \max \quad & 3x_ 1 + 5x_ 2 - 4(0.3y_ 1 + 0.4y_ 2 + 0.3y_ 3) \\ \text{s.t.} \quad & x_ 1 \geq 2, \quad x_ 2 \geq 3 \\ & 2x_ 1 + x_ 2 - y_ k \leq 8.355 \quad (\text{机会约束线性化}) \\ & y_ k \geq 2x_ 1 + x_ 2 - \xi_ k, \quad y_ k \geq 0 \quad (k=1,2,3) \end{align} \] 5. 求解与结果分析 代入\(\xi_ k\)值后，用单纯形法求解得： 最优解：\(x_ 1^* = 2\)，\(x_ 2^* = 4.355\)，\(y_ 1^* = 0.355\)，\(y_ 2^* = 0\)，\(y_ 3^* = 0\)。 最大期望利润：\(3 \times 2 + 5 \times 4.355 - 4 \times (0.3 \times 0.355) = 27.775\)。 解释：生产计划优先满足高利润产品B，通过补偿机制平衡风险，95%概率下资源约束成立。 关键点 补偿模型通过引入随机变量的期望值将随机规划转化为确定性线性规划，机会约束的线性化是核心步骤。