第六章动态规划.ppt

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