求解机组组合问题的分段线性近似方法

全 然，张幼毅

（河南工业大学 理学院，郑州 450001）

在电力系统中，机组组合(Unit commitment，UC)问题是一类重要的经济调度问题，其数学模型是一类复杂的大规模混合整数非线性规划（Mixed integer nonlinear programming，MINLP）问题[1]。该问题的主要目标是在满足系统的功率需求和发电机组的技术要求条件下，使发电机组在计划时间范围内的总运行成本最低。

几十年来，国内外专家学者在UC问题上已经提出了许多经典的求解方法，大致可分为两类。第一类为数学优化算法，主要包括优先顺序法(Priority list，PL)[2-3]、动态规划法(Dynamic programming，DP)[4-5]、拉格朗日松弛算法(Lagrangian relaxation，LR)[6-7]、交替方向乘子 法(Alternating direction method of multipliers，ADMM)[8-9]、混合整数线性规划法(Mixed integer linear programming，MILP)[10-12]等。第二类为智能优化算法，主要包括粒子群算法(Particle swarm optimization，PSO)[13-14]、模拟退火算法(Simulated annealing，SA)[15-16]、人工神经网络算法(Artificial neural network，ANN)[17]等。数学优化算法属于求解UC问题的经典算法，多年来在UC问题的求解上已得到广泛应用。其中，DP法通过搜索机组的启停状态所形成的解空间以求解UC问题，能够获得中等规模UC问题的全局最优解；LR法将UC问题分解为一系列容易求解的子问题，能够加快求解速度；MILP法是将UC问题近似为MILP模型进行求解，可在合理的时间内获得高质量的次优解。智能优化方法也被广泛应用于UC问题的求解，得到了较好的效果。然而，其有时容易出现早熟现象，导致解的质量不高。

MILP法已成为解决UC问题的主流方法，这主要归功于MILP求解器算力的显著改进。Carrión和Arroyo在文献[10]中提出了UC问题的混合整数线性模型，需要较少的二进制变量和约束来减少计算负担，获得了良好的计算结果。在文献[11]中，利用透视割平面逼近二次目标函数，所提MILP方法可在短时间内获得高质量的解。文献[12]通过引入一类新的有效不等式，对发电机的可行运行计划给出了更紧的描述，从而显著缩短了整体求解时间。文献[18]提出了一种外内逼近（Outer-inner approximation，OIA）方法来求解UC问题。在这种OIA方法中，UC问题被分解为更紧的外逼近子问题和内逼近子问题，提供了更好的上下界。

分段线性近似（Piecewise linear approximation，PLA）是将非线性函数在其讨论区间内用多段线性函数进行近似[19]。容易知道，增加断点的数量将提高近似的精度，但会导致问题规模的增长，因此断点数并不是越多越好；同时，断点的选择方法对求解的结果也有影响。文献[19]通过对变量域进行不均匀划分来选择断点，结果优于相同断点数的均匀划分。

本文利用PLA方法并对区域进行非均匀取点，将UC问题的MIQP模型转化为MILP问题求解。仿真结果表明，与MIQP和区域均匀划分取点的两种方法相比，本文提出的方法能够在一定程度上节约生产费用和计算时间，是一种有效的方法。

1 UC问题的数学模型

通常情况下，UC问题的数学模型为一个MIQP问题，具体如下。

（Ⅰ）目标函数

目标函数是使火电机组总燃料费用最小：

（Ⅱ）约束条件

（a）机组出力约束

（b）系统的功率平衡约束

式中，PD,t为常数项，表示第t时段的功率总需求。

（c）系统的旋转备用约束

式中，Rt表示t时段的旋转备用。

（d）机组的最小启停时间约束

式中，vi,t，wi,t都是状态转移变量，如果机组i在t时段开机，则vi,t取值为1，否则值为0。与vi,t相反，机组i在t时段关机，wi,t取值为1，否则值为0。分别表示机组false的最小开机和停机时间。

（e）启动费用约束

式中，Chot,i与Ccold,i分别表示机组i的热启动费用和冷启动费用，Tcold,i表示机组i的冷启动时间。

（f）机组出力的爬坡约束

式中，Pup,i与Pdown,i分别表示机组i的功率上升速率限制和功率下降速率限制。Pstart,i与Pshut,i分别表示机组i的启动功率速率限制和停机功率速率限制。

由前述可知，UC问题的数学模型为一个MIQP问题，具体为：

引入辅助变量ηi,t，则上述问题等价于

2 求解UC问题的PLA算法

下面介绍PLA的算法思想。设非线性函数f（x）在区间[xl, xu]上有定义，在[xl, xu]内插入 n-1 个断点 x1, x2,…, xn-1，使得 x0= xl＜ x1＜x2＜…＜xn= xu，这 n-1个断点将区间[xl, xu]分成 n个小区间 [xi, xi+1]，i=0,1,…,n-1。令 yi=f（xi）,i=0,1,…,n，则连接点（xi+1, yi+1）与（xi,yi）的线性函数构成了f（x）的分段线性近似，如图1所示。

图1 分段线性近似

容易知道，增加断点的数量将提高PLA的近似精度，但也会导致问题规模的增长，这会给问题求解带来一定的难度。为了提高近似精度，并控制问题的规模，本文采用区域的非均匀划分方法[19]，具体方法如下。假设变量x∈[l,u]的局部解为x*，则可在区间[x*, u ]内或在[ l, x*]内选取断点，本文采用文献[19]中的非均匀断点选取方法，即断点取为：

其中k取1到2之间的值，j=1,2,...。

结合式，可得到UC问题的PLA模型：

显然，式是UC问题的一个MILP近似。

3 数值结果分析

3.1 参数设置

在MATLAB R2020a环境下进行编程，调用CPLEX 12.5对计算过程中涉及到的MILP、MIQP和二次规划问题进行求解，MILP和MIQP的求解精度设置为10-3。计算机配置为：Intel(R)Core(TM) i5-7200U CPU @ 2.50 GHz 2.70 GHz。

本文在求解UC问题时，仿真的系统以10机组24时段系统为基础，通过对此10个机组的数据复制可得到10个以上机组系统的数据。旋转备用取系统总负荷的10%，即Rt= 0.1PD,t。计算时，考虑以下两种情形的爬坡约束限制：情形一，爬坡出力速率限制和滑坡出力速率限制均取机组最大出力限制的20%，即；开机出力速率限制和停机出力速率限制均取机组最大出力限制，即。情形二，。

3.2 UC问题的计算结果

表1给出第一种情形下所提方法与另外两种方法的计算结果比较。其中，OIA为外内逼近算法[18]，DEA为微分进化算法[20]。从表1可以看出，对于所有机组系统，所提方法均在一定程度上优于文献中OIA和DEA这两种计算方法。

表1 不同算法总费用比较($)

表2为第一种情形下所提方法与均匀划分的计算结果比较，第2列到第4列表示本文非均匀划分的计算结果，第5列表示均匀划分的计算结果。从表中可以看出，机组数为20、40、100时，非均匀划分的次优值结果均在一定程度上优于均匀划分。对于10机组系统，非均匀划分与均匀划分的次优值相等。对于60和80机组系统，均匀划分和非均匀划分的次优值各有优劣，但相差不大。对于计算时间，两种划分各有优劣，但对于k=2时的非均匀划分，80和100机组系统用时较多。

表2 情形一中本文方法与均匀划分的计算结果比较

表3为第一种情形下所提方法与MIQP方法的计算结果比较。从表3可以看出，在次优值方面，两种方法相差不大；但对于计算时间，所提方法明显占优。

表3 情形一中本文方法与MIQP的数值结果比较

表4为第二种情形下所提方法与均匀划分的计算结果比较。

表4 情形二中本文方法与均匀划分的计算结果比较

从表中可以看出，对于k=1.7时的非均匀划分，20到80机组系统的次优值结果均优于均匀划分。对于k=1.5时的非均匀划分，当机组系统增加到40以上时，次优值结果均优于均匀划分。对于10机组系统，非均匀划分与均匀划分的次优值相等。当k=2时，对于10到40机组系统，非均匀划分和均匀划分的次优值相等，对于60机组系统次优值相差不大，但对于80和100机组系统非均匀划分的次优值优于均匀划分。计算时间方面，对于10到60机组系统，非均匀划分和均匀划分两者相差不大，但对于80和100机组系统，非均匀划分的时间明显占优。

表5为第二种情形下所提方法与MIQP方法的计算结果比较。对于60、80和100机组系统，所提方法在次优值方面比MIQP方法占有优势，但两种方法整体相差不大。对于计算时间，所提方法明显占优。

表5 情形二中本文方法与MIQP的数值结果比较

4 结论

本文利用PLA方法对区域进行非均匀取点，将UC问题转化为MILP问题求解。数值结果表明，与MIQP方法和均匀取点方法相比，本文提出的方法能够在一定程度上节约生产费用和计算时间，尤其是计算时间，具有良好的性能。