该方法的核心是由美国数学家R.E.贝尔曼(Richard Ernest Bellman,1920~1984)于20世纪50年代提出的贝尔曼最优性原理,即多级决策过程的最优策略具有这种性质,不论初始状态和初始决策如何,其余的决策对于由初始决策所形成的状态必定也是一个最优策略。这个原理可以归结为一个基本的递推公式,当求解多级决策问题时,要从末端开始,到始端为止,逆向递推。
贝尔曼动态规划解决问题的基本思路:把整体比较复杂的大问题划分为一系列较易于解决的小问题,通过逐个求解,最终取得整体最优解。这种“分而治之,逐步调整”的方法,在解决一些复杂问题中已经显示出优越性。
动态规划程序设计是解最优化问题的一种途径和方法。问题不同,求解问题的模型也不同,基本步骤可分为以下5步:①确定问题的决策对象;②对决策过程划分阶段;③对各阶段确定状态变量;④根据状态变量确定费用函数和目标函数;⑤建立各阶段状态变量的转移过程,确定状态转移方程。
动态规划的局限性表现为以下3个方面:①动态规划还没有一个统一的标准模型可供使用。②当构造动态规划模型时,状态变量必须满足“无后效性”条件。③用动态规划方法进行数值求解时遇到的主要问题是所谓“维数爆炸”。
经过多年的发展,动态规划在经济管理、生产调度、工程技术等领域得到了广泛的应用,并取得了很好效果。在解决如最短路线设计、库存管理、资源分配、设备更新、排序、装载等问题方面,采用动态规划方法比用其他方法求解更为便利。