廣東大唐國(guó)際電力營(yíng)銷有限公司 屈 源

隨著電力市場(chǎng)改革的不斷深入，全國(guó)多數(shù)地區(qū)都組織了符合各自特點(diǎn)的電力市場(chǎng)。在批發(fā)市場(chǎng)中，雖組織方式各有不同，但中長(zhǎng)期合同都占有較大份額。在零售市場(chǎng)中，售電公司與用戶簽訂的代理合同都屬于中長(zhǎng)期合同。為保證交易序列的正常開(kāi)展，批發(fā)市場(chǎng)中的中長(zhǎng)期合同都會(huì)設(shè)置一定上限，而零售合同因售電公司的經(jīng)營(yíng)特點(diǎn)都會(huì)對(duì)簽約有所規(guī)劃。背包問(wèn)題是組合最優(yōu)化中一類經(jīng)典問(wèn)題，可合理的控制容量并使得目標(biāo)函數(shù)盡可能最優(yōu)。背包問(wèn)題的近似算法可在中長(zhǎng)期合同優(yōu)化中發(fā)揮巨大作用，并在數(shù)學(xué)上給出充分的理論支撐。

1 總量限制的中長(zhǎng)期合同優(yōu)化問(wèn)題

中長(zhǎng)期電力合同的簽訂是供需雙方之間互相選擇的過(guò)程，以最低的成本簽約是每一個(gè)市場(chǎng)主體各階段的基本目標(biāo)。在可交易空間充裕的情況下，通過(guò)排序、篩選即可完成合同的整體規(guī)劃，但是在實(shí)際操作中將面臨較多限制。發(fā)電企業(yè)受到裝機(jī)容量、計(jì)劃?rùn)z修等諸多因素影響，可簽訂的實(shí)物交割中長(zhǎng)期合同有限。在集中式現(xiàn)貨市場(chǎng)中，具有期權(quán)性質(zhì)的差價(jià)中長(zhǎng)期合同可簽約上限也受到機(jī)組類型、發(fā)電成本、交易策略等因素綜合影響。售電企業(yè)為使中長(zhǎng)期合同發(fā)揮最大的避險(xiǎn)、套利作用，交易空間同樣要有所限制。

如只是簡(jiǎn)單對(duì)可簽約合同進(jìn)行排序，往往會(huì)把單筆過(guò)大的低價(jià)合同優(yōu)先選擇，最終在中長(zhǎng)期簽約階段浪費(fèi)寶貴的避險(xiǎn)交易空間和盈利空間。在總量有所限制的情況下，如何恰當(dāng)?shù)剡x擇簽約對(duì)象、最終使得簽約獲利盡可能大，是發(fā)售雙方都要面對(duì)的問(wèn)題，而且往往會(huì)影響相當(dāng)一段時(shí)期的經(jīng)營(yíng)情況。盡管基于總量限制的合同簽約規(guī)劃問(wèn)題適用場(chǎng)景有很多，但大體可抽象為一個(gè)數(shù)學(xué)模型：總量限制的中長(zhǎng)期合同優(yōu)化問(wèn)題（模型1）。

給定一個(gè)客戶集S={s1,s2…sn-1,sn}，尺寸函數(shù)c∶S →R+，收益函數(shù)p∶S →R+，尺寸限制B ∈R+：

其中,客戶集S 代表可簽約客戶，尺寸函數(shù)c(si)表示客戶si的簽約電量，收益函數(shù)p(si)表示與客戶si的簽約所能獲得收益。優(yōu)化模型表示從客戶集S 中尋找一個(gè)子集，在子集客戶的簽約電量之和小于簽約限制B 的情況下，使得子集客戶簽約收益之和盡可能大。

雖然該模型是一個(gè)從不同中長(zhǎng)期簽約規(guī)劃情景提煉的一個(gè)共性模型，但與背包問(wèn)題的數(shù)學(xué)模型很相近。背包問(wèn)題是組合優(yōu)化中的一個(gè)經(jīng)典問(wèn)題，只是背包問(wèn)題的所有函數(shù)映射的值域?yàn)檎麛?shù)。對(duì)于模型1的任意實(shí)例，如把所有函數(shù)值的精度改造為整數(shù)，便構(gòu)造成了背包問(wèn)題的一個(gè)實(shí)例。例如，需要考慮到小數(shù)點(diǎn)后k 位的收益，則可以定義權(quán)重函數(shù)；如果權(quán)重函數(shù)前j 位普遍相同，則可把前j 位權(quán)重截去，僅考慮尾數(shù)權(quán)重。經(jīng)過(guò)改造后的簽約模型，便可借助背包問(wèn)題的有效算法，在大量的可簽約對(duì)象中找出合理的簽約方案。同時(shí)也可借助數(shù)學(xué)中對(duì)背包問(wèn)題的研究，更深刻地理解總量限制的中長(zhǎng)期合同優(yōu)化問(wèn)題。

2 相關(guān)算法

2.1 背包問(wèn)題及遞歸算法

背包問(wèn)題是一個(gè)看似簡(jiǎn)單的問(wèn)題，因?yàn)轵?yàn)證一個(gè)可行解很容易。給出兩個(gè)可行解，比較哪個(gè)選擇更優(yōu)也很容易。算法科學(xué)雖然證明了背包問(wèn)題屬于NP 類問(wèn)題，但也同時(shí)證明了背包問(wèn)題是NP 完備性問(wèn)題。目前還沒(méi)有多項(xiàng)式時(shí)間復(fù)雜度的算法求解此類問(wèn)題，如果引入一個(gè)近似度不高的近似算法，在簽約策略優(yōu)化中將同樣造成一定的浪費(fèi)。如果備選客群電量較為分散，每一份合同簽約電量相比簽約限制占比較低，引入背包問(wèn)題的近似算法所得結(jié)果可能劣于傳統(tǒng)排序定界的方法。為更好地解決本文所要解決的實(shí)際問(wèn)題，引入一個(gè)偽多項(xiàng)式時(shí)間復(fù)雜度的遞歸算法：算法1。

給定{S,B;c,p},其中S={s1,s2…sn-1,sn}，B＞0，c∶S →Z+，p∶S →Z+，；對(duì)于q ∈{1,2,…,nP}，i ∈{1,2,…,n}，通過(guò)遞歸求得（if Si,q不存在，則A(i,q)=+∞）。初始化A(i,q)，遞歸：，輸出max{i|A(i,q)≤B 及相應(yīng)的Si,g。

算法1可求得背包問(wèn)題實(shí)例的最優(yōu)解，時(shí)間復(fù)雜度達(dá)為O(n2P)，不僅與集合規(guī)模n 有關(guān)，且與收益函數(shù)最大值相關(guān)。遞歸算法在找出總量限制的最優(yōu)簽約方案的同時(shí)，也給出了不同收益期望、不同合同數(shù)量的最優(yōu)簽約規(guī)模。不僅實(shí)現(xiàn)了總量控制的最優(yōu)決策，還可通過(guò)其他收益情況的最優(yōu)簽約規(guī)模修正決策中的總量限制B，最終達(dá)到整體最優(yōu)決策。

2.2 FPTAS 算法方案

在解決傳統(tǒng)背包問(wèn)題時(shí)，如果輸入規(guī)模與權(quán)重本身差距不大，遞歸算法效果較為理想。本文所解決的問(wèn)題實(shí)例需要針對(duì)中長(zhǎng)期合同的收益進(jìn)行權(quán)重改造，當(dāng)高位數(shù)呈梯度聚類，低位數(shù)差異較小的情況時(shí)，收益函數(shù)將大幅超出輸入規(guī)模，算法的時(shí)間復(fù)雜度也將大幅提高。為在制定簽約策略時(shí)權(quán)衡算法的時(shí)間復(fù)雜度和輸出結(jié)果的準(zhǔn)確度，下面將引入背包問(wèn)題的一個(gè)FPTAS 算法。

算法2： FPTAS 算法。給定{S,B;c,p},其中S={s1,s2…sn-1,sn}，B＞0，c∶S →Z+，p∶S →Z+,設(shè)置ε＞0，計(jì)算K=εP/n。對(duì)A∈S，計(jì)算P＊(si)=p(si)/K，運(yùn)用算法1解決{S,B;c,p＊}。

定理1：算法2是背包問(wèn)題的一個(gè)FPTAS，時(shí)間復(fù)雜度為O(n2[n/ε])。經(jīng)過(guò)對(duì)收益函數(shù)的改造，時(shí)間復(fù)雜度和算法近似度都可通過(guò)ε 進(jìn)行控制，而且定理1為算法2提供了強(qiáng)有力的數(shù)學(xué)支撐。

3 分量限制的中長(zhǎng)期合同優(yōu)化與多維背包問(wèn)題

總量限制的簽約優(yōu)化是中長(zhǎng)期交易決策的一個(gè)方面，在很多情況下受到電量交割、供需匹配等因素的限制，對(duì)電量合同分量也有一定限制。在考慮總量限制后提高考量維度，可進(jìn)一步優(yōu)化策略。

全國(guó)大部分地區(qū)電力市場(chǎng)在簽訂年度雙邊協(xié)商合同時(shí)，都需要把電量分解到各月。廣東在2018年雙邊協(xié)商交易過(guò)后又組織了年度集中交易，作為年度交易的補(bǔ)充，交易電量按供需情況以固定比例分解到月。無(wú)論是發(fā)電側(cè)還是售電方都需要分月進(jìn)行匹配，而在整體規(guī)劃過(guò)后，契合每月發(fā)、用電需求成為了優(yōu)化決策的又一重要目標(biāo)。在電力現(xiàn)貨市場(chǎng)中，無(wú)論是哪種組織形式，中長(zhǎng)期合同都需要進(jìn)行細(xì)致分解。如沒(méi)有按照精細(xì)維度進(jìn)行規(guī)劃、僅單純從總量著手，將可能因不規(guī)則交割陷入虧損風(fēng)險(xiǎn)。

假設(shè)有A、B兩個(gè)增量合同，總電量相同，合同A 總量收益略高于合同B，但合同A 與現(xiàn)有存量合同的各分量相關(guān)性較高。如僅考慮總量限制則更傾向于合同A；把合同A 分解到各分量后，將導(dǎo)致原接近限值的分量超出限制；反之，如果選擇合同B 進(jìn)行簽約，則使得整體在各分量中更加均勻。因此在中長(zhǎng)期合同簽約決策時(shí)，多維度考慮分量限制可達(dá)到更好的效果。

3.1 模型2（分量限制的中長(zhǎng)期合同優(yōu)化問(wèn)題）

給定{S,B;C,p}，其中有n 個(gè)客戶集S={s1,s2…sn-1,sn}，尺寸限制向量B={b1,b2,…,bk}為k 個(gè)維度的尺寸限制，尺寸矩陣，度電收益函數(shù)p∶S →R+：

其中，客戶集S 同樣代表可簽約客戶；尺寸矩陣C 中的任意元素ci,j表示客戶si在第j 個(gè)維度的簽約電量；度電收益函數(shù)p(si)表示客戶si簽約每度電所能獲得的收益；對(duì)于∈B 表示第j 維度分量限制上限。目標(biāo)是在客戶集S 中選擇一個(gè)子集S＊，在每個(gè)維度電量之和低于約束上限情況下，使得簽約收益盡可能大。

模型2恰好與多維背包問(wèn)題的數(shù)學(xué)模型將近，通過(guò)多維背包問(wèn)題的算法可完美地解決分量限制的中長(zhǎng)期合同優(yōu)化問(wèn)題。多維背包問(wèn)題是0-1背包問(wèn)題的集合，如果在j ≥2時(shí)有bj＞，多維背包問(wèn)題便轉(zhuǎn)化成0-1背包問(wèn)題。進(jìn)而多維背包問(wèn)題同樣是NP-完備性問(wèn)題，目前還沒(méi)有多項(xiàng)式時(shí)間復(fù)雜度的算法可求解。目前可運(yùn)用動(dòng)態(tài)規(guī)劃、分支定界、枚舉等算法求得最優(yōu)解。在數(shù)據(jù)較為復(fù)雜時(shí)，最優(yōu)算法的運(yùn)算量將過(guò)于龐大，而且輸出解的改進(jìn)程度可能很小。目前工程上普遍采用貪心算法、遺傳算法、蟻群算法等啟發(fā)式算法進(jìn)行求解，雖然不能得到最優(yōu)解，甚至輸出解的近似程度也不能準(zhǔn)確估計(jì)，但可通過(guò)算法較為快速的進(jìn)行科學(xué)決策。

綜上，市場(chǎng)用戶準(zhǔn)入范圍還比較有限，目前市場(chǎng)用戶類型比較集中。在交易決策中，簽約意向客戶數(shù)量還比較有限。隨著市場(chǎng)準(zhǔn)入門檻逐步降低，準(zhǔn)入用戶類型將趨于復(fù)雜，單純的枚舉測(cè)算將不能滿足決策需求。電力合同簽約決策運(yùn)算復(fù)雜度將大幅提高，選擇有效可行的算法十分必要。

下一步的研究將進(jìn)一步把決策模型更加細(xì)化，限制條件更加具體?？砂芽蛻舾鶕?jù)不同的依據(jù)進(jìn)行分類，再分塊規(guī)劃簽約目標(biāo)。一方面可在交易中將風(fēng)險(xiǎn)分散；另一方面可對(duì)于不同類型的客戶進(jìn)行差異化決策。盡可能把更多算法科學(xué)的成果，成功地應(yīng)用在解決電力市場(chǎng)實(shí)際問(wèn)題上，以應(yīng)對(duì)日趨復(fù)雜的市場(chǎng)環(huán)境。