求解计及失负荷概率约束机组组合问题的快速启发式算法

李文启，郭为民，杨 明，魏 强，程凤璐

（1.国网河南省电力公司，郑州 450052；2.国网河南省电力公司电力科学研究院，郑州 450052；3.山东大学电气工程学院，济南 250061）

0 引言

机组组合是电力系统运行调度体系中的关键环节，与在线经济调度相比，其对系统运行经济性的提升效果更为显著［1－5］。由于电力系统运行中存在发、输电设备随机故障等不确定性因素［6－7］，在机组组合过程中配置一定的旋转备用，是提高系统运行可靠性水平的一种有效手段，但是配置过多旋转备用可能会导致系统发电成本提高。因此，合理配置旋转备用就成为学术界、工业界关注的焦点问题［8－9］。

本文提出一种有效的以失负荷概率上限为约束的快速启发式机组组合算法。该算法的特点在于其快速性与鲁棒性，即使是含有上百台机组的系统并且考虑高阶故障，该算法可在较短时间内给出最优或次优的但必定为可行的解算结果，从而使以失负荷概率为约束的机组组合方法在计算耗时上具有了与传统确定性机组组合方法相近的优势，利于该类方法在生产实际中的推广应用。

1 问题描述

失负荷概率通常是指给定时间跨度内由于机组故障等各类扰动事件造成用户供电中断的概率［10］。由于该指标直接反应系统运行的可靠性，因而把它作为机组组合问题的约束条件将比采用备用约束更加直观与合理［11］。计及失负荷概率约束的机组组合模型可以如下描述。

决策目标为机组包括发电及启动成本在内的运行成本最小的表达式为：

式（1）中右边第2项为发电机组的启动成本，与停机时长有关，此处采用非线性函数表示为：

式中：φi为启动成本中的固定成本部分；βi为冷启动成本，Γi为机组的热时间常数，反映机组的冷却速度。

寻求目标函数最小化的过程中必须满足如下约束条件。

功率平衡约束为：

式中：Dt为时段t的负荷需求。

发电机输出功率上、下限约束为：

采用确定性备用配置策略的机组组合方法还规定了系统的最小备用需求约束（即容量约束）：

而对于以失负荷概率上限为约束的机组组合方法，系统最小备用需求约束式（5）将被失负荷概率约束所替代，即要求：

除上述约束外，机组组合模型还应包括最小开停机时间约束。由于该类约束将在所采用的拉格朗日松弛法的单机动态规划阶段计及，因而并不需要将其解析表达［12－13］。

上述即为对计及失负荷概率约束机组组合问题的描述，其中，式（6）是该模型的关键。对于任何一种给定的机组组合方式，系统失负荷概率可通过构建系统的发电容量停运概率表（COPT，Capacity Outage Probability Table）进行求取［10］。然而，由于优化前无法预知机组的组合方式，失负荷概率函数L（u）实际上是难以事先给出的。而文献［14］引入附加｛0，1｝整数变量、文献［12］、［15］和［16］采用备用与失负荷概率拟合的方式，其根本出发点均是希望优化前在机组启停决策变量与失负荷概率之间建立直接的函数对应关系，从而可采用统一优化方法进行求解。然而，这些方法要么计算效率不高，要么无法保证解的可行性。

2 一种快速启发式算法

2.1 总体流程

由于无法预知机组组合方式，从而确定备用与系统失负荷概率之间的对应关系，这里采用计及备用约束的常规机组组合与系统运行可靠性评估迭代求解的启发式算法。算法初始化时将系统在各个时段的备用需求置为零，利用拉格朗日松弛法进行无备用约束的机组组合预决策。在此基础上，根据机组组合预决策结果以及给定的最大允许失负荷概率对系统在各个时段的备用需求进行估计，进而进入下一次计及备用约束的机组组合计算，开始机组组合与运行可靠性评估的迭代过程。在该过程中，当一次机组组合计算完成后，若在线机组所能提供的备用容量无法满足当前机组组合方式下维持给定系统运行可靠性水平所需的备用容量，则更新备用需求，重新进行计及备用约束机组组合的计算，反之，则算法收敛，计算结束。算法总体流程如图1所示。

2.2 计及备用约束机组组合问题的求解

求解计及备用约束机组组合问题是上述算法的重要组成部分，此处采用拉格朗日松弛法进行求解。在机组组合问题的优化模型中，功率平衡约束与备用需求约束导致各机组的决策相互关联，无法单独进行，而拉格朗日松弛法的求解思路便是将这两类约束进行松弛，使松弛后的问题可以对各台机组独立求解。

基于问题描述部分所给出的机组组合模型，利用拉格朗日乘子对约束式（3）与约束式（5）进行松弛，松弛后优化模型的目标函数为：

图1 快速启发式算法总体流程图

式中：L为拉格朗日函数；λt、μt分别为功率平衡约束与备用需求约束对应的拉格朗日乘子，其值非负。

该目标函数在λt、μt给定时，去除对决策无影响的常数项后，可表示为：

由此可见，此目标函数是对机组可分的。在进行最小化该目标函数时需遵从机组输出功率上下限约束以及机组的最小开停机持续时间约束。由于此两类约束同样属于单机约束，因而松弛后可对每台机组单独求解。

然而，对原问题松弛后，问题的可行域将会增大，因而松弛后问题的解并不一定总在原问题的可行域内。如果松弛后问题的解不在原问题可行域内，那么迭代过程中需增大拉格朗日乘子，加大对违背约束的惩罚力度，促使松弛后问题的解趋向于原问题的可行域。如果松弛后问题的解在原问题可行域内，那么松弛后问题的目标函数是在原问题目标函数基础上减去非负项得到的，因而，松弛后问题的解实际上是原问题解的下限。此时，在循环过程中，将以使式（7）值最大化为目标更新拉格朗日乘子，此时所形成的最大最小问题被称为原问题的对偶问题。当对偶问题与原问题的目标函数值之差（对偶间隙）小于给定值时，则算法收敛。

拉格朗日松弛法求解计及备用约束机组组合问题的流程如图2所示。各模块具体功能及实现方法如下。

1）初始化 初始化部分采用优先级表法［17］确定机组启停初值，并在此基础上通过经济调度程序确定乘子λt初值；乘子μt初值设为0。

2）单机动态规划 依据乘子λt、μt的值，对每台机组采用动态规划法［17］求解松弛后问题，得到新的启停机计划。

3）备用需求约束检验 检验新的启停机计划是否能够满足备用需求约束。

4）更新乘子μt若备用需求约束不能满足，则需增大μt，重新进行单机动态规划过程。μt更新按次梯度方向，步长选择及加速收敛的方法可参考文献［13］。

5）经济调度计算 若备用需求约束满足，则进行经济调度，得到新的乘子λt。

6）收敛标准检验 检验此时原问题与对偶问题目标函数的差值，若小于预设值，程序收敛。

7）重置乘子μt若收敛标准没有达到，则将μt重新置零，合并最新得到的乘子λt，代入模块（2）重新进行单机动态规划计算。

2.3 备用需求的更新

本文算法的另一个重要部分是备用需求的更新。备用需求的更新主要包括3个环节：首先是根据当前机组组合方式构建发电容量停运概率表；其次是根据给定的失负荷概率上限从发电容量停运概率表中截取到对应的备用需求容量；最后是对估计得到的当前备用需求与当前在线机组能够提供的备用容量进行比较，判断程序是否收敛并形成下次迭代的备用需求容量。

发电容量停运概率表如表1所示。其中，第一列为升序排列的系统可能出现的停运容量；第二列为与停运容量对应的发生概率。

表1 发电容量停运概率表

图2 拉格朗日松弛法流程图

根据发电容量停运概率表，时段t系统的失负荷概率指标Lt可表示为：

式中：Mt为时段t在线机组所对应的发电容量停运概率表的总行数，即系统可能存在的运行状态总数；m为状态序号；为状态m发生的概率；为状态m下是否有失负荷的情况发生，有取1，无取0；Δ为状态m下的停运容量；Rt为系统在时段t的备用容量。

对于某一时段，当机组组合方式对应的系统失负荷概率指标高于给定的允许值时，说明当前时段在线机组所提供的备用容量无法满足要求，机组组合应向备用容量增多的方向发展。这里用当前机组组合方式下满足给定失负荷概率约束的备用容量来估计下一次迭代过程中系统的备用需求，将备用需求的调整步长ΔRt设定为：

对于任意时段t，系统备用需求的更新流程如图3所示。

3 解的可行性及最优性

启发式算法应在保证解算结果的可行性同时，尽量提高解的优化程度。本文算法的收敛条件设定为某次迭代过程中，已得机组组合方式对应的备用容量能够满足此方式下根据发电容量停运概率表以及给定的系统失负荷概率上限所确定的备用需求。在此条件下，如果算法收敛，那么解算结果显然能够满足系统的失负荷概率上限约束及其他机组组合相关约束，这样的结果当然是可行的。

图3 备用更新流程图

于此同时，对于计及失负荷概率约束机组组合问题的迭代式求解方法［11］，备用以较小步长（如1MW）增长无疑是较为稳妥的，可能得到较优的结果，但显然此法计算效率不高。所以，在所设计的迭代算法中，直接根据当次迭代的机组组合情况按给定失负荷概率上限求得下次迭代过程中的备用需求。这种备用方法是基于如下认识：在相同备用条件下，机组增多会使系统的失负荷概率增大。实际上，在一定系统备用情况下，新增机组增加了系统发生事故的可能性，由此，在相同备用容量下必然会增加系统的失负荷概率。

在半对数坐标系下，在总容量为344 MW的10机系统中相继加入3台容量为76 MW机组时，备用容量与失负荷概率之间的关系曲线如图4所示。

图4说明了随着新机组的加入，在任意给定的备用容量情况下系统的失负荷概率均会上升。因而，当在第k次迭代过程中确定了k＋1次迭代的备用需求后，若k＋1次迭代机组组合结果有新机组投入运行，要维持相同的失负荷概率，备用需求量一定会增加，故可以认为第k次迭代按式（9）确定的备用需求增长步长是适中的。尽管如此，在采用迭代算法时，算法收敛后仍需尝试进行减机组操作，以防配置过多的备用容量［11，18］。减机组操作流程如图5所示。图5中，边际机组按机组组合完成前最后一次经济调度计算得到的机组边际成本高低排序选取。

图4 备用容量与失负荷概率关系图

图5 减机组流程

4 算例分析

通过对单区域及多区域RTS-96系统进行测试，可以验证所提方法的有效性。RTS-96系统中含有26台火电机组，机组运行特性及成本参数见文献［19］，机组可靠性参数见文献［20］。计算发电容量停运概率表时，要求截断误差小于10－7。在单区域及多区域测试系统中，要保证该截断误差，均需考虑三阶故障全部及部分的四阶故障。

采用文献［11］与本文方法分别对单区域RTS-96系统进行机组组合计算。机组初始启停状态及已开停机时间见表2。表2中，“＋”表示开启，“－”表示关闭，数字表示状态持续时间。系统在24 h内的负荷需求变化见表3。假设各个时段中系统允许的失负荷概率上限均为5×10－5。

表2 机组初始状态 h

表324 h负荷需求 MW

采用文献［11］与本文方法决策得到的机组启停计划相同（见图6）。图6中，0表示停机，1表示开机。在计算时间上，采用文献［11］方法计算用时3516.14 s，本文方法计算用时8.37 s，计算速度提升显著。

图6 单区域RTS-96系统机组组合结果

计算效率的提升源自备用更新方法的改进，采用本文备用更新方法，仅需进行二次迭代。这里用第11 h的备用更新情况进行说明。初始时，系统要求的备用容量为0 MW，进行无备用约束的机组组合计算，得到第11 h机组组合方式对应的备用容量为96 MW。在此情况下，对系统可靠性进行分析，发现要将失负荷概率控制在5×10－5以下，需要备用容量为400 MW。因而，当前系统的失负荷概率上限约束无法满足，需进行下一次迭代。在第二次迭代中常规机组组合的备用容量下限约束定为400 MW，而经过机组组合计算所得的机组组合方式能够提供备用容量为435 MW。此时，为满足当前机组组合方式下的失负荷概率上限约束，需要提供的备用容量为420 MW。由于系统能够提供的备用容量大于维持系统运行可靠性所需的备用容量，因而该次迭代得到的机组组合方式能够满足失负荷概率上限约束，程序收敛。

为进一步检验本文算法的计算效率，对2区域、3区域、4区域、6区域及8区域RTS-96系统进行测试，负荷水平均参照单区域系统倍增。测试结果如表4所示。

表4 算法比较结果

从表4可以看出，对于各种情况，本文方法均可在较少的迭代次数内收敛，计算时间较短，能够满足机组组合问题对计算效率的要求。其中，对8区域系统的计算时间较对6区域系统的计算时间增长较多，这主要是由于随着机组数目的增多，机组组合问题的求解时间增长较为明显。同时，由于负荷的增长，在线机组的增多，使形成发电容量停运概率表的工作量增长显著，从而导致较长的计算时间。但尽管如此，15 min左右的计算时长对于机组组合问题而言是可以接受的。

5 结语

本文提出了一种求解计及失负荷概率约束机组组合问题的新的启发式算法。算法采用给定备用需求约束机组组合与系统运行可靠性评估的迭代求解策略进行模型求解，并在求解过程中，充分认识到随着在线机组数量的增多，维持相同系统失负荷概率所需的备用容量亦会增多这一规律。利用当前所得机组组合信息对系统实际所需的备用容量进行估计，提高了备用需求的更新速度，使算法在保持较高计算精度的同时，总体计算效率大幅提高。通过对单区域及多区域RTS-96系统的测试计算，验证了算法的有效性。

［1］ 夏清，康重庆，沈瑜.考虑网络安全约束条件的机组组合新方法［J］.清华大学学报（自然科学版），1999，39（9）：14-17.

［2］ 全然，韦化，简金宝.求解大规模机组组合问题的二阶锥规划方法［J］.中国电机工程学报，2010，30（25）：101-107.

［3］ 汪洋，夏清，康重庆.机组组合算法中起作用整数变量的辨识方法［J］.中国电机工程学报，2010，30（13）：46-52.

［4］ 王剑，刘天琪，刘学平.基于优先级排序和内点法的机组优化组合［J］.电力系统保护与控制，2010，38（13）：55-60.

［5］ 张晓花，赵晋泉，陈星莺.节能减排下含风电场多目标机组组合建模及优化［J］.电力系统保护与控制，2011，39（17）：33-39.

［6］ 康重庆，夏清，徐玮.电力系统不确定性分析［M］.北京：科学出版社，2011.

［7］ 谢开贵，肖畅.计及负荷不确定性的无功优化模型与算法［J］.电力系统保护与控制，2011，39（4）：18-22，29.

［8］ 张国强，吴文传，张伯明.考虑风电接入的有功运行备用协调优化［J］.电力系统自动化，2011，35（12）：15-19，46.

［9］ 杨梓俊，丁明，孙昕.电力市场下综合考虑系统可靠性和旋转备用效益的机组组合［J］.电网技术，2003，27（6）：13-18.

［10］Billinton R，Allan R N.Reliability evaluation of power systems［M］.New York and London：Plenum Press，1996.

［11］Gooi H B，Mendes D P，Bell K R W，et al.Optimal scheduling of spinning reserve［J］.IEEE Transactions on Power Systems，1999，14（4）：1485-1492.

［12］杨朋朋，韩学山，王静，等.用拉格朗日松弛法求解概率备用解析表达的机组组合［J］.山东大学学报，2007，37（2）：58-62，108.

［13］Virmani S，Adrian E C，Imhof K，Mukherjee S.Implementation of a Lagrangian relaxation based unit commitment problem［J］.IEEE Transactions on Power Systems，1989，4（4）：1373-1379.

［14］Bouffard F，Galiana F D.An electricity market with a probabilistic spinning reserve criterion［J］.IEEE Transactions on Power Systems，2004，19（1）：300-307.

［15］Wang M Q，Gooi H B.Spinning reserve estimation in microgrids［J］.IEEE Transactions on Power Systems，2011，26（3）：1164-1174.

［16］Ortega-vazquez M A，Kirschen D S.Estimating the spinning reserve requirements in systems with significant wind power generation penetration［J］.IEEE Transactions on Power Systems，2009，24（1）：114-124.

［17］Wood A J，Wollenberg B F.Power generation，operation，and control［M］.New York：Wiley Interscience，1996.

［18］杨朋朋，韩学山.基于改进拉格朗日乘子修正方法的逆序排序机组组合［J］.电网技术，2006，30（9）：40-45.

［19］Wang C，Shahidehpour S M.Effects of ramp-rate limits on unit commitment and economic dispatch［J］.IEEE Transactions on Power Systems，1993，8（3）：1341-1350.

［20］Grigg C，Wong P，Albrecht P，et al.The IEEE reliability test system-1996［J］.IEEE Transactions on Power Systems，1999，14（3）：1010-1018.