鄭海艷，簡金寶，全 然，楊林峰

（1.廣西大學(xué) 數(shù)字與信息科學(xué)學(xué)院，廣西 南寧 530004；2.玉林師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，廣西 玉林 537000；3.河南工業(yè)大學(xué) 理學(xué)院，河南 鄭州 450001；4.廣西大學(xué) 計算機(jī)與電子信息學(xué)院，廣西 南寧 530004）

0 引言

在當(dāng)今節(jié)能減排這樣一個世界共識下，電力系統(tǒng)的優(yōu)化運行顯得尤為重要。機(jī)組組合UC（Unit Commitment）是電力系統(tǒng)運行調(diào)度一個非常重要的方面，同時也是一個非?；钴S的研究領(lǐng)域。近年來各類UC問題相繼被提出和研究，如融入隨機(jī)性很強(qiáng)的風(fēng)能發(fā)電的含風(fēng)電場的UC問題[1]、含插電式混合動力汽車的UC問題[2]等，然而火電機(jī)組仍然是最主要的組成部分。經(jīng)典的UC問題是指在一個調(diào)度周期內(nèi)滿足系統(tǒng)負(fù)荷需求和旋轉(zhuǎn)備用等條件下，確定機(jī)組的啟停計劃和機(jī)組出力，從而使得發(fā)電總費用最小，其在數(shù)學(xué)上是一個大規(guī)模的混合整數(shù)規(guī)劃問題。由于其可行解集的組合性質(zhì)，UC問題是一個NP（Nondeterministic Polynomial）難問題，即在多項式時間內(nèi)很難求解。到目前為止，嘗試用于求解UC問題的方法大致有確定性和啟發(fā)式兩大類。確定性方法主要有動態(tài)規(guī)劃法[3]、割平面法[4]、半定規(guī)劃法[5]、拉格朗日松弛法[6]和外逼近法[7]等；啟發(fā)式方法主要有遺傳算法[8]、禁忌搜索[9]和粒子群算法[10]等。 在上述方法中，啟發(fā)式方法可以很好地處理離散變量，在理論上也具有全局收斂性，但由于是隨機(jī)搜索方法，其計算效率不穩(wěn)定，且容易陷入局部最優(yōu)解。在確定性方法中，拉格朗日松弛法根據(jù)對偶理論將大規(guī)模問題分解為多個易于求解的中小規(guī)模子問題，是目前求解大規(guī)模UC問題最有效和最常用的方法之一。但由于對偶間隙的存在，該方法難以獲得UC問題的全局最優(yōu)解，且在迭代過程中容易出現(xiàn)振蕩現(xiàn)象。

Benders分解法 BDM（Benders Decomposition Method）[11-12]是求解組合優(yōu)化問題的一類經(jīng)典方法，其基本思想是將問題分解為相對易于求解的主問題和子問題，通過逐次交替迭代求解主問題和子問題來達(dá)到求解原復(fù)雜問題的目的。傳統(tǒng)的BDM中主問題是一個混合整數(shù)線性規(guī)劃問題，其求解比較費時，文獻(xiàn)[13]提出一個基于分支割平面的內(nèi)點型BDM，算法中求解的是主問題的線性松弛，并且證明了由此所產(chǎn)生的松弛型Benders割平面是全局性的有效割平面。

為了改進(jìn)傳統(tǒng)BDM的計算效率，本文基于文獻(xiàn)[13]的思想，首先結(jié)合覆蓋不等式建立一個求解離散變量為0-1變量的混合整數(shù)規(guī)劃的改進(jìn)的松弛型BDM；其次，對于經(jīng)典的UC問題，本文借助于透視割平面（PC）和線性化技術(shù)建立一個新的近似混合整數(shù)線性規(guī)劃MILP（Mixed Integer Linear Programming）模型；最后利用本文所建立的改進(jìn)的松弛型BDM求解該近似MILP模型。由于改進(jìn)的松弛型BDM的主問題是一個線性規(guī)劃問題，且中間加入了大量的覆蓋不等式，整個算法的計算效率大幅提高。10～1000臺機(jī)組24時段多個系統(tǒng)上的測試結(jié)果表明，相比于傳統(tǒng)的BDM，本文算法的計算時間大幅減少。另一方面，將測試結(jié)果與其他方法進(jìn)行比較，結(jié)果進(jìn)一步說明了本文算法是有效的。此外，本文算法可順利推廣應(yīng)用到求解其他類型的UC問題中。

1 BDM與覆蓋不等式

1.1 BDM 簡介[13]

BDM是一種分解方法，其思想是將復(fù)雜問題分解為2個相對簡單的形式，即主問題與子問題，初始主問題是原問題的一個松弛，僅包含部分約束和變量，而在子問題中，主問題中已經(jīng)考慮過的變量的值可以固定下來。以如下形式的MILP問題為例：

常稱為原始子問題，其相應(yīng)的對偶子問題為：

注意到對偶子問題（4）的可行解集與整數(shù)變量y無關(guān)，且根據(jù)對偶理論（2）可表示為：

引入一個輔助變量θ，將上述問題進(jìn)一步表示為：

式（5）稱為 Benders主問題，約束（Ⅰ）、（Ⅱ）分別稱為Benders最優(yōu)性割平面與可行性割平面。在Benders算法的具體實施過程中，通常是從HP與HR均為空集開始，然后在迭代過程中不斷更新這2個集合。算法中Benders最優(yōu)性割平面是通過求解原子問題（3）或?qū)ε甲訂栴}（4）產(chǎn)生，而 Benders 可行性割平面可通過求解另一可行性子問題來產(chǎn)生。若y為0-1變量，文獻(xiàn)[19]提出了可顯式計算產(chǎn)生的組合Benders割平面，即下述整數(shù)型割平面：

1.2 覆蓋不等式[4]

對于整數(shù)規(guī)劃問題所有的可行解而言均成立的不等式稱為有效不等式，進(jìn)一步若其對于整數(shù)規(guī)劃松弛問題的可行解而言，并不是處處成立，則稱其為割平面。下面介紹一類非常有用的有效不等式——覆蓋不等式，其能非常有效地割除連續(xù)松弛問題最優(yōu)解中整數(shù)變量的非整數(shù)值。以如下0-1背包問題為例：

為可行集YΩ的一個覆蓋不等式，其中表示集合C中元素的個數(shù)。

定理 1[4]：設(shè) C?Ω為 0-1背包約束的一個覆蓋，則覆蓋不等式（8）為0-1背包問題（7）可行解集YΩ的一個有效不等式，同時是一個割平面。

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

為方便起見，先引進(jìn)一些記號：N為機(jī)組總數(shù)，機(jī)組標(biāo)號 i=1，2，…，N；T為時段總數(shù)，時段標(biāo)號 t=1，2，…，T；αi、βi、γi為機(jī)組 i的發(fā)電費用參數(shù)；Chot，i、Ccold，i分別為機(jī)組i的熱啟動費用與冷啟動費用；分別為機(jī)組i的最小停機(jī)時間與最小運行時間；Ti，t為機(jī)組i在第t時段已連續(xù)運行時間（為正值）或連續(xù)停機(jī)時間（為負(fù)值）；Tcold，i為機(jī)組 i的冷啟動時間；PD，t為系統(tǒng)第 t時段的總負(fù)荷分別為機(jī)組 i的最小和最大出力；Pup，i、Pstart，i、Pdown，i、Pshut，i分別為機(jī)組i的功率上升速度限制、啟動功率速度限制、功率下降速度限制及停機(jī)功率速度限制；Rt為系統(tǒng)第t時段的總備用。0-1整數(shù)變量ui，t為機(jī)組i在第t時段的狀態(tài)，值為1表示機(jī)組i處于運行狀態(tài)，值為0表示機(jī)組i處于停機(jī)狀態(tài)；連續(xù)變量Pi，t為機(jī)組i在第t時段的出力。經(jīng)典UC問題的目標(biāo)函數(shù)為發(fā)電總費用FC最小，即：

其中，fi（Pi，t）為機(jī)組 i在第 t時段的發(fā)電費用，常用二次函數(shù)表示；Ci，t為機(jī)組i在第t時段的啟動費用。

UC問題的約束條件如下。

a.功率平衡約束：

b.機(jī)組出力約束：

c.爬坡約束：

d.旋轉(zhuǎn)備用約束：

e.最小啟停時間約束：

3 基于改進(jìn)的松弛型BDM與透視割平面求解UC問題

3.1 改進(jìn)的松弛型BDM

傳統(tǒng)BDM中的主問題是一個MILP問題，求解比較費時，其求解時間占用整個算法的絕大部分，為改進(jìn)傳統(tǒng)BDM的計算效率，文獻(xiàn)[13]提出一個基于分支割平面的內(nèi)點型BDM。基于文獻(xiàn)[13]的松弛思想，本文結(jié)合覆蓋不等式建立一個求解0-1 MILP問題改進(jìn)的松弛型BDM。下面給出改進(jìn)的松弛型BDM的基本步驟。

（1）初始化：給定初始上界UB與下界LB、允許誤差。

（2）當(dāng) LB＜UB-ε 時，執(zhí)行下列步驟。

步驟1：求解主問題（5）的線性松弛得到 yˉ，同時利用式（5）的目標(biāo)函數(shù)值修正下界LB。

步驟2：利用yˉ產(chǎn)生相應(yīng)的覆蓋不等式。

步驟3：利用 yˉ形成相應(yīng)的子問題（4）并求解。若子問題有解，則產(chǎn)生松弛型Benders最優(yōu)性割平面（I），同時更新HP，若子問題的解進(jìn)一步滿足整數(shù)要求，則修正上界UB；若子問題無解，則利用式（6）計算組合Benders割平面。

步驟4：將所產(chǎn)生的覆蓋不等式以及Benders割平面加入到主問題（5）中，返回步驟1。

引理 1[13]改進(jìn)的松弛型BDM步驟3中所產(chǎn)生的Benders割平面是全局性的有效割平面。

3.2 UC問題的近似MILP模型

在文獻(xiàn)[15]中，F(xiàn)rangioni與 Gentile針對一類凸的具有特定結(jié)構(gòu)的0-1混合整數(shù)規(guī)劃提出一類特殊的有效不等式——透視割平面。文獻(xiàn)[16]將其進(jìn)行了推廣，通過引進(jìn)0-1變量將一類更具一般性的混合整數(shù)非線性規(guī)劃問題進(jìn)行透視變形。為簡單起見，同時結(jié)合UC問題的特點，以如下形式的混合整數(shù)規(guī)劃為例簡單介紹透視割平面：

其中，D= [0，0]∪[pmin，pmax]×｛1｝，常數(shù) pmin≤pmax；γ、β、α為常數(shù)系數(shù)。問題（9）最好的凸松弛就是計算f（p，u）在D上的凸包絡(luò)，即求解定義在其最小上圖像上的閉凸函數(shù)。 記 f（p，u）的閉凸包為 h（p，u），即：

顯然 h（p，u）與透視函數(shù) g（p，u）=uf（p，u）相關(guān)，且當(dāng)（p，u）?D 時，由 0＜u≤1 知 h（p，u）≥f（p，u）。 所以對于連續(xù)松弛方法而言，作為目標(biāo)函數(shù)h（p，u）比f（p，u）更好，但是 h（p，u）最大的一個缺陷就是非線性程度高，且在（0，0）處不可微。 根據(jù)文獻(xiàn)[15]中的定理1可知函數(shù)h（p，u）的上圖像是由滿足以下2個條件的（z，p，u）組成：

a.upmin≤p≤upmax，0≤u≤1；

基于以上分析，將UC問題近似寫成如下MILP模型：

其中，EP、Au、AP、Du、Bu、Bp、Bz為相應(yīng)系數(shù)矩陣；cp、cup、cu、cupz為常數(shù)向量。

3.3 MILP模型的求解

由于UC問題中的旋轉(zhuǎn)備用與最小啟停時間約束僅含整數(shù)變量，且根據(jù)0-1變量值的互補(bǔ)性，很容易將其寫成0-1背包約束的形式，從而可以利用文獻(xiàn)[4]中的啟發(fā)式方法產(chǎn)生相應(yīng)的覆蓋不等式。利用透視割平面以及線性化技術(shù)將UC問題近似表示為MILP模型后，利用3.1節(jié)所建立的改進(jìn)的松弛型BDM進(jìn)行求解。松弛型BDM在求解UC問題的過程中整個問題被分解成主問題與子問題兩部分，其中主問題僅涉及到與機(jī)組啟停狀態(tài)相關(guān)的變量和一個簡單的連續(xù)變量，即：

利用主問題所得到的U，形成如下原始子問題：

求解該子問題或其對偶子問題可得到相應(yīng)的松弛型Benders最優(yōu)性割平面，而當(dāng)子問題無解時則利用式（6）產(chǎn)生相應(yīng)的整數(shù)型割平面。當(dāng)精度滿足算法終止時，整數(shù)要求并不滿足，則可采用文獻(xiàn)[4]中的方法，進(jìn)行一些啟發(fā)式調(diào)整。圖1給出具體的算法流程圖。

圖1 算法流程圖Fig.1 Flowchart of algorithm

4 數(shù)值仿真

為說明所提算法的有效性，在10～1000臺機(jī)組24時段等多個系統(tǒng)上進(jìn)行測試，其中10臺機(jī)組的發(fā)電機(jī)參數(shù)及各時段負(fù)荷數(shù)據(jù)見文獻(xiàn)[6]。20～1000臺機(jī)組的相關(guān)數(shù)據(jù)是通過復(fù)制10機(jī)組24時段系統(tǒng)的基本參數(shù)得到。旋轉(zhuǎn)備用取系統(tǒng)總負(fù)荷的10%。運行環(huán)境為AMD Athlon Dual Core Processor 4400+2.3 GHz，1 GB RAM，并在 MATLAB 2009a環(huán)境下調(diào)用 CPLEX 11[17]求解主問題與子問題。

算法中各參數(shù)的取值如下：允許誤差ε=0.005；初始上、下界分別為UB=∞、LB=0。此外，在形成透視割平面時取。

為了說明改進(jìn)的松弛型BDM比傳統(tǒng)的BDM計算效率高，對于不計爬坡約束情形，分別將這2種算法對10～1000臺機(jī)組進(jìn)行測試。2種算法的迭代次數(shù)均為2次，其他測試結(jié)果具體見表1，其中BDM表示用傳統(tǒng)的Benders分解求解UC問題新的近似MILP模型，RBDM則表示用改進(jìn)的松弛型Benders分解進(jìn)行求解。從表1可以看出，2種算法所計算得到的發(fā)電總費用基本相近，但計算時間方面，RBDM卻少了許多，RBDM的計算時間不到BDM的一半。

表1 10～1000臺機(jī)組系統(tǒng)24時段的測試結(jié)果（無爬坡約束）Table 1 Test results of 24-period，10～1000-unit systems（without ramp-rate constraint）

另一方面，由于廣義Benders分解（GBD）可直接用于求解混合整數(shù)非線性規(guī)劃問題，文獻(xiàn)[14]直接利用GBD求解UC問題。為了與文獻(xiàn)[14]中的計算結(jié)果進(jìn)行比較，下面對于40～100臺機(jī)組不計爬坡約束，并且采用相同的允許誤差進(jìn)行測試，比較結(jié)果見表2，表中“—”表示文中沒有給出結(jié)果。通過表2可以看出，除了誤差為0.004時40臺機(jī)組與100臺機(jī)組的測試結(jié)果比GBD方法稍差外，本文所提算法的其他計算結(jié)果均優(yōu)于文獻(xiàn)[14]中GBD方法的計算結(jié)果。此外，在求解不同規(guī)模UC問題時文獻(xiàn)[14]中GBD方法的迭代次數(shù)為3～5次，而本文算法則均為2次，說明本文算法具有良好的穩(wěn)定性。

表2 40～100臺機(jī)組系統(tǒng)24時段2種算法的結(jié)果比較Table 2 Comparison of test results between two algorithms for 24-period，40～100-unit systems

為了進(jìn)一步檢驗本文所提算法的有效性，對于10～100臺機(jī)組不計爬坡約束情形，再將計算得到的發(fā)電總費用和文獻(xiàn)[6]與文獻(xiàn)[18]的方法進(jìn)行比較，其中文獻(xiàn)[6]是采用拉格朗日松弛法求解UC問題，而文獻(xiàn)[18]是把UC問題近似表示為MILP模型，然后直接調(diào)用CPLEX進(jìn)行求解。在相同的條件下將計算結(jié)果進(jìn)行比較，具體見表3。通過表3可以看出，本文算法的計算結(jié)果均優(yōu)于另外2種方法的計算結(jié)果。

表3 10～100機(jī)組系統(tǒng)24時段不同算法的結(jié)果比較Table 3 Comparison of test results among different algorithms for 24-period，10～100-unit systems

對于計及爬坡約束情形，類似于文獻(xiàn)[4]，取機(jī)組爬坡約 束功率限制分別 為 Pup，i=Pdown，i=20%Pi，且不計啟動和停機(jī)功率速度限制，令 Pstart，i=Pshut，i=Pi。 用傳統(tǒng)的BDM和本文所提出的RBDM這2種方法對10～100臺機(jī)組進(jìn)行測試，測試結(jié)果也是2種算法都經(jīng)過2次迭代收斂，計算所得的發(fā)電費用基本相近，而RBDM的計算時間卻大幅減少，具體結(jié)果如表4所示。

表4 10～100機(jī)組系統(tǒng)24時段結(jié)果（計及爬坡約束）Table 4 Test results of 24-period，10～100-unit systems（with ramp-rate constraint）

5 結(jié)語

本文基于改進(jìn)的松弛型BDM與透視割平面，提出一種求解UC問題的新算法。該算法通過借助覆蓋不等式建立一個改進(jìn)的松弛型BDM，算法中大量覆蓋不等式的加入與線性松弛大幅減少了計算時間。10～1000臺機(jī)組24時段多個系統(tǒng)的數(shù)值仿真結(jié)果也證實了本文算法能在較快的時間內(nèi)獲得高質(zhì)量的次優(yōu)解。該算法為各類UC問題的有效求解提供了一條新的途徑。