当系统模型具备马尔科夫性质,同时目标函数可分且嵌套单调时,基于贝尔曼提出的最优化原理,可将多阶段全局最优决策问题分解为一系列在各个时间段上的局部优化问题进行求解,这种方法叫作动态规划法。
动态规划模型是求解最优化问题的一种途径和方法,而不是一种特殊算法,因此没有标准的数学表达式和明确清晰的解题方法。动态规划模型的设计往往是针对一种最优化问题,由于各种问题的性质不同,其最优解的条件也互不相同,因此动态规划模型根据不同的问题,有不同的解题方法,而不存在一种万能的解法。所以必须根据具体问题做具体分析处理。
值得注意的是,虽然动态规划模型主要用于求解以时间划分的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进了时间因素,并把它视为多阶段决策过程,就可以用动态规划模型方便地进行求解。
以下介绍两种常用的动态规划模型思路:
①逆推解法:利用已知条件从最后一个阶段开始从后向前推算,求得各阶段的最优决策和最优目标函数,由此算出第一阶段的目标函数并得到最优目标函数值,然后再从第一阶段开始,利用状态转移方程确定最优轨线和最优策略。
②顺推解法:和逆推解法的递推顺序正好相反,在顺推解法中是从第一阶段开始,利用状态转移方程从前向后推算。
相比其他解法,特别是在有扰动或在随机情况下,动态规划模型能有效地提供一个在当前信息集下的最优反馈控制策略。在过去的若干年里,动态规划模型取得了不少进展。动态规划模型在21世纪前后的一个重大突破是其在海量数据分析中的应用,特别是在人类基因组计划完成以后,它成为生物信息学的一个基本模型和工具。然而,在克服被贝尔曼称为“维数灾”的这一动态规划致命弱点的方面,至今尚未取得突破。所以,寻求克服维数灾的有效算法对动态规划模型在高维问题中的应用具有紧迫性。另外,求解不可分优化问题的最优策略时,动态规划模型并不满足最优化原理,或不具备时间一致性。因此怎样找出一组可分优化问题来逼近一个给定的不可分优化问题,也对动态规划模型的发展极其重要。