列生成算法在电力系统机组组合问题中的两阶段随机规划模型求解示例

字数 2089 2025-12-04 18:28:39

列生成算法在电力系统机组组合问题中的两阶段随机规划模型求解示例

题目描述
考虑一个电力系统机组组合问题，电力公司需要决定未来24小时内各发电机组的启停状态和出力水平，以满足预测的电力需求。由于可再生能源（如风电）的不确定性，电力公司面临随机性挑战。采用两阶段随机规划模型：第一阶段决定发电机组的启停状态（整数决策），第二阶段根据风电出力的随机场景调整发电机组的出力水平（连续决策），以最小化总期望成本（包括启动成本、燃料成本和弃风惩罚成本）。由于问题规模大（机组数量多、场景多），直接求解困难，使用列生成算法进行高效求解。

解题过程

问题建模
- 设发电机集合为 \(I\)，时间周期集合为 \(T\)，风电随机场景集合为 \(S\)（每个场景 \(s\) 有概率 \(p_s\)）。
- 第一阶段变量：\(x_{it} \in \{0,1\}\) 表示机组 \(i\) 在时段 \(t\) 的启停状态。
- 第二阶段变量：\(y_{its} \geq 0\) 表示在场景 \(s\) 下机组 \(i\) 在时段 \(t\) 的出力。
- 目标函数：最小化总期望成本 = \(\sum_{i,t} C_i^s x_{it} + \sum_{s} p_s \left( \sum_{i,t} C_i^g y_{its} + \sum_t C^c w_{ts} \right)\)，其中 \(C_i^s\) 是启动成本，\(C_i^g\) 是燃料成本，\(C^c\) 是弃风惩罚成本，\(w_{ts}\) 是场景 \(s\) 下的弃风量。
- 约束条件：
  - 功率平衡约束：\(\sum_i y_{its} + w_{ts} = D_t\)（\(D_t\) 为需求）。
  - 机组出力上下限：\(x_{it} L_i \leq y_{its} \leq x_{it} U_i\)（\(L_i, U_i\) 为出力下限和上限）。
  - 风电不确定性：弃风量 \(w_{ts}\) 由风电实际出力与预测值偏差决定。
列生成算法框架
- 将原问题分解为主问题（Master Problem, MP） 和定价子问题（Pricing Subproblem, PSP）。
- 主问题：负责选择机组启停方案（对应列），目标是最小化期望成本。初始时，主问题包含少量可行列（如仅启停成本最低的机组）。
- 定价子问题：为每个机组生成新的启停方案（新列），检验其能否降低总成本。子问题利用主问题的对偶变量计算检验数（Reduced Cost）。
主问题建模（限制主问题）
- 设 \(\lambda_k\) 是机组启停方案 \(k\) 的决策变量（连续，表示使用方案 \(k\) 的比例），\(c_k\) 是方案 \(k\) 的总期望成本（包括启动成本和场景依赖的燃料成本）。
- 主问题形式：

\[ \min \sum_k c_k \lambda_k \]

\[ \text{s.t. } \sum_k \lambda_k = 1 \quad \text{（凸组合约束）}, \quad \lambda_k \geq 0 \]

注意：主问题松弛了整数变量（\(x_{it}\) 的整数约束），通过列生成得到下界，再结合分支定界求整数解。

定价子问题构建
- 对每个机组 \(i\)，子问题生成新的启停方案（新列）。
- 子问题目标：最小化检验数 \(\text{Reduced Cost} = c_k - \pi\)，其中 \(\pi\) 是主问题对偶变量。
- 具体地，\(c_k\) 包含启动成本 \(C_i^s\) 和第二阶段成本（需解随机规划子问题计算期望燃料成本）。
- 子问题是一个随机规划问题，需考虑所有场景 \(s\) 下的出力调整。
算法迭代步骤
- 步骤1：初始化主问题，加入少量可行列（如所有机组始终运行）。
- 步骤2：求解主问题（线性规划），得到对偶变量 \(\pi\)。
- 步骤3：对每个机组 \(i\)，求解定价子问题：
  - 固定该机组的启停状态变量 \(x_{it}\)。
  - 解第二阶段随机规划问题，计算该方案下期望成本 \(c_k\)。
  - 计算检验数 \(\text{Reduced Cost} = c_k - \pi\)。
- 步骤4：如果所有机组的检验数均非负（无改进列），算法停止；否则，将检验数为负的列加入主问题。
- 步骤5：重复步骤2-4直至收敛。
处理整数性
- 列生成得到连续松弛下界后，结合分支定界法（Branch-and-Price）搜索整数解。
- 在分支节点上重新运行列生成，确保全局最优。

关键点说明

列生成通过分解大幅减少变量数，尤其适合场景多的随机规划。
定价子问题本身是随机规划，可并行求解以加速。
实际应用中需考虑机组最小启停时间等约束，可在子问题中建模。

列生成算法在电力系统机组组合问题中的两阶段随机规划模型求解示例题目描述考虑一个电力系统机组组合问题，电力公司需要决定未来24小时内各发电机组的启停状态和出力水平，以满足预测的电力需求。由于可再生能源（如风电）的不确定性，电力公司面临随机性挑战。采用两阶段随机规划模型：第一阶段决定发电机组的启停状态（整数决策），第二阶段根据风电出力的随机场景调整发电机组的出力水平（连续决策），以最小化总期望成本（包括启动成本、燃料成本和弃风惩罚成本）。由于问题规模大（机组数量多、场景多），直接求解困难，使用列生成算法进行高效求解。解题过程问题建模设发电机集合为 \( I \)，时间周期集合为 \( T \)，风电随机场景集合为 \( S \)（每个场景 \( s \) 有概率 \( p_ s \)）。第一阶段变量：\( x_ {it} \in \{0,1\} \) 表示机组 \( i \) 在时段 \( t \) 的启停状态。第二阶段变量：\( y_ {its} \geq 0 \) 表示在场景 \( s \) 下机组 \( i \) 在时段 \( t \) 的出力。目标函数：最小化总期望成本 = \( \sum_ {i,t} C_ i^s x_ {it} + \sum_ {s} p_ s \left( \sum_ {i,t} C_ i^g y_ {its} + \sum_ t C^c w_ {ts} \right) \)，其中 \( C_ i^s \) 是启动成本，\( C_ i^g \) 是燃料成本，\( C^c \) 是弃风惩罚成本，\( w_ {ts} \) 是场景 \( s \) 下的弃风量。约束条件：功率平衡约束：\( \sum_ i y_ {its} + w_ {ts} = D_ t \)（\( D_ t \) 为需求）。机组出力上下限：\( x_ {it} L_ i \leq y_ {its} \leq x_ {it} U_ i \)（\( L_ i, U_ i \) 为出力下限和上限）。风电不确定性：弃风量 \( w_ {ts} \) 由风电实际出力与预测值偏差决定。列生成算法框架将原问题分解为主问题（Master Problem, MP）和定价子问题（Pricing Subproblem, PSP）。主问题：负责选择机组启停方案（对应列），目标是最小化期望成本。初始时，主问题包含少量可行列（如仅启停成本最低的机组）。定价子问题：为每个机组生成新的启停方案（新列），检验其能否降低总成本。子问题利用主问题的对偶变量计算检验数（Reduced Cost）。主问题建模（限制主问题）设 \( \lambda_ k \) 是机组启停方案 \( k \) 的决策变量（连续，表示使用方案 \( k \) 的比例），\( c_ k \) 是方案 \( k \) 的总期望成本（包括启动成本和场景依赖的燃料成本）。主问题形式： \[ \min \sum_ k c_ k \lambda_ k \] \[ \text{s.t. } \sum_ k \lambda_ k = 1 \quad \text{（凸组合约束）}, \quad \lambda_ k \geq 0 \] 注意：主问题松弛了整数变量（\( x_ {it} \) 的整数约束），通过列生成得到下界，再结合分支定界求整数解。定价子问题构建对每个机组 \( i \)，子问题生成新的启停方案（新列）。子问题目标：最小化检验数 \( \text{Reduced Cost} = c_ k - \pi \)，其中 \( \pi \) 是主问题对偶变量。具体地，\( c_ k \) 包含启动成本 \( C_ i^s \) 和第二阶段成本（需解随机规划子问题计算期望燃料成本）。子问题是一个随机规划问题，需考虑所有场景 \( s \) 下的出力调整。算法迭代步骤步骤1 ：初始化主问题，加入少量可行列（如所有机组始终运行）。步骤2 ：求解主问题（线性规划），得到对偶变量 \( \pi \)。步骤3 ：对每个机组 \( i \)，求解定价子问题：固定该机组的启停状态变量 \( x_ {it} \)。解第二阶段随机规划问题，计算该方案下期望成本 \( c_ k \)。计算检验数 \( \text{Reduced Cost} = c_ k - \pi \)。步骤4 ：如果所有机组的检验数均非负（无改进列），算法停止；否则，将检验数为负的列加入主问题。步骤5 ：重复步骤2-4直至收敛。处理整数性列生成得到连续松弛下界后，结合分支定界法（Branch-and-Price）搜索整数解。在分支节点上重新运行列生成，确保全局最优。关键点说明列生成通过分解大幅减少变量数，尤其适合场景多的随机规划。定价子问题本身是随机规划，可并行求解以加速。实际应用中需考虑机组最小启停时间等约束，可在子问题中建模。