- -
当时在兰德公司〔〕从事研究工作的贝尔曼首先提出了动
态规划的概念。 年贝尔曼发表了数篇研究论文,并出版了他的第一部著
作动态规划。该著作成为了当时唯一的进一步研究和应用动态规划的理论源
泉。在贝尔曼及其助手们致力于开展和推广这一技术的同时,其他一些学者也
对动态规划的开展做出了重大的奉献,其中最值得一提的是爱尔思〔〕和
梅特顿〔〕。爱尔思先后于 年和 年出版了两部关于动态规
划的著作,并于 年同尼母霍思尔〔〕、威尔德〔〕一
道创立了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多
对动态规划后来开展有着重要意义的根底性观点,并且对明晰动态规划路径的
数学性质做出了巨大的奉献。
动态规划问世以来,在工程技术、经济管理等社会各个领域都有着广泛的
应用,并且获得了显著的效果。在经济管理方面,动态规划可以用来解决最优
路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更
新问题以及生产过程最优控制问题等,是经济管理中一种重要的决策技术。许
多规划问题用动态规划的方法来处理,常比线性规划或非线性规划更有效。特
别是对于离散的问题,由于解析数学无法发挥作用,动态规划便成为了一种非
常有用的工具。动态规划可以按照决策过程的演变是否确定分为确定性动态规
划和随机性动态规划;也可以按照决策变量的取值是否连续分为连续性动态规
划和离散性动态规划。虽然动态规划主要用于求解以时间划分阶段的动态过程
的优化问题,但是一些与时间无关的静态规划 如线性规划、非线性规划!,只
要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方
便地求解。
2.动态规划的根本思想一般来说,只要问题可以划分成规模更小的子问题,
并且原问题的最优解中包含了子问题的最优解,那么可以考虑用动态规划解决。
动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分
解为更小的、相似的子问题,并存储子问题的解而防止计算重复的子问题,以
解决最优化问题的算法策略。由此可知,动态规划法与分治法和贪心法类似,
它们都是将问题实例归纳为更小的、相似的子问题,并通过求解子问题产生一
个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择,但不
- word.zl-