动态规划.ppt

动态规划1动态规划的方法,在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用,并且获得了显著的效果。在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等,他是现代企业管理中的一种重要的决策方法。许多实际问题采用动态规划方法去处理,常比线性规划或非线性规划更加有效。特别对于离散性的问题,由于解析数学无法施展其术,而动态规划的方法就成为一种非常有效的工具。2应特别指出的是,动态规划是解决某一类问题的一种方法,是分析问题的一种途径,而不是一种特殊算法(如线性规划是一种算法)。因而,它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。因此,在学习动态规划时,除了对基本概念和方法正确地理解外,应以丰富的想象力去建立模型,用创造性的技巧去求解。正如贝尔曼本人所说:“由于动态规划的最优化原理仅仅是一种基本原理,正是它的某种不确定性为你提供了发挥你创造性思维的巨大空间!3本部分我们主要研究离散决策过程,介绍动态规划的基本概念、理论和方法,在通过一些典型的应用问题来说明它的应用。动态规划所研究的对象是多阶段决策问题。所谓多阶段决策问题是指一类活动过程,它可以分为若干个相互联系的阶段,在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益,而且决定下一阶段的初始状态。每个阶段的决策确定以后,就得到一个决策序列,称为策略。多阶段决策问题就是求一个策略,使各阶段的效益的总和达到最优。4第一节多阶段决策问题在生产经营活动中,某些问题决策过程可以划分为若干相互联系的阶段,每个阶段需要做出决策,从而使整个过程取得最优。当每个阶段的决策确定以后,全部过程的决策就是这些阶段决策所组成的一个决策序列,所以多阶段决策问题也称为序贯决策问题。动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的意思。然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入“时段”因素,就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。5动态规划求解的多阶段决策问题的特点通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,还可能与系统过去经历的状态和决策有关。因此,问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,即具有“无后效性”的多阶段决策过程。所谓无后效性,又称马尔柯夫性,是指系统从某个阶段往后的发展,仅由本阶段所处的状态及其往后的决策所决定,与系统以前经历的状态和决策(历史)无关。625112141061041311**********C1C3D1AB1B3B2D2EC2为了说明动态规划的基本思想方法和特点,以下图所示为例,讨论求最短路问题的方法。求从A到E的最短路径7第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果,再对它们一一进行比较,求出最优方案。这里从A到E的路程可以分为4个阶段。第一、二阶段的走法有三种,第三阶段的走法有两种,第四段的走法仅一种,因此共有3×3×2×1=18条可能的路线,分别算出各条路线的距离,最后进行比较,可知最优路线是A→B2→C1→D1→E,,当组成交通网络的节点很多时,用穷举法求最优路线的计算工作量将会十分庞大,“局部最优路径”法,是说某人从A出发,他并不顾及全线是否最短,只是选择当前最短途径,“逢近便走”,错误地以为局部最优会致整体最优,在这种想法指导下,所取决策必是A→B2→C1→D1→E,全程长度是25;显然,。动态规划方法寻求该最短路问题的基本思想是,如果A=S1→S2→…→Sk→…→Sn→E是A到E的最短路,则Sk到E的最短路一定是Sk→…→Sn→E。首先将问题划分为4个阶段,每次的选择总是综合后继过程的一并最优进行考虑,在各段所有可能状态的最优后继过程都已求得的情况下,全程的最优路线便也随之得到。为了找出所有可能状态的最优后继过程,动态规划方法总是从过程的最后阶段开始考虑,然后逆着实际过程发展的顺序,逐段向前递推计算直至始点。10