基于背包問題算法的中長期電力合同簽約優化問題

廣東大唐國際電力營銷有限公司 屈 源

隨著電力市場改革的不斷深入，全國多數地區都組織了符合各自特點的電力市場。在批發市場中，雖組織方式各有不同，但中長期合同都占有較大份額。在零售市場中，售電公司與用戶簽訂的代理合同都屬于中長期合同。為保證交易序列的正常開展，批發市場中的中長期合同都會設置一定上限，而零售合同因售電公司的經營特點都會對簽約有所規劃。背包問題是組合最優化中一類經典問題，可合理的控制容量并使得目標函數盡可能最優。背包問題的近似算法可在中長期合同優化中發揮巨大作用，并在數學上給出充分的理論支撐。

1 總量限制的中長期合同優化問題

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

如只是簡單對可簽約合同進行排序，往往會把單筆過大的低價合同優先選擇，最終在中長期簽約階段浪費寶貴的避險交易空間和盈利空間。在總量有所限制的情況下，如何恰當地選擇簽約對象、最終使得簽約獲利盡可能大，是發售雙方都要面對的問題，而且往往會影響相當一段時期的經營情況。盡管基于總量限制的合同簽約規劃問題適用場景有很多，但大體可抽象為一個數學模型：總量限制的中長期合同優化問題（模型1）。

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

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

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

2 相關算法

2.1 背包問題及遞歸算法

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

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

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

2.2 FPTAS 算法方案

在解決傳統背包問題時，如果輸入規模與權重本身差距不大，遞歸算法效果較為理想。本文所解決的問題實例需要針對中長期合同的收益進行權重改造，當高位數呈梯度聚類，低位數差異較小的情況時，收益函數將大幅超出輸入規模，算法的時間復雜度也將大幅提高。為在制定簽約策略時權衡算法的時間復雜度和輸出結果的準確度，下面將引入背包問題的一個FPTAS 算法。

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

定理1：算法2是背包問題的一個FPTAS，時間復雜度為O(n2[n/ε])。經過對收益函數的改造，時間復雜度和算法近似度都可通過ε 進行控制，而且定理1為算法2提供了強有力的數學支撐。

3 分量限制的中長期合同優化與多維背包問題

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

全國大部分地區電力市場在簽訂年度雙邊協商合同時，都需要把電量分解到各月。廣東在2018年雙邊協商交易過后又組織了年度集中交易，作為年度交易的補充，交易電量按供需情況以固定比例分解到月。無論是發電側還是售電方都需要分月進行匹配，而在整體規劃過后，契合每月發、用電需求成為了優化決策的又一重要目標。在電力現貨市場中，無論是哪種組織形式，中長期合同都需要進行細致分解。如沒有按照精細維度進行規劃、僅單純從總量著手，將可能因不規則交割陷入虧損風險。

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

3.1 模型2（分量限制的中長期合同優化問題）

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

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

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

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

下一步的研究將進一步把決策模型更加細化，限制條件更加具體。可把客戶根據不同的依據進行分類，再分塊規劃簽約目標。一方面可在交易中將風險分散；另一方面可對于不同類型的客戶進行差異化決策。盡可能把更多算法科學的成果，成功地應用在解決電力市場實際問題上，以應對日趨復雜的市場環境。