3.3 动态规划在水资源管理中的应用
动态规划在输水线路优选、水量最优分配，水资源配置，水资源调度和运行管理，节水灌溉优化等水资源管理很多方面得到了广泛的应用。下面选取几类简单例子介绍如下。
1.输水线路选择
前面[例3.1]就是输水线路选择问题。
2.水资源量最优分配
有限的水资源，如何科学地分配给若干个部门，使其总效益最大？ 例如单位供水量所创造的产值最大，经济效益或社会效益最高或水资源的有效利用率最高等，都属于这类水资源的最优分配问题。
一般说，其一部分配到的水资源量多，其效益也大。两者之间的关系，可能是线性的，而多数是非线性的，可能是连续函数关系，或者是离散的数值对应关系。这类本来属于静态问题，引入“时间”因素后就可转化为动态规划问题。即把同时给几个部门最优配水问题，视为分阶段依次对这些部门进行最优供水，并分阶段做出决策，使各部门的总效益最大，然后按动态规划法求解。
【例3.3】有可供水量Q=8（单位），考虑向A、B和C三个城市供水。已知三城市供水量的效益见表3.1，问如何给三城市分配水量才能使总效益最大？（陈爱光等，1991）
表3.1 A、B、C三城市供水效益表
从上面数据看，比如A 城市有1和2个单位水量时，效益分别是6和12，但3个单位水量时，效益则为35（可能由于水量的增加，新上了效益好的企业，城市用水整体效益马上就提高了）。很明显，这个问题不属于线性规划问题。
解：该问题没有阶段性，可以人为设置为不同阶段问题。设给三城市供水分为3个阶段（i=1，2，3），第1阶段考虑同时给三市供水，第2阶段给B 及C 两市洪水，第3阶段只给C市供水（这么设主要考虑逆序求解方便）。
设决策变量xi为第i阶段分配水量（逆序递推即为分配给第i城市水量：i=3，分配给C市水量；i=2，分配给B市水量；i=1，分配给A 市水量），状态变量qi为第i阶段可供水量，则有数学模型：
可供水量0≤q3≤8
可分配水量x3=q3
计算结果可以直接从表3.1中查出，见表3.2。
表3.2 单独向C市供水计算效益表
第二步：i=2，考虑向B、C二市供水。
可供水量：0≤q2≤8
状态转移方程：q3=q2-x2
q2=8时，x2为分配给B市的水量，取值为0～8共9种状态，每种均需要做出决策。计算如下：
此时x2可有0～8共9种取值状态，计算如下：
q2=7时，x2为分配给B 的水量，取值为0～7共8种状态，每种均需要做出决策。计算如下：
此时x2可有0～7共8种取值状态，计算如下：
其他q2=6、q2=5、q2=4、q2=3、q2=2、q2=1、q2=0可以类似计算，结果见表3.3。
表3.3 同时向B、C二城市供水计算效益表
第三步：i=1，考虑向A、B、C三市同时供水。
可供水量：0≤q1≤8
状态转移方程：q2=q1-x1
q1=8时，x1为分配给A 市水量，取值为0～8共9种状态，每种均需要做出决策。计算如下：
此时x1可有0～8共9种取值状态，计算如下：
其他q2=7、q2=6、q2=5、q2=4、q2=3、q2=2、q2=1、q2=0可以类似计算，结果见表3.4。(https://www.daowen.com)
表3.4 同时向A、B、C三城市供水计算效益表
从表中可以看出，f*1（8）=130 就是水量分配最大效益，最优方案是分配给第1个城市（A）市最优水量x1（8）=4。余下的4 个单位按表3.3 分配，即分配给第2个城市（B）最优水量x2（4）=4，最后是x3（0）=0，即不分配给第3 个城市（C）。汇总见表3.5。
表3.5 A、B、C三城市最优水量分配表
当分配水量小于8个单位时，不用重新求解，可以直接从表中查询最优分配结果。比如，如果可分配水量为7 个单位，最优解为最大效益是117，x1（7）=4，x2（3）=0，x3（3）=3（即A 分配4个单位水量、B不分配、C 分配3个单位水量）。即动态规划不仅仅可得到最优分配结果，还可以得到许多有益的中间信息。
【例3.4】用动态规划标号法求解[例3.3]问题（鲍新华，1993）。
[例3.3]水量分配问题，可以根据表3-1数据，设给三城市供水分为3个阶段（i=1，2，3），第1阶段考虑同时给A、B、C 三市供水，第2 阶段给B 及C 两市洪水，第3阶段只给C市供水。画出水量分配网络图（图3.6），该图与输水线路选择图3.1类似。
由于图3.6中空间小，各状态效益（决策）ri（xi）未在图中标注，如第一阶段由状态8至状态2线上应该标出91（6），表示给A 市分配6个单位水量效益为91，分配前状态为8个单位水量，分配后状态为2个单位水量。采用动态规划标号法求得最大效益为130（图3.5），此时各阶段始末状态为8-4-0-0，即最优分配方案为A 市分配4个单位，B市分配4个单位，C市不分配。
图3.5 A、B、C三城市水量分配标号法求解结果
图3.6 多阶段水量调度网络图及动态规划标号法求解结果（圈点上方数字为标号值）
3.水资源调度和运行管理
【例3.5】某水源公司在5个时期内需要保证有足够的水量供应一个地区。公司拥有一座调蓄用的水库，最大库容40个单位，随时可以调入水源加以补充蓄水，以备下期供水。且在每个时期开始，公司均能向全部用户供水。设每时期水库单位水量储存费用为0.1，每次调入水量（不论多少）的费用为20。I时期开始调入水量为xi，并按Δ=10整数增量。第一期开始和最末期结束，水库蓄水量均为零。现要求在满足规划期全部需水量（各时期需水量Di分别为10、20、30、30、20）的条件下，使总供水量费用最小，采用动态规划法标号进行水量最优调度（鲍新华，1993）。
根据上述问题，可分析给出该问题的水量调度网络图（图3.8）。由于图中空间小，图上仍未标出储水费用ri（xi）。
采用标号法求解，结果直接标在了图3.6上，图中最优方案线条进行了加粗。
从图3.6可见，各阶段始末状态与决策一目了然。该方案最小费用为64，此时各阶段始末状态为0-20-0-20-20-0，即最优蓄水方案为30-0-30-50-0。
本例题还可以采用递推公式求解。
4.几种方法简单比较
从上面输水线路选择、水量最优分配、水库蓄水最优调度3个例子对比看，对于较简单的问题，采用标号法求解更方便。标号法的结果是由末端生长到起点的一棵树，达到起点的最远枝干就是最优方案。如果有多个最优方案，图上也一目了然。同时，对于较复杂的问题，网络图的绘制，也有利于对问题的进一步理解。
上面几个动态规划模型，一般具有这么几个特点：①不同问题，数学模型不同，求解的程序有差别，不易编制统一的计算机程序；②具体问题的各阶段状态变量及决策变量集合是已知或可知的；③系统的始末一般只有一种状态。
对于上面的动态规划问题，可以形成同输水线路性质一样的网络图，有了这样的网络图，就可以采用统一的计算机程序求解。LINGO、MATLAB等均可求解动态规划问题。
5.动态规划的LINGO 求解
一般动态规划，如果能形成类似输水线路网络图的初始网络，就可以采用统一的计算机程序求解。以LINGO 软件为例，求解[例3.1]的动态规划问题如下。
【例3.6】用LINGO 软件求解[例3.1]。
打开LINGO 演示版软件，主面板输入程序如图3.7 所示，计算结果如图3.8所示。
图3.7 [例3.6]LINGO求解程序
图3.8 [例3.6]LINGO程序求解结果
运行结果显示最优值为18[D（A）=18，其余D 为标号法求的局部最优值]，最优路线为A-E-2F-1G-1B（P 值为1表示为局部最优，连接起来就是最优路线）。
LINGO 的函数及命令可进一步参照软件说明，这里不多介绍。
练 习 题
3.1 水源地为A，需从水源地引水至D 城，供水管路要经过B，C 两个地点，且每个地点又有多个可供选择的方案（图3.9），管路可能经过的线路及各路段的输水费用如图3.9所示，试采用动态规划标号法和逆序递推公式计算选择一条输水费用最小的路线。[答案：f*1（A）=9，最优路线A-B3-C2-D]
图3.9 水源地A到城市D可能的输水线路
3.2[例3.3]中表3.1中去掉最后2列，即可用分配水量共6个单位，采用递推公式和标号法求解最优水量分配问题。
图3.10 A、B、C三城市水量分配网络图
3.3 采用动态规划递推公式求解[例3.5]。
