动态规划简介课件.ppt
《动态规划简介课件.ppt》由会员分享,可在线阅读,更多相关《动态规划简介课件.ppt(56页珍藏版)》请在三一办公上搜索。
1、动态规划,本章内容重点多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例,动态规划,动态规划是解决多阶段决策过程最优化的一种数学方法。1951年美国数学家贝尔曼等人根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决。贝尔曼的动态规划于1957年出版。动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的意思。然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入“时段”因素,就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。,动态规划,
2、所谓多阶段决策问题是指这样的决策问题:其过程可分为若干个相互联的阶段,每一阶段都对应着一组可供选择的决策,每一决策的选定即依赖于当前面临的状态,又影响以后总体的效果。当每一阶段的决策选定以后,就构成一个决策序列,称为一个策略,它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。,多阶段决策问题,工厂生产过程:由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排。设备更新问题:一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为
3、故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差,并且,使用的年限越长、处理价值也越低,自然,如果卖去旧的买新的,还需要付出更新费因此就需要综合权衡决定设备的使用年限,使总的经济效益最好。,多阶段决策问题,连续生产过程的控制问题:一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大。资源分配问题:资源分配问题属于静态问题。如某工业部门或公司,拟对其所属企业进行稀缺资源分配,为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分
4、配量,它与时间因素无关,不属动态决策,但是,我们可以人为地规定一个资源分配的阶段和顺序,从而使其变成一个多阶段决策问题。,动态规划求解的特点,通常多阶段决策过程的发展是通过状态的一系列变换来实现的。 一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,还可能与系统过去经历的状态和决策有关。适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,即具有“无后效性”的多阶段决策过程。 无后效性(又称马尔柯夫性)是指系统从某个阶段往后的发展,仅由本阶段所处的状态及其往后的决策所决定,与系统以前经历的状态和决策(历史)无关。,A,动态规划问题实例,C4,C2,D3,D2,G,B2,B1,
5、C1,C3,D1,E3,E2,E1,F2,F1,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,例6-1 给定一个线路网络,要从A向F铺设一条输油管,各点间连线上的数字表示距离,问应选择什么路线,可使总距离最短?,A,动态规划,C4,C2,D3,D2,G,B2,B1,C1,C3,D1,E3,E2,E1,F2,F1,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,1.阶段与阶段变量 为了便于求解和表示决策及过程的发展顺序,而把所给问题恰当地划分为若干个相
6、互联系又有区别的子问题,称为多段决策问题的阶段。 描述阶段的变量称为阶段变量,常用k表示。阶段的划分,一般是根据时间和空间的自然特征来进行的,但要便于问题转化为多阶段决策。,动态规划的基本概念,动态规划的基本概念,2.状态、状态变量与可能状态集 描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量,称为状态。反映状态变化的量叫做状态变量。状态变量包含在给定的阶段上确定全部允许决策所需要的信息。 每个阶段的状态可分为初始状态和终止状态,或称输入状态和输出状态,阶段k的初始状态记作sk,终止状态记为sk+1。通常定义阶段的状态即指其初始状态。 一般状态变量的取值有一定的范围或允许集合,
7、称为可能状态集,或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示,skSk,。,A,动态规划问题实例,C4,C2,D3,D2,G,B2,B1,C1,C3,D1,E3,E2,E1,F2,F1,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,第1阶段,第2阶段,第3阶段,第4阶段,第5阶段,状态1,状态2,状态3,状态4,状态5,状态6,第6阶段,状态7,动态规划的基本概念,3.决策 当一阶段的状态确定后,可以作出不同的选择从而演变到下一阶段的某个状态,这种选择手段称为决策
8、。在最优控制问题中也称为控制。 描述决策的变量,称为决策变量。决策变量的允许取值的范围称为允许决策集合。决策变量是状态变量的函数。用uk(sk)表示第K阶段处于状态sk时的决策变量; Dk(sk)表示sk的允许决策集合。,A,动态规划问题实例,C4,C2,D3,D2,G,B2,B1,C1,C3,D1,E3,E2,E1,F2,F1,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,第1阶段,第2阶段,第3阶段,第4阶段,第5阶段,状态1,状态2,状态3,状态4,状态5,状态6,第6阶段,状态7,u2(B2)=C2D2(B2)=
9、C2,C3,C4,动态规划的基本概念,4.策略 一个按顺序排列的决策组成的集合。由过程的第K阶段开始到终止阶段为止的过程称为问题的后部子过程。由每段的决策按顺序排列组成的决策函数序列uk(sk),un(sn)称为K子过程策略,简称子策略,记为pk,n(sk)。 当K=1时,此决策函数序列称为全过程的一个策略,简称策略,记为p1,n(s1),即: p1,n(s1)= u1(s1), u2(s2),un(sn),A,动态规划问题实例,C4,C2,D3,D2,G,B2,B1,C1,C3,D1,E3,E2,E1,F2,F1,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2
10、,3,3,3,5,5,2,6,6,4,3,状态1,状态2,状态3,状态4,状态5,状态6,状态7,p3,6(C2)=u3(C2), u4(D2), u5(E3), u6(F1)p1,6(A)=u1(A), u2(B1), u3(C2), u4(D2), u5(E3), u6(F1),动态规划的基本概念,5.状态转移方程 确定过程由一个状态到另一个状态的演变过程。若给定第K阶段的状态变量sk的值,如果该阶段的决策变量uk一经确定,第K+1阶段的状态变量sk+1的值也就完全确定。即sk+1的值随sk和uk的值变化而变化。这种确定的对应关系记为: sk+1=Tk(sk , uk(sk),工厂1,工厂
11、2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态s2,状态变量sk :可用于第k, k+1,n个工厂的投资额。决策变量xk :第 k 阶段对第 k 个工厂的投资额。状态转移方程: sk+1 = sk - xk,s1=600,状态s3,状态s4,状态s5,s2=s1-x1,s3=s2-x2,s4=s3-x3,动态规划的基本概念,6.指标函数和最优值函数 用来衡量策略或子策略或决策的效果的某种数量指标,就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题,指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用等等。 1)阶段指标函数(阶段效
12、应) 用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标,则它就是第k段指标函数,简记为gk。,动态规划的基本概念,(2)过程指标函数(目标函数) 用Vk(sk,uk)表示第k子过程的指标函数指标函数,不仅跟当前状态sk有关,还跟该子过程策略pk(sk)有关,因此它是sk和pk(sk)的函数,严格说来,应表示为: Vk(sk, pk(sk) ,实际应用中上式可表示为: Vk(sk, uk) 或Vk(sk) 。 过程指标函数Vk(sk,uk) 通常是描述所实现的全过程或 k 后部子过程效果优劣的数量指标,它是由各阶段的阶段指标函数 gk(sk,uk) 累积形成的。,动态规
13、划的基本概念,适于用动态规划求解的问题的过程指标函数(即目标函数),必须具有关于阶段指标的可分离形式对于k部子过程的指标函数可以表示为: Vk,n = Vk,n (sk , uk , sk+1 , uk+1 , ,sn ,un) = gk(sk,uk) gk+1(sk+1,uk+1) gn(sn,un) 多阶段决策问题中,常见的目标函数形式之一是取各阶段效应之和的形式,即:,有些问题,如系统可靠性问题,其目标函数是取各阶段效应的连乘积形式,如:,动态规划的基本概念,指标函数的最优值称为最优值函数,记为fk(sk)。它表示从第K阶段的状态开始到第n阶段的终止状态的过程,采取最优策略所得到的指标函
14、数值。,相应的子策略称为sk状态下的最优子策略,记为pk*(sk) ;而构成该子策赂的各段决策称为该过程上的最优决策,记为: uk*(sk), uk+1*(sk+1), un*(sn)。 特别当k=1且s1取值唯一时,f1(s1)就是问题的最优值,而p1*就是最优策略。但若取值不唯一,则问题的最优值记为f0有:,动态规划的基本概念,7. 多阶段决策问题的数学模型 综上所述,适于应用动态规划方法求解的一类多阶段决策问题,亦即具有无后效性的多阶段决策问题的数学模型呈以下形式:,A,最短路径问题,C4,C2,D3,D2,G,B2,B1,C1,C3,D1,E3,E2,E1,F2,F1,5,3,1,3,
15、6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,例6-2:用动态规划求解最短路径。,将问题分成五个阶段,第k阶段到达的具体地点用状态变量sk表示,例如:s2=B2表示第二阶段到达位置B2。这里状态变量取字符值而不是数值。将决策定义为到达下一站所选择的路径,例如目前的状态是s2=B2,这时决策允许集合包含三个决策,它们是D2(s2)=D2(B2)=B2C2,B2 C3,B2 C4。最优指标函数 fk(xk) 表示从目前状态到E的最短路径。终端条件为:f7 (s7) = f7(G) = 0其含义是从G到G的最短路径为0。递推方程为:,最短路径
16、问题,贝尔曼最优化原理,作为一个全过程的最优策略具有这样的性质:对于最优策略过程中的任意状态而言,无论其过去的状态和决策如何,余下的诸决策必构成一个最优子策略。该原理的具体解释是,若某一全过程最优策略为:p1*(s1) = u1*(s1), u2*(s2), un*(sn)则对上述策略中所隐含的任一状态而言,第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1* 中,即为:pk*(sk) =uk*(sk), uk+1*(sk+1), un*(sn),贝尔曼最优化原理,基于贝尔曼最优化原理,提出了一种逆序递推法;该法的关键在于给出一种递推关系。一般把这种递推关系称为动态规划的函数基
17、本方程。对于求最小的加法的计算公式为:,贝尔曼最优化原理,(1)当过程指标函数为“和”的形式时,相应的函数基本方程为:,(2)当过程指标函数为“和”的形式时,相应的函数基本方程为:,动态规划方法的基本步骤,用函数基本方程逆推求解是常用的方法:首先要有效地建立动态规划模型,然后再递推求解,最后得出结论。正确地建立一个动态规划模型,是解决问题的关键。正确的动态规划模型,应该满足下列条件:1.应将实际问题恰当地分割成n个子问题(n个阶段)通常是根据时间或空间而划分的,或者在经由静态的数学规划模型转换为动态规划模型时,常取静态规划中变量的个数n。,动态规划方法的基本步骤,2.正确地定义状态变量sk,使
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 简介 课件

链接地址:https://www.31ppt.com/p-1564567.html