新形势下水库调度决策单调性与动态规划算法改进

徐章耀

【摘要】新形势下水库在灌溉、供水等调度中，水库的经济效益呈现出不同的特征。随着供水量的增加，“边际效用递减”为水库经济效益的主要特征。为了获得两阶段水库调度中本时段泄水量、下一时段余留水量与最初水库蓄水量间的单调增加关系，本文主要采用“边际效应递减”的假设进行分析。根据这一单调关系，进一步推广到多阶段水库调度过程中，最终提出动态规划算法的改进，主要包括邻域搜索算法和搜索域缩减算法。在新形势下水库供水调度研究案例中，两种动态规划的改进算法能够明显地缩短规划计算时间。

【关键词】水库调度决策；边际效用递减；单调性；动态规划改进算法

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.