求解機(jī)組組合問題的分段線性近似方法

全 然，張幼毅

（河南工業(yè)大學(xué) 理學(xué)院，鄭州 450001）

在電力系統(tǒng)中，機(jī)組組合(Unit commitment，UC)問題是一類重要的經(jīng)濟(jì)調(diào)度問題，其數(shù)學(xué)模型是一類復(fù)雜的大規(guī)?；旌险麛?shù)非線性規(guī)劃（Mixed integer nonlinear programming，MINLP）問題[1]。該問題的主要目標(biāo)是在滿足系統(tǒng)的功率需求和發(fā)電機(jī)組的技術(shù)要求條件下，使發(fā)電機(jī)組在計(jì)劃時(shí)間范圍內(nèi)的總運(yùn)行成本最低。

幾十年來(lái)，國(guó)內(nèi)外專家學(xué)者在UC問題上已經(jīng)提出了許多經(jīng)典的求解方法，大致可分為兩類。第一類為數(shù)學(xué)優(yōu)化算法，主要包括優(yōu)先順序法(Priority list，PL)[2-3]、動(dòng)態(tài)規(guī)劃法(Dynamic programming，DP)[4-5]、拉格朗日松弛算法(Lagrangian relaxation，LR)[6-7]、交替方向乘子 法(Alternating direction method of multipliers，ADMM)[8-9]、混合整數(shù)線性規(guī)劃法(Mixed integer linear programming，MILP)[10-12]等。第二類為智能優(yōu)化算法，主要包括粒子群算法(Particle swarm optimization，PSO)[13-14]、模擬退火算法(Simulated annealing，SA)[15-16]、人工神經(jīng)網(wǎng)絡(luò)算法(Artificial neural network，ANN)[17]等。數(shù)學(xué)優(yōu)化算法屬于求解UC問題的經(jīng)典算法，多年來(lái)在UC問題的求解上已得到廣泛應(yīng)用。其中，DP法通過(guò)搜索機(jī)組的啟停狀態(tài)所形成的解空間以求解UC問題，能夠獲得中等規(guī)模UC問題的全局最優(yōu)解；LR法將UC問題分解為一系列容易求解的子問題，能夠加快求解速度；MILP法是將UC問題近似為MILP模型進(jìn)行求解，可在合理的時(shí)間內(nèi)獲得高質(zhì)量的次優(yōu)解。智能優(yōu)化方法也被廣泛應(yīng)用于UC問題的求解，得到了較好的效果。然而，其有時(shí)容易出現(xiàn)早熟現(xiàn)象，導(dǎo)致解的質(zhì)量不高。

MILP法已成為解決UC問題的主流方法，這主要?dú)w功于MILP求解器算力的顯著改進(jìn)。Carrión和Arroyo在文獻(xiàn)[10]中提出了UC問題的混合整數(shù)線性模型，需要較少的二進(jìn)制變量和約束來(lái)減少計(jì)算負(fù)擔(dān)，獲得了良好的計(jì)算結(jié)果。在文獻(xiàn)[11]中，利用透視割平面逼近二次目標(biāo)函數(shù)，所提MILP方法可在短時(shí)間內(nèi)獲得高質(zhì)量的解。文獻(xiàn)[12]通過(guò)引入一類新的有效不等式，對(duì)發(fā)電機(jī)的可行運(yùn)行計(jì)劃給出了更緊的描述，從而顯著縮短了整體求解時(shí)間。文獻(xiàn)[18]提出了一種外內(nèi)逼近（Outer-inner approximation，OIA）方法來(lái)求解UC問題。在這種OIA方法中，UC問題被分解為更緊的外逼近子問題和內(nèi)逼近子問題，提供了更好的上下界。

分段線性近似（Piecewise linear approximation，PLA）是將非線性函數(shù)在其討論區(qū)間內(nèi)用多段線性函數(shù)進(jìn)行近似[19]。容易知道，增加斷點(diǎn)的數(shù)量將提高近似的精度，但會(huì)導(dǎo)致問題規(guī)模的增長(zhǎng)，因此斷點(diǎn)數(shù)并不是越多越好；同時(shí)，斷點(diǎn)的選擇方法對(duì)求解的結(jié)果也有影響。文獻(xiàn)[19]通過(guò)對(duì)變量域進(jìn)行不均勻劃分來(lái)選擇斷點(diǎn)，結(jié)果優(yōu)于相同斷點(diǎn)數(shù)的均勻劃分。

本文利用PLA方法并對(duì)區(qū)域進(jìn)行非均勻取點(diǎn)，將UC問題的MIQP模型轉(zhuǎn)化為MILP問題求解。仿真結(jié)果表明，與MIQP和區(qū)域均勻劃分取點(diǎn)的兩種方法相比，本文提出的方法能夠在一定程度上節(jié)約生產(chǎn)費(fèi)用和計(jì)算時(shí)間，是一種有效的方法。

1 UC問題的數(shù)學(xué)模型

通常情況下，UC問題的數(shù)學(xué)模型為一個(gè)MIQP問題，具體如下。

（Ⅰ）目標(biāo)函數(shù)

目標(biāo)函數(shù)是使火電機(jī)組總?cè)剂腺M(fèi)用最?。?/p>

（Ⅱ）約束條件

（a）機(jī)組出力約束

（b）系統(tǒng)的功率平衡約束

式中，PD,t為常數(shù)項(xiàng)，表示第t時(shí)段的功率總需求。

（c）系統(tǒng)的旋轉(zhuǎn)備用約束

式中，Rt表示t時(shí)段的旋轉(zhuǎn)備用。

（d）機(jī)組的最小啟停時(shí)間約束

式中，vi,t，wi,t都是狀態(tài)轉(zhuǎn)移變量，如果機(jī)組i在t時(shí)段開機(jī)，則vi,t取值為1，否則值為0。與vi,t相反，機(jī)組i在t時(shí)段關(guān)機(jī)，wi,t取值為1，否則值為0。分別表示機(jī)組false的最小開機(jī)和停機(jī)時(shí)間。

（e）啟動(dòng)費(fèi)用約束

式中，Chot,i與Ccold,i分別表示機(jī)組i的熱啟動(dòng)費(fèi)用和冷啟動(dòng)費(fèi)用，Tcold,i表示機(jī)組i的冷啟動(dòng)時(shí)間。

（f）機(jī)組出力的爬坡約束

式中，Pup,i與Pdown,i分別表示機(jī)組i的功率上升速率限制和功率下降速率限制。Pstart,i與Pshut,i分別表示機(jī)組i的啟動(dòng)功率速率限制和停機(jī)功率速率限制。

由前述可知，UC問題的數(shù)學(xué)模型為一個(gè)MIQP問題，具體為：

引入輔助變量ηi,t，則上述問題等價(jià)于

2 求解UC問題的PLA算法

下面介紹PLA的算法思想。設(shè)非線性函數(shù)f（x）在區(qū)間[xl, xu]上有定義，在[xl, xu]內(nèi)插入 n-1 個(gè)斷點(diǎn) x1, x2,…, xn-1，使得 x0= xl＜ x1＜x2＜…＜xn= xu，這 n-1個(gè)斷點(diǎn)將區(qū)間[xl, xu]分成 n個(gè)小區(qū)間 [xi, xi+1]，i=0,1,…,n-1。令 yi=f（xi）,i=0,1,…,n，則連接點(diǎn)（xi+1, yi+1）與（xi,yi）的線性函數(shù)構(gòu)成了f（x）的分段線性近似，如圖1所示。

圖1 分段線性近似

容易知道，增加斷點(diǎn)的數(shù)量將提高PLA的近似精度，但也會(huì)導(dǎo)致問題規(guī)模的增長(zhǎng)，這會(huì)給問題求解帶來(lái)一定的難度。為了提高近似精度，并控制問題的規(guī)模，本文采用區(qū)域的非均勻劃分方法[19]，具體方法如下。假設(shè)變量x∈[l,u]的局部解為x*，則可在區(qū)間[x*, u ]內(nèi)或在[ l, x*]內(nèi)選取斷點(diǎn)，本文采用文獻(xiàn)[19]中的非均勻斷點(diǎn)選取方法，即斷點(diǎn)取為：

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

結(jié)合式，可得到UC問題的PLA模型：

顯然，式是UC問題的一個(gè)MILP近似。

3 數(shù)值結(jié)果分析

3.1 參數(shù)設(shè)置

在MATLAB R2020a環(huán)境下進(jìn)行編程，調(diào)用CPLEX 12.5對(duì)計(jì)算過(guò)程中涉及到的MILP、MIQP和二次規(guī)劃問題進(jìn)行求解，MILP和MIQP的求解精度設(shè)置為10-3。計(jì)算機(jī)配置為：Intel(R)Core(TM) i5-7200U CPU @ 2.50 GHz 2.70 GHz。

本文在求解UC問題時(shí)，仿真的系統(tǒng)以10機(jī)組24時(shí)段系統(tǒng)為基礎(chǔ)，通過(guò)對(duì)此10個(gè)機(jī)組的數(shù)據(jù)復(fù)制可得到10個(gè)以上機(jī)組系統(tǒng)的數(shù)據(jù)。旋轉(zhuǎn)備用取系統(tǒng)總負(fù)荷的10%，即Rt= 0.1PD,t。計(jì)算時(shí)，考慮以下兩種情形的爬坡約束限制：情形一，爬坡出力速率限制和滑坡出力速率限制均取機(jī)組最大出力限制的20%，即；開機(jī)出力速率限制和停機(jī)出力速率限制均取機(jī)組最大出力限制，即。情形二，。

3.2 UC問題的計(jì)算結(jié)果

表1給出第一種情形下所提方法與另外兩種方法的計(jì)算結(jié)果比較。其中，OIA為外內(nèi)逼近算法[18]，DEA為微分進(jìn)化算法[20]。從表1可以看出，對(duì)于所有機(jī)組系統(tǒng)，所提方法均在一定程度上優(yōu)于文獻(xiàn)中OIA和DEA這兩種計(jì)算方法。

表1 不同算法總費(fèi)用比較($)

表2為第一種情形下所提方法與均勻劃分的計(jì)算結(jié)果比較，第2列到第4列表示本文非均勻劃分的計(jì)算結(jié)果，第5列表示均勻劃分的計(jì)算結(jié)果。從表中可以看出，機(jī)組數(shù)為20、40、100時(shí)，非均勻劃分的次優(yōu)值結(jié)果均在一定程度上優(yōu)于均勻劃分。對(duì)于10機(jī)組系統(tǒng)，非均勻劃分與均勻劃分的次優(yōu)值相等。對(duì)于60和80機(jī)組系統(tǒng)，均勻劃分和非均勻劃分的次優(yōu)值各有優(yōu)劣，但相差不大。對(duì)于計(jì)算時(shí)間，兩種劃分各有優(yōu)劣，但對(duì)于k=2時(shí)的非均勻劃分，80和100機(jī)組系統(tǒng)用時(shí)較多。

表2 情形一中本文方法與均勻劃分的計(jì)算結(jié)果比較

表3為第一種情形下所提方法與MIQP方法的計(jì)算結(jié)果比較。從表3可以看出，在次優(yōu)值方面，兩種方法相差不大；但對(duì)于計(jì)算時(shí)間，所提方法明顯占優(yōu)。

表3 情形一中本文方法與MIQP的數(shù)值結(jié)果比較

表4為第二種情形下所提方法與均勻劃分的計(jì)算結(jié)果比較。

表4 情形二中本文方法與均勻劃分的計(jì)算結(jié)果比較

從表中可以看出，對(duì)于k=1.7時(shí)的非均勻劃分，20到80機(jī)組系統(tǒng)的次優(yōu)值結(jié)果均優(yōu)于均勻劃分。對(duì)于k=1.5時(shí)的非均勻劃分，當(dāng)機(jī)組系統(tǒng)增加到40以上時(shí)，次優(yōu)值結(jié)果均優(yōu)于均勻劃分。對(duì)于10機(jī)組系統(tǒng)，非均勻劃分與均勻劃分的次優(yōu)值相等。當(dāng)k=2時(shí)，對(duì)于10到40機(jī)組系統(tǒng)，非均勻劃分和均勻劃分的次優(yōu)值相等，對(duì)于60機(jī)組系統(tǒng)次優(yōu)值相差不大，但對(duì)于80和100機(jī)組系統(tǒng)非均勻劃分的次優(yōu)值優(yōu)于均勻劃分。計(jì)算時(shí)間方面，對(duì)于10到60機(jī)組系統(tǒng)，非均勻劃分和均勻劃分兩者相差不大，但對(duì)于80和100機(jī)組系統(tǒng)，非均勻劃分的時(shí)間明顯占優(yōu)。

表5為第二種情形下所提方法與MIQP方法的計(jì)算結(jié)果比較。對(duì)于60、80和100機(jī)組系統(tǒng)，所提方法在次優(yōu)值方面比MIQP方法占有優(yōu)勢(shì)，但兩種方法整體相差不大。對(duì)于計(jì)算時(shí)間，所提方法明顯占優(yōu)。

表5 情形二中本文方法與MIQP的數(shù)值結(jié)果比較

4 結(jié)論

本文利用PLA方法對(duì)區(qū)域進(jìn)行非均勻取點(diǎn)，將UC問題轉(zhuǎn)化為MILP問題求解。數(shù)值結(jié)果表明，與MIQP方法和均勻取點(diǎn)方法相比，本文提出的方法能夠在一定程度上節(jié)約生產(chǎn)費(fèi)用和計(jì)算時(shí)間，尤其是計(jì)算時(shí)間，具有良好的性能。