新形勢下水庫調度決策單調性與動態規劃算法改進

徐章耀

【摘要】新形勢下水庫在灌溉、供水等調度中，水庫的經濟效益呈現出不同的特征。隨著供水量的增加，“邊際效用遞減”為水庫經濟效益的主要特征。為了獲得兩階段水庫調度中本時段泄水量、下一時段余留水量與最初水庫蓄水量間的單調增加關系，本文主要采用“邊際效應遞減”的假設進行分析。根據這一單調關系，進一步推廣到多階段水庫調度過程中，最終提出動態規劃算法的改進，主要包括鄰域搜索算法和搜索域縮減算法。在新形勢下水庫供水調度研究案例中，兩種動態規劃的改進算法能夠明顯地縮短規劃計算時間。

【關鍵詞】水庫調度決策；邊際效用遞減；單調性；動態規劃改進算法

1、研究背景

我國是一個水資源相當匱乏的國家，水資源的分布在時空上也不同，呈現出汛多枯少，南多北少的特點。以至于在各地出現水資源的利用率不足，浪費現象嚴重的現象。水庫的修建在一定程度上改變了這種現象，并能減少洪澇災害，有效地利用水資源。同時，水庫調度的重要性也顯現了出來，水庫調度即對水庫的控制運用，通過合理的調度控制，應用有效的調度決策，達到興利效益的一種技術措施。通過對水庫調度的改進，可以提升水庫的水資源利用效率。

2、邊際效用遞減與調度決策單調性

水庫調度問題采用動態規劃算法進行求解的基本思路是多階段水庫優化調度問題，主要考慮到它可以簡化為一系列兩階段優化問題，并且這些優化問題有遞歸方程相互聯系。為了更清晰的研究，我們將動態規劃的遞歸方程用相應的變量予以表示，其中，Ft（）表示為時段T至t的最大累計效用函數，ft（）表示時段t的水庫效用函數；將st看作水庫調度狀態變量，相應的動態規劃的遞歸方程用以下公式表示：

其中：表示在時段t初的水庫蓄水量（也即時段t-1末的水庫蓄水量）；表示在時段t內的進入水庫的入水量；表示在時段t內水庫的泄水量。

相應地，用水量平衡方程可以表示、與剩余留水量之間的關系：

水庫效用函數的凹凸性不同，決定了優化模型的不同性質。其中，當ft（）表現為凹函數時，在公式（2）所表示的兩階段優化模型呈現凹性和單調性兩個重要性質，對于凹性，即最大累積效用函數Ft（）也表現為凹函數，對于單調性，發生在時段t內的最優泄水量以及在時段t+1的最優余留水量都與時段t出的水庫蓄水量呈現出單調非減關系。其中，可以根據定理1推出其凹凸性，根據定理1和定理2推導出單調性。

定理1：設定兩個凹函數即和，定義為

則稱為凹函數。

定理2：設定兩個凹函數即和，定義為

則和x呈現單調增加的關系。

根據定理2可以說明，在總資源x增加的情況下，若想取得最大值，即分配方案達到最優，必須保證分配給和的資源量都將得到增加。在水庫的調度中，可將公式（3）中的看作為x（式5），對于公式（2）中的假設其為凹函數，又由定理1中知也為凹函數，再考慮定理2可得，在水庫優化調度中，本時段的用水量和下一時段的余留水量將隨著水庫蓄水量的增加而逐漸增加。對于效用函數為線性函數和嚴格凹函數的情況都可以應用于定理1中，在定理2推導得出結論的過程中，由于忽略了水庫調度中庫容量以及下泄水量的約束條件，因此考慮兩個約束條件，即：（1）在以及都不起約束作用的情況下，增加，相應的本時段的用水量和下一時段的余留水量也隨之增大；（2）在和其中任意一個起約束作用時，增加不能改變其對應的決策變量，但是另一個決策變量將會增長；（3）當這兩個約束都起作用時，模型（2）將會隨著的增加而沒有可行解。

3、基于調度決策單調性的動態規劃算法改進

3.1 動態規劃算法及其改進。通過對定理1和定理2的闡述，即可以確定在水庫調度過程中，時段初的水庫蓄水量與發生在時段初的最優下泄水量、時段末的最優余留水量存在的單調關系。相應的在供應鏈管理中，為了提高優化算法的效率，常將這樣的單調關系應用于縮減搜索域算法中；但在水庫的調度當中，優化解的單調性并沒有被考慮在動態規劃的算法中。因此我們做出以下假設，將分離為個取值，被分離為個取值，我們需要對剩余留水量的個離散值進行比較選取其中最大的，進而確定出每個離散值所對應的最大累積效用函數，如圖1（a）所示。

當單時段效用函數表現為凹函數時，利用單調性條件，可以將動態規劃進行簡化，即將以經得到的優化解信息設計出兩種策略進而的得到簡化動態規劃的計算。策略1，僅基于時段t初水庫蓄水量與時段t+1最優余留水量間的單調關系，若滿足s1

3.2 在考慮策略1為基礎的情況下設計搜索域縮減算法，具體如圖3所示：第一步，通過將時段t水庫蓄水量離散成個取值，且取值的間隔相等，然后將其進行從小到大依次排序，由1到進行標記，同時離散時刻t+1時段的書庫蓄水量為個取值，其間隔等于，并由1到進行依次排序標記；第二步，使q=1，q=，該設定在初始階段進行；第三步，考慮剩余在q和q間的最小最大離散值，并在其中搜索出最優余留水量，然后用其更新q和q；第四步，重復進行第三步，當個的離散值被搜索到后即可終止。

如圖2（a）所示，根據單調性原理，可以清晰的理解其提高動態規劃算法的計算效率，即在第三步的反復計算中，搜索范圍隨著q的增加以及q的減小而逐漸縮小，最終提升其計算效率，進而改進動態規劃算法。

3.3 在考慮策略2為基礎的情況下設計鄰域搜索算法，具體如圖4所示：第一步，令k=1，即的最小值，然后在q=[1，]范圍內進行搜索，找出最優值；第二步，令k=k+1，將q=、進行比較，找出最優值并更新；第三步，將第二步反復進行，直到k=時結束。將圖1和圖2進行對比，假設n==，并在動態規劃中將公式計算次，以便確定出的值，對應于動態規劃算法的計算量，搜索域縮減法的計算量是其的一半，即n+（n-1）+…+1=，鄰域搜索域算法大約是動態規劃算法的3/n，即為n+2（n-1）=3n-2。

4、結語

在求解水庫調度問題時，引入動態規劃算法簡化問題，其主要原理是將多階段調度決策簡化處理為一系列的兩階段決策，再由遞歸方程進行相互聯系，從而又將兩階段決策聯系組成為多階段決策。本文在求解水庫調度邊際效用遞減問題時，正是以兩階段優化為主要框架進行討論，進而確定時段初水庫蓄水量與最優泄水量、最優余流水量之間的單調關系，以此為基礎提出了鄰域搜索算法和搜索域縮減算法來改進動態規劃算法。在實際供水調度研究案例中，利用這兩種算法均可以搜索最終得到優化解，在減少計算時間的作用上顯著提高。

參考文獻：

[1]梅亞東，熊瑩，陳立華.梯級水庫綜合利用調度的動態規劃方法研究[J].水力發電學報，2007，（02）.

[2]劉攀，郭生練，張文選，肖義，高仕春.梯級水庫群聯合優化調度函數研究[J].水科學進展，2007，（06）.

[3]劉寧.三峽-清江梯級電站聯合優化調度研究[J].水利學報，2008，38（3）：264-271.

[4]梅亞東，熊瑩，陳立華.梯級水庫綜合利用調度的動態規劃方法研究[J].水力發電學報，2007，26（2）：1-4.

[5]劉攀，郭生練，張文選等.梯級水庫群聯合優化調度函數研究[J].水科學進展，2007，18（6）：816-825.