1、动态规划概述
动态规划是最优化领域中的一个重要分支，是一种研究多段决策过程的递推最优化方法。所谓多段决策过程，是指根据时间、空间或其它特性可将过程分为若干互相联系的阶段，而在每个阶段必须作出决策的过程。凡是能作为多段决策过程来考虑的问题，都可应用动态规划求解。 由于“阶段”常常是与时间有关的动态问题，因而被称为动态规划。但动态规划实际上也可求解与时间无关的静态问题。由于动态规划一般是从最末一个阶段开始求解，一段段递推到始点，最后解决全过程的最优化问题，所以也称“递推最优化”。把求解过程作为一个连续的递推过程的基础是动态规划的核心一最优化原理。
2、动态规划原理和方法
现用实例说明动态规划法的基本原理和应用 设要修建一条引 水线路，如上图所示。取水口位于 X41 ，终点为X0，中间必需通过x1、X2、X3 站。经勘测，每站有3个节点，且给出各站节点间线路段的费（连线上的数字）。现要求选择出一条从 X4 到 X0 的引水线路，使总费用为最小。
2.1 用穷举法求解
为了比较，先用穷举法，即把全部方案一一列举出来进行计算求解。从 X4 到 X0 的全部可能方案如下图所示，共计17个方案。把每个方案中 4 段线路的费用加起来，即得该方案的总费。取总费用最小者即为最优方案，本例为 X4—X31–X22–X11–X0，如图总费用为：6 + 3 + 6 + 2=17。每个方案有4段线路，要进行3次费用相加，17个方案的计算工作量共计为51次加法运算。
2.2 用动态规划法求解
现在用另一种方法来寻找最优线路方案。这个问题是个多段决策问题，可把全线路分为4段，即 X4X3、 X3X2、X2X1、X1X0 共4段。任何一条从 X4 到 X0 的线路必由该4段组成。但每一段有若于条线路方案可供选择。同理，可以采用从终点 X0 向始点 X4 的逆序方向逐段寻优，为此，把从 X0 到 X4 的总引水线路按逆序方向编号，以便于计算。用动态规划方法只需进行加法运算17次即可求得最优结果。可见，动态规划法能大大节省计算工作量。
3、模型的组成
要把一个实际问题构造为动态规划的数学模型，必须包括3个变量、2 个方程、1 个约束。 .
3.1 三个变量
阶段变量：动态规划是研究多段决策过程的一种数学方法，这里的段即阶段，例如按时间分段，则时段即为阶段；或者按所研究问题的实际情况进行分段，但不管是与时间有关的或无关的问题，必须满足无后效性的要求，即本阶段发生的事仅影响后面各阶段的事，对它以前的阶段的事没有影响。. 状态变量：它完整地描述系统在各阶段所有可能发生的状态，常用 xi (或 xt) 表示， xi 表示第 i 阶段开始时的状态。如下图，第 3 阶段的状态集合为：
决策变量和决策序列：当某阶段的状态给定后，可以选择不同的决策，使以后各段的状态依不同的方式演变。例如，第2段的状态 X22 ，可供选择的决策 d 共有3个，即 d112、d122、d131，若选决策 d122，则第2阶段末的状态转入 X12 等。描述决策的变量 di ，称为决策变量。 决策序列是一个按顺序排列的决策集合。例如，从 X4 到 X0 经过4段，每段均需作出决策，从 X4 到 X3 的第4段有 3 个决策d31. d32、d33，即有3条路线可供选择，需作出决策走那一 条路线，选定后则转入第3段，在第3段再需作出决策，一直到终点为止，这是一一个多段决策过程。在这个多段决策过程中有许多可供选择的方案，该例中共有17条线路方案可供选择，每一条线路方案都由每段的1个决策组成共4个决策构成。该实例共有17个决策序列可供选择，该17个决策序列即为该例的允许决策序列集合或决策序列.空间。根据所研究课题的目标的要求，其中最优者即为最优决策序列，该例的目标为费用最小，其最优决策序列为： .
3.2 二个方程式
状态转移规律(系统方程)：它是联系阶段变量、状态变量和决策变量三者相互关系的方程式。若在第 i 阶段，已给定状态变量 xi 的值，如该阶段的决策变量 di 一经确定，则第 i-1 阶段的状态变量 xi-1 的值也就完全确定了。 xi-1 的值随 xi 和 di 的不同而变化。它们之间有如下确定的对应关系： 这个关系式表示由阶段 i 到阶段 i-1 的状态转移规律，为动态规划的状态转移方程或称系统方程。该关系式为系统仅有1个状态变量和1个决策变鼂的情况。当有n个状态变量和决策变量时，函数 Ti 将包括阶段的全部状态变量和决策变量。
阶段效应和目标函数方程：在最优化过程中，需要确定一个用来衡量实现预定任务好坏的数量指标，即目标，例如目标为要求效益最大或要求费用最小等。各阶段输入状态 xi 和决策变量 di 不仅决定了该阶段的输出状态 xi-1 ，而且决定了该阶段对自标函数的贡献，即阶段效应 ri，它们之间也是一个函数关系： ri = gi (xi,di)。全部n个阶段的目标总值为: 目标函数常用 f(x) 或 f (x,d) 表示。若系统的起始状态为 xn，要求到最终状态为止的某个数量指标最优(最太或最小等)，则该问题的目标函数方程为： 应用动态规划最优化原理，则上式变为： 如果目标是1个，则称单目标问题;如为许多目标，则为多目标向题。
3.3 一个约束条件
约柬条件是完成某项任务的客观条件，包括状态空间 S 和决策空间 D，以 xi ∈ S 和 di ∈ D 表示。例如水库的兴利蓄水最高不得超过正常蓄水位和防洪限制水位，最低不应低于死水位；水电厂的最大决策出力不能大于装机容量和水头预想出力等。在约束条件中，一种是不可改变的，例如水电厂的最犬出力，受发电机组设备条件限制，不能大于装机容量，另一种是人为的可改变的，例如供水期各月电力系统，对某水电厂发最小出力的要求，常常是可改变的。
最优化愿理为：一个最优决策序列 ( dn，dn-1 … di … d2, d1 ) 具有这样的性质，不论初始状态 xi 和初始决策 di 怎样，对于由 xi 和 di 所确定的状态 xi-1 来说，在此以后的决策 dn-1, dn-2 … d2, d1 必构成最优决策序列。简言之，即最优决策序列的后部子决策序列一定也是最优的。 . 归结起来，动态规划的基本原理主要有以下两点： 一是最优决策序列，只要从当前的状态出发，使面临段的效应和余留期的最优目标值之和达到最优。 二是最优决策序列只与当前的状态及目标有关，与过去的历史无关。也就是说只要有了当前的状态，就可作出决策，与此前如何到达当前的状态无关，过去的历史只能通过当前的状态去影响未来的发展。也就是动态规划要求系统的状态具有马尔柯夫过程的性质，这个性质也称为多段决策过程的无后效性，这是应用动态规划的一个重要条件。
4、确定型动态规划及具有长期径流预报的水库优化调度
动态规划模型分为确定型和随机型两类，在模型中有随机因素时，为随机型动态规划，否则，为确定型动态规划。
4.1 问题和条件
讨论用确定型动态规划解决单–水库的最优调度问题。由于1年内供水期的径流比较稳定，长期预报比较可靠准确，而且年调节水库的供水期是确定保证电量的控制时期，因而在已知供水期各阶段径流的情况下，找出供水期最优调度方案，是水利水电规划中的一个重要课题。
设某水电站水库具有年调节性能，已知供水期为11~6月共8个月，供水期初水库水位为正常蓄水位 735 米，供水期末水库水位为死水位 694 米，现已知供水期各月天然流量，扣除水库水量损失和上游灌溉用水后，如表1一1所示，要求在满足各种约束条件下找出供水期总发电量最大的最优调度线。须满足的约束条件包括:允许最小流量 Q’,在11、 5、6月为下游灌溉用水500、900、750米3 /秒，其它各月为工业城市用水200米3/秒；允许最大流量Q"，除三月下游防凌要求不得超过443 米3/秒外，其它各月为扣除机组计划检修后的水电站最大过水能力。水库的允许最小蓄水量V’，为相应于死水位的蓄水量411.6米3/秒·月；允许最大蓄水量 V" 为相应于正常蓄水位的蓄水量1948.6米3/秒·月。允许最大出力N"，在以下4个出力中取小值：水头预想出力、5、6月的装机容量116万千瓦、11- 4月扣除1台机22.5万千瓦进行计划检修后的最大可用出力93.5万千瓦、此外，由于本电站除供当地用电外，还向邻省送电，近期因受当地负荷、向邻省输电能力和担任调峰的限制，6月的最大平均出力不得大于100万千瓦。在本题中暂不考虑电力系统对本水电站各月最小平均出力N’的要求和本水电站对下游梯级水电站效益的影响。本水电站出力系数为8.3，并已知水库水位库容关系曲线和下游水位流量的关系。
4.2 数学模型
阶段变量i：由于水库调度是按时间过程进行的，属于多段决策过程，阶段可按时间段选取，根据调度要求和径流资料情况，可取1个月、1旬或0.5个月为一时段，也可根据限制条件和资料情况不同采用月和旬等相结合。例如本题3月因防凌要求(为20天)， 可采用以旬为一时段， 其它各月均以月为一时段，现为简化均取1个月为一个时段，i= 1, 2, … n, n = 8，进行逆序排列， 6月为第1阶段，5月为第2个阶段…11月为第8个阶段。
状态变量：可以选用月初水库水位 Zi 或月初水库蓄水量 Vi， 它们都能反应调度过程的演变，并满足无后效性要求。本题采用月初蓄水量 Vi 为状态变量。该状态是在正常蓄水位相应的库容和死库容之间连续变化的，为便于计算，把它离散化，取水库水位变化 3 米为一间隔(步长)，相应于该水位的水库蓄水量为一状态。这样，时段的分割和状态的分格形成一个网格，如图1–9所示。从各阶段间网格交点连线组成的谓度线群中来选择最优调度线。这种求解方法称为格点法，它是求解动态规划问题中使用很广的一种方法。格点愈多，计算工作量愈大，所得结果的精确度也愈高；反之，格点愈少，计算工作量愈小，但所得结果的精度也愈差。格点的多少，应根据精度要求具体分析确定。
决策变量：选用各时段的发电用水量 Qi (m3/s·月)相应于一个决策，就有一个阶段效应(本题为发电量)，即 Ni( Vi, Qi) ，可根据公式 Ni = 8.3QiHi(万千瓦月)算出。
状态转移规律：结合水库调度情况及本题所采用的状态变量和决策变量，状态转移规律为： 式中 qi —— 时段的净入流量(见表1-1) T—— 时段的时间，当取1个月为1时段、且 V 以m3 /秒*月计算时，则T常省赂不写; . Vi-1 —— 第 i 时段末、即 i-1 时段初的水库蓄水量。
目标函数和递推方程：目标是供水期总发电量最大。目标函数和递推方程为： 式中 Ni(Vi, Qi) —— 面临段 i 在时段初水库蓄水量为 Vi 和该时段发电用水量为 Qi 时的发电量 Ni-1(Vi-1)—— 余留期 (从 i-1 时段到第 1 时段) 最优发电量 Ni(Vi) —— 从时段初水库蓄水量 Vi 出发，从时段 i 到时段1 的最优发电量
约束条件为:
4.3 模型求解
在约束条件下应用 目标函数和递推方程，状态转移规律进行计算，采用逆序递推法，步骤如下：
第1时段 将 i = 1代入，得 由于本时段为原问题的最后时段, N0 (V0) = 0
同理，将 i = 1 代入状态转移规律得
因本时段末水库水位均要求降到死水位，所以 V0 为一固定值，V0 = 411.6米3/秒·月。由于时段末固定，因而对时段初的任一个状态( 蓄水量)来说，本时段只有唯一的一条调度线，即时段初蓄水量到时段末相应于死水位蓄水量之间的连线，该调度线也就是最优调度线，没有选择的余地。对不同时段初状态的计算如表1一2所示：
表中 (12) 栏的本时段发电量数值，已计入水头预想出力和装机容量的限制，再加上输用电限制100万千瓦后，则尚应排除 V11 至 V14 4个状态 (或不排除，则该4个状态时有无益弃水，一般不会被选为最优方案)；计入满足灌溉用水 750m^3/s 的约束后，则应排除 V111 至 V115 5个状态（表1—2 ( 8 )栏），因而本时段初的允许(可行)状态集合为从状态 V15 到 V110之间的6个状态。从这些初始状态到本时段末状态(均为 V011 )的调度线，即为本时段的最优调度线，相应的发电量即为最优发电量【表1一2(12)栏的98.2、87.0、 … 51.4万千瓦月】。
. 第2时段： 将 i = 2 代入目标函数和递推方程，状态转移规律得 把图1-9第2时段放大，如图1一10所示：
从理论上讲，该时段每一个初始状态同全部时段末的15个状态构成15个可能的调度方案，如图1 - 10 所画 V21 同 V11 ，V12、… 、V115，同样 V23、V24 … V215 均可分别同 V11、V12 …V115 构成15个调度方案，这样总共将有调度方案15x15= 225个。但实际上，由于第1时段的约束条件，已使第1时段初始状态即第2时段末状态从15个减少到6个，因而实际调度方案大大减少，在第2时段计算时可不必考虑其余9个时段末状态。再就是第2时段的各种约束条件也将使调度方案大大减少。
本时段的计算与第1时段不同，对某个初始状态 V2，及某个时段末状态 V1，根据状态转移方程计算出 Q2，从而可求出本时段发电量 N2(V2, Q2) = 8.3Q2H2，再根据 V1 查出第 1 时段计算所得最优发电量 N1(Vi)，对第2时段来说即为余留期最优发电量，从而可求得本时段发电量与余留期最优发电量之和，即得全时期发电量。对不同的时段末状态按上述方法分别求出全时期发电量，并从中选出全时期发电量最大的方案，该方案即为在该初始状态时的最优调度方案。按同样方法，对所有可能的初始状态，均可分别求出最优调度方案。计算如表1一3所示。 当初始状态为 V21 时，对时段末状态 V15由状状态转移规律得：
Q
21
,
15
=
V
21
+
q
2
−
V
15
=
1948.6
+
365
−
1382.4
=
931.2
m
3
/
s
Q~21,15~ = V~21~ + q~2~ - V~15~ = 1948.6 + 365- 1382.4= 931.2 m^3/s
Q 21,15 =V 21 +q 2 −V 15 =1948.6+365−1382.4=931.2m3/s 如第(8)栏所示，根据已知资料可求出本时段发电量为 80.5 万千瓦月，再根据 V15 ，在第1时段计算结果【表1—2第( 12)栏】查得为 98.2万千瓦月，即为余留最优发电量，相加后得全时期发电量为178.7万千瓦月；同样可求得时段末状态为 V16，V17，…，V110 时的全时期发电量分别为177.2、176.2、 …167.4 万千瓦月；比较各全时期发电量值，最大值为178.7万千瓦月，相应的调度线为 V21 —V15 —V0 (即735—723——694米 ) 这就是初始状态为 V21 时的最优调度线。按同样方法可求得初始状态为 V22、V23 …等的最优调度线及相应的最大发电量。各初始状态的全部计算和方案均需满足本时段的各种约束条件。例如 V21 时最优方案的发电流量 931.2 大于该月灌溉要求 900m3/s 等。 . 第3~7时段的选优：用第2时段的计算和选优方法与步骤，继缕进行第3至第7时段的计算和选优。 . 第8时段的选优 由于初始状态是一个固定值 V81，因而只要对 V81 进行计算和选优即可，方法与第2时段相同。所得结果即为全供水期的最优成果，如表1-4所示，供水期最优总发电量343. 5万千 瓦月(25.08亿度),它比采用等出力调节方案的发电量(23.58亿度)多6.4%。 当计入电力系统对本水电站最小出力要求时，则在逐时段递推计算中加上该约束，例如若4月最小出力为30万千瓦，则需将未考虑最小出力要求时的最优出力17.2万千瓦 (见表1-4 ) 改为30万千瓦， 因此其后各时段、即第4至8时段的最优出力亦将随之变化。
4.4 总结
以上优化问题既可用于设计供水期保证电量的优化，也可用于具有长期径流预报的水电站水库优化调度。通过上述优化计算所得结果和结合物理意义的分析，可从中总结出年调节水库供水期电量最优分配的一般规律是：在充分利用供水期天然水量和发电调节库容蓄水量的情况下，水头愈高，发电量愈大。为此，在供水前期应尽量少发电少供水，使得有较长时间维持较高的水库水位和发电水头(最高为正常蓄水位，即按天然流量发电)，供水后期以最短时间按最大出力工作，尽量减少低水头工作时间，并使供水期末水库水位降到死水位，以充分利用水量。这就是水量利用最充分、发电水头最高、发电量最大的方案。
应用上述优化调度一般规律，可简便地求得优化成果。 1、定起始终止时刻的库水位：根据预报时期确定开始和终止时刻的水库水位。若为年调节水库的供水期，供水开始时为正常蓄水位，供水期末为死水位，或到供水后期某时刻的某个控制电位(例如某个灌溉用水控制水位)。 2、定允许最大、最小发电量等约束：确定预报时期内各时段的各种约束条件，求出各时段的水电站允许最大发电量和允许最小发电量;有关综合利用要求可作为约束条件处理。 3、从终点按允许最大发电量逆序调节计算：根据预报时期内各时段的预报流量，扣除水库水量损失和上游用水后，从预报时期终止时刻的水库水位开始，按允许最大发电量工作，逆时序逐时段进行调节计算，求出各时段初的水库水位。 4、从起点按允许最小发电量顺序调节计算：再从预报时期开始时刻的水库水位起，按各时段允许最小发电量工作，顺时序逐时段进行调节计算，求各时段末的水库水位，直至与逆时序计算求得的水库水位变化线相交。 5、得最优调度线：顾时序求得的前段水库水位变化线与相交后的逆时序算出的后段水库水位变化线所组成的全部预报时期的水库水位变化线，即为该预报期内的最优调度线。同时亦得出了各时段的最优发电量和全预报期的总发电量最优值。
文章来源
发表评论