动态规划

来自中文百科专业版
跳转至: 导航搜索

  动态规划汉语拼音:Dong tai gui hua;英语:dynamic programming),解决多阶段决策(序贯决策)过程最优化的一种数学方法。运筹学的一个分支。这一独特的方法大约产生于20世纪50年代。1951年美国数学家R.贝尔曼等人根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列相互联系的单阶段优化问题,然后逐个加以解决。与此同时,他提出解决此类问题的“最优性原理”,从而创立了解决优化问题的新方法——动态规划方法。1957年他的著作《动态规划》出版,标志着这一学科的创立。

理论基础

  动态规划的理论基础是最优性原理,它认为整个过程的最优策略有这样的特点:即无论过去的状态和决策如何,对于前面的决策所形成的状态而言,余下的诸决策必定构成最优策略。这就是说,任何一个完整的最优策略的子策略总是最优的。根据这个重要的原理,用动态规划方法求解一个优化问题首先应把问题的过程分成几个相互联系的阶段,这些阶段的状态可以用阶段的某种特征来描述,而决策过程可以通过状态的演变来说明。于是就可以根据问题的实际意义,找出由一个状态演变到另一状态的状态转移方程,再根据所求问题的有关效益指标,建立起能够联系局部与全局最优性的动态规划基本方程。它是一个递推公式,把单一的优化问题嵌入到具有不变结构和特征的一族优化问题中,从而把一个整体的大问题化为一族同类型的子问题,通过迭代逐层求解,最后便可求得全问题的最优解,同时也求出各个阶段子问题的最优解。

规划方法

  动态规划方法在工程技术企业管理、工农业生产以及军事部门都有广泛的应用。比如在企业管理方面,动态规划方法可以用来解决最优路径问题、资源分配问题、生产调度、库存、装载、排序、设备更新、最优工艺等问题。所以是一种重要的决策方法。

  解决最优化问题经典的理论是微分学变分法,这种方法对函数的解析要求较高,而且不能处理离散问题。而动态规划方法对函数的要求较低,因而它的适用面很宽,几乎能求任何集的全部极值。但是动态规划只是一种考察问题的途径和方法,不像用单纯形法解线性规划那样是一种固定算法,所以对于具体问题还要进行具体分析和处理,用创造性的技巧求解。比如它不仅可以处理与时间有关的决策问题,也可以处理与时间无关的静态问题。此外,状态变量的“维数障碍”限制了动态规划的应用范围。一般地说,三维以上的问题用动态规划求解是不可取的。

参见条目