动态规划的基本原理和递推方程
发布网友
发布时间：2022-03-24 06:02
共1个回答
热心网友
时间：2022-03-24 07:32
贝尔曼等所提出的动态规划最优化原理是：“一个过程的最优策略具有这样的性质，即无论初始状态和初始决策如何，从这一决策所导致的新状态开始，以后的一系列决策必须是最优的”。
如前所述，动态规划逆序决策过程中，总是从整个过程的终端开始计算，向始端逐阶段择优，其中每一个阶段都要考虑未来各阶段情况加以比较而选取决策，唯独终端的阶段决策时，只考虑终端这一阶段最有利即可。
同时，根据最优化原理可知，一个n 阶段的决策过程，如果所选取的最优策略，经过第i阶段si状态时，则从si至终点的最优策略，必然是整个最优策略的一部分。这样，就使多阶段决策过程寻找最优策略问题，具有逆推的性质。即求第i阶段至末阶段的最优策略时，可用当前i阶段的一个决策加上剩余阶段相应的最优策略，作为从i阶段至终点的一个比较策略，从中选取最优策略。据此，可建立动态规划的递推方程。
设（si）表示任一状态si开始至终点使用所有决策序列dk所得到的最小费用，则有
华北煤田排水供水环保结合优化管理
若把决策序列分为两部分，即在di上最小化和di+1，di+2，…，dn最小化，则式（3.3.1）可写为
华北煤田排水供水环保结合优化管理
式（3-27）中，第一项仅依赖di而与dk无关（k＞i），因此dk上的最小化对此项没有影响，而第二项si+1与di有关，随系统状态转移方程而定，即
华北煤田排水供水环保结合优化管理
故式（3-27）可写为
华北煤田排水供水环保结合优化管理
因为
华北煤田排水供水环保结合优化管理
将式（3-29）代入式（3-28）可得
华北煤田排水供水环保结合优化管理
式（si）和（si+1）分别代表第i阶段状态为si及第i+1阶段状态为si+1时的最优目标函数值。若阶段变量i=n，n-1，…，1，经历过程所有阶段，式（3-30）就成为一个递推方程，当i=1时，最优目标函数值（s1）也就是全过程最小总费用R*，即
华北煤田排水供水环保结合优化管理
上述递推方程的阶段编码次序和递推次序与实际过程状态转换方向相反，故称为逆序递推；如果阶段编码次序和递推次序与实际过程状态转换方向相一致时，故称为顺序递推。那么，逆序递推的式（3-30）变顺序递推可写为
华北煤田排水供水环保结合优化管理
全过程最优目标函数值为
华北煤田排水供水环保结合优化管理
递推方程计算时，可顺序递推，也可逆序递推。通常，当初始状态已知时，逆序递推较方便，当最终状态已知时，顺序递推较方便。但无论是顺序递推或逆序递推，都要采用前述逆序决策过程——选定系统前进方向后，逆此方向自终点向始点逐阶段寻优，达到整体最优。所以，逆序递推与逆序决策过程是两个不同的概念。
