《刘诚(5)动态规划(xg》由会员分享，可在线阅读，更多相关《刘诚(5)动态规划(xg（101页珍藏版）》请在金锄头文库上搜索。
1、1,第九章 动态规划,1 多阶段决策过程最优化 2 动态规划基本概念 3 动态规划基本原理 4 动态规划的应用,2,1.多阶段决策过程的最优化,一、多阶段决策问题 动态规划是把多阶段决策问题作为研究对象。 多阶段决策问题：根据问题本身的特点，可以将其求解的全过程划分为若干个相互联系的阶段(即将问题划分为许多个相互联系的子问题)，在它的每一阶段都需要作出决策，并且在一个阶段的决策确定以后再转移到下一个阶段。,3,1.多阶段决策过程的最优化,多阶段决策过程(Multi-Stagedecision process)： 前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。各个阶段所确定的决策就
2、构成了一个决策序列，称为一个策略。一般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，就会有许多可供选择的策略。,4,1.多阶段决策过程的最优化,最优策略： 若对应于一个策略，可以由一个量化的指标来确定这个策略所对应的活动过程的效果，那么不同的策略就有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。把一个问题划分成若干个相互联系的阶段选取其最优策略，这类问题就是多阶段决策问题。,5,1.多阶段决策过程的最优化,多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各段决策间有机地联系着，本段决策的执行将影响到下一段的决策，以至于影响总体效果，所
3、以决策者在每段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而作出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。,6,1.多阶段决策过程的最优化,图1 运输网络图示,7,多阶段决策过程特点:,要点：阶段，状态，决策，状态转移方程，k-后部子过程,1.多阶段决策过程的最优化,8,1.多阶段决策过程的最优化,四、动态规划方法导引 例1：为了说明动态规划的基本思想方法和特点，下面以图1所示为例讨论的求最短路问题的方法。 第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从v1到v10的路程可以分为4个阶段
4、。第一段的走法有三种，第二三两段的走法各有两种，第四段的走法仅一种，因此共有322112条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是v1 v3 v7 v9 v10 ,最短距离是18,9,1.多阶段决策过程的最优化,显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算 第二种方法即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是v1 v3 v5 v8 v10 ，全程长度是20；显然，这种方法的结果常是错误的,
5、10,1.多阶段决策过程的最优化,第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为4个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。 为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。,11,1.多阶段决策过程的最优化,结论： 全枚举法虽可找出最优方案，但不是个好算法； 局部最优法则完全是个错误方法； 动态规划方法属较科学有效的算法：它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求
6、解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。,12,2.动态规划的基本概念,使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述和讨论方便，这里需要对动态规划的下述一些基本术语进一步加以说明和定义：,13,2.动态规划的基本概念,(一) 阶段和阶段变量 为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题
7、，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目。,14,2.动态规划的基本概念,（二）状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后，每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态
8、记为sk+1。但为了清楚起见，通常定义阶段的状态即指其初始状态。,15,2.动态规划的基本概念,2可能状态集 一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，skSk，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定,16,（三）决策、决策变量和允许决策集合 所谓决策，就是确定系统过程发展的方案。决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。 用以描述决策变化的量称之决策变量和状态变量一样，决策变量可以用一个数，一组数或一
9、向量来描述，也可以是状态变量的函数，记以uk= uk(sk)，表示于阶段k状态sk时的决策变量。 决策变量的取值往往也有一定的允许范围，称之允许决策集合。决策变量uk(sk)的允许决策集用Uk(sk)表示, uk(sk) Uk(sk)允许决策集合实际是决策的约束条件。,2.动态规划的基本概念,17,（四）、策略和允许策略集合 策略(Policy)也叫决策序列策略有全过程策略和k部子策略之分，全过程策略是指具有n个阶段的全部过程，由依次进行的n个阶段决策构成的决策序列，简称策略，表示为p1,nu1,u2,un。从k阶段到第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略,表示为pk,nuk
10、,uk+1,un ，显然当k=1时的k部子策略就是全过程策略。 在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集合，称之允许策略集合，记作P1,n ，从允许策略集中，找出具有最优效果的策略称为最优策略。,2.动态规划的基本概念,18,（五）状态转移方程 系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1 ，或者说，系统由k阶段的状态sk转移到了阶段k+1的状态sk+1 ，多阶段决策过程的发展就是用阶段状态的相继演变来描述的。 对于具有无后效性的多阶
11、段决策过程,系统由阶段k到阶段k+1的状态转移完全由阶段k的状态sk和决策uk(sk)所确定，与系统过去的状态s1,s2, ,sk-1及其决策u1(s1), u2(s2)uk-1(sk-1)无关。系统状态的这种转移，用数学公式描述即有：,2.动态规划的基本概念,(1),19,通常称式(1)为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。 (六) 指标函数 用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产
12、量、耗量、距离、时间、效用，等等。,2.动态规划的基本概念,20,(1)阶段指标函数（也称阶段效应）。用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数，简记为gk 。 (2)过程指标函数（也称目标函数）。用Rk(sk,uk)表示第k子过程的指标函数。如图5-1的Rk(sk,uk)表示处于第k段sk状态且所作决策为uk时，从sk点到终点v10的距离。由此可见，Rk(sk,uk)不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为:,2.动态规划的基本概念,21,不过实际应用中往往表示为Rk
13、(sk,uk)或Rk(sk)。还跟第k子过程上各段指标函数有关，过程指标函数Rk(sk)通常是描述所实现的全过程或k后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数gk(sk,uk)累积形成的，适于用动态规划求解的问题的过程指标函数（即目标函数），必须具有关于阶段指标的可分离形式对于部子过程的指标函数可以表示为： 式中，表示某种运算，可以是加、减、乘、除、开方等。,2.动态规划的基本概念,(2),22,多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即: (3) 有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如： (4) 总之，具体问题的目标函数表
14、达形式需要视具体问题而定。,2.动态规划的基本概念,23,(七) 最优解 用fk(sk)表示第k子过程指标函数 在状态sk下的最优值,即 称fk(sk)为第k子过程上的最优指标函数；与它 相应的子策略称为sk状态下的最优子策略，记 为pk*(sk) ；而构成该子策赂的各段决策称为该 过程上的最优决策，记为 有 简记为,2.动态规划的基本概念,24,特别当k=1且s1取值唯一时，f1(s1)就是问题的最优值，而p1*就是最优策略。如例只有唯一始点v1即s1取值唯一,故f1(s1)=18就是例的最优值，而 就是例的最优策略。 但若取值不唯一,则问题的最优值记为f0有 最优策略即为s1=s1*状态下
15、的最优策略： 我们把最优策略和最优值统称为问题的最 优解。,2.动态规划的基本概念,25,按上述定义，所谓最优决策 是指它们在全过程上整体最优(即所构成的全过程策略为最优)，而不一定在各阶段上单独最优。 (八) 多阶段决策问题的数学模型 综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式:,2.动态规划的基本概念,（5）,26,式中“OPT”表示最优化，视具体问题取max或min。 上述数学模型说明了对于给定的多阶段决策过程，求取一个(或多个)最优策略或最优决策序列 ，使之既满足式(5)给出的全部约束条件，又使式(5)所示的目标函数取得
16、极值，并且同时指出执行该最优策略时，过程状态演变序列即最优路线,2.动态规划的基本概念,27,最优化原理 （贝尔曼最优化原理） 作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：,动态规划的基本原理,则对上述策略中所隐含的任一状态而言， 第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为,28,3.动态规划方法的基本步骤,1应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。 2正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具
