新形勢下水庫調(diào)度決策單調(diào)性與動態(tài)規(guī)劃算法改進(jìn)

徐章耀

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

【關(guān)鍵詞】水庫調(diào)度決策；邊際效用遞減；單調(diào)性；動態(tài)規(guī)劃改進(jìn)算法

1、研究背景

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

2、邊際效用遞減與調(diào)度決策單調(diào)性

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

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

相應(yīng)地，用水量平衡方程可以表示、與剩余留水量之間的關(guān)系：

水庫效用函數(shù)的凹凸性不同，決定了優(yōu)化模型的不同性質(zhì)。其中，當(dāng)ft（）表現(xiàn)為凹函數(shù)時，在公式（2）所表示的兩階段優(yōu)化模型呈現(xiàn)凹性和單調(diào)性兩個重要性質(zhì)，對于凹性，即最大累積效用函數(shù)Ft（）也表現(xiàn)為凹函數(shù)，對于單調(diào)性，發(fā)生在時段t內(nèi)的最優(yōu)泄水量以及在時段t+1的最優(yōu)余留水量都與時段t出的水庫蓄水量呈現(xiàn)出單調(diào)非減關(guān)系。其中，可以根據(jù)定理1推出其凹凸性，根據(jù)定理1和定理2推導(dǎo)出單調(diào)性。

定理1：設(shè)定兩個凹函數(shù)即和，定義為

則稱為凹函數(shù)。

定理2：設(shè)定兩個凹函數(shù)即和，定義為

則和x呈現(xiàn)單調(diào)增加的關(guān)系。

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

3、基于調(diào)度決策單調(diào)性的動態(tài)規(guī)劃算法改進(jìn)

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

當(dāng)單時段效用函數(shù)表現(xiàn)為凹函數(shù)時，利用單調(diào)性條件，可以將動態(tài)規(guī)劃進(jìn)行簡化，即將以經(jīng)得到的優(yōu)化解信息設(shè)計出兩種策略進(jìn)而的得到簡化動態(tài)規(guī)劃的計算。策略1，僅基于時段t初水庫蓄水量與時段t+1最優(yōu)余留水量間的單調(diào)關(guān)系，若滿足s1

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

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

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

4、結(jié)語

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

參考文獻(xiàn)：

[1]梅亞東，熊瑩，陳立華.梯級水庫綜合利用調(diào)度的動態(tài)規(guī)劃方法研究[J].水力發(fā)電學(xué)報，2007，（02）.

[2]劉攀，郭生練，張文選，肖義，高仕春.梯級水庫群聯(lián)合優(yōu)化調(diào)度函數(shù)研究[J].水科學(xué)進(jìn)展，2007，（06）.

[3]劉寧.三峽-清江梯級電站聯(lián)合優(yōu)化調(diào)度研究[J].水利學(xué)報，2008，38（3）：264-271.

[4]梅亞東，熊瑩，陳立華.梯級水庫綜合利用調(diào)度的動態(tài)規(guī)劃方法研究[J].水力發(fā)電學(xué)報，2007，26（2）：1-4.

[5]劉攀，郭生練，張文選等.梯級水庫群聯(lián)合優(yōu)化調(diào)度函數(shù)研究[J].水科學(xué)進(jìn)展，2007，18（6）：816-825.