55动态规划.ppt

2017-2-22 1第五章第五章动态规划动态规划?§ 动态规划的基本概念和方法?§ 动态规划的基本原理﹑模型和解法?§ 前向动态规划法?§ 动态规划的应用 2017-2-22 2 多阶段决策及过程最优化多阶段决策及过程最优化多阶段决策是指这样一类特殊的活动过程, 它们可以按时间顺序分解成若干相互联系的阶段, 每个阶段都要作出决策, 全部过程的决策是一个决策序列, 所以多阶段决策问题又称为序贯决策问题。多阶段决策的目标是要达到整个活动过程的总体效果最优, 所以多阶段决策又叫做过程最优化。也正是因为如此, 多阶段决策并非各阶段决策的简单总和, 由于各阶段决策之间的有机联系, 某一段决策的执行必将影响到下一段的决策,以至于影响到总体效果, 所以决策者在每一段决策中不仅应考虑本段最优, 还应考虑对最终目标的影响, 从而做出对全局来说最优的决策。动态规划就是符合这种要求的一种决策方法。所以, 所谓动态规划, 就是解决多阶段决策和过程最优化问题的一种数学规划方法。显然, 由于它所解决问题的多阶段性, 因此它必然与时间有着密切的关系, 随着时间的推移或过程的发展而决定各阶段的决策, 从而, 产生了一个决策序列, 这就是动态的意思。然而它也可处理与时间无关的静态问题, 只要在问题中人为地引入“时间”因素, 将问题看成一个多阶段的决策过程即可。§ § 动态规划的基本概念和方法动态规划的基本概念和方法 2017-2-22 3 动态规划是现代管理中一种重要的决策方法,它可以广泛地用于解决最短路径问题、资源分配问题、生最短路径问题、资源分配问题、生产计划与库存问题、投资问题、装载问题、排序问题产计划与库存问题、投资问题、装载问题、排序问题及生产过程的最优控制及生产过程的最优控制等。由于它具有独特的解题思路因此在处理某些优化问题时常比线性规划等方法更为有效。动态规划模型一般根据决策过程的时间参数是离散的还是连续的过程的演变是确定型的还是随机型的可以划分为离散确定型、离散随机型、连续确定型和连续随机型四种类型, 其中离散确定型离散确定型是最基本的。 2017-2-22 4 设A地的某一企业要把一批货物由 A地运到 E 城销售, 其间要经过八个城市,各城市间的交通路线及距离如图 所示, 问应选择什么路线才能使总的距离最短? 路线图(共18条路线,3×3×2×1=18) 2017-2-22 5 这是一个最短路径问题的动态规划,也叫车马驿站问题。由图 不难看出, 本例是一个四阶段的决策问题, 因此, 无疑可以用动态规划方法求解。 动态规划的基本概念动态规划的基本概念一、阶段一、阶段(stage) (stage) 将所给问题的过程,按时间或空间特征分解成若干相互联系的段落以便按次序求解就形成了阶段,阶段变量常用字母阶段变量常用字母 k k来表示来表示。如例 若有四个阶段, k就等于 1,2,3,4 。第一阶段共有 3 条路线即(A,B1), (A,B2) 和(A,B3), 第二阶段有 9条路线,第 3 阶段有 6条路线,第4 阶段有 2 条路线。 2017-2-22 6 二、状态二、状态(state) (state) 各阶段开始时的客观条件或出发点称作各阶段开始时的客观条件或出发点称作状态状态,描述各阶段状态的变最称作状态变量状态变量, , 用用s s表示表示。状态变量的取值集合称为状态集合, 用S 表示。在例 中,第一阶段的状态为 A,第二阶段的状态为城市 B 1,B 2和B 3。所以状态变量 s 1 的集合 S 1 ={A}, s 2 的集合是 S 2 ={B 1,B 2,B 3 }, 依次有 S 3 ={C 1,C 2,C 3 }, S 4 ={D 1,D 2}。所以, 在这里, 状态变量的取值实际上是给定集合的一个元素。在动态规划中, 状态必须具有如下性质状态必须具有如下性质:即当某阶段状态给定以后,在这阶段以后过程的发展不受这段以前各状态的影响, 这称作无后效性无后效性。如果所选定的变量不具备无后效性, 就不能作为状态变量来构造动态规划模型。如在例 中,当某阶段的状态变量确定以后,假定 s3=C2, 因而在确定第 3 阶段的货运路线时,就只与 C2 这个城市有关,而与货物由哪个城市到达此地无关,所以满足状态的无后效性。 2017-2-22 7 三、决策和策略三、决策和策略(Decision and Policy) (Decision and Policy) 当各阶段的状态确定以后,就可以做出不同的决定或选择, 从而确定下一阶段的状态,这种决定就