第三节动态规划ppt课件.ppt
《第三节动态规划ppt课件.ppt》由会员分享,可在线阅读,更多相关《第三节动态规划ppt课件.ppt(38页珍藏版)》请在三一办公上搜索。
1、4.3 动态规划模型,一、多阶段决策过程及实例二、动态规划的基本概念三、动态规划模型举例,一、多阶段决策过程及实例动态规划是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家Bellman(贝尔曼)等人,根据一类多阶段决策问题的特性,提出了解决这类问题的“最优化原理”,并研究了许多实际问题,从而创建了最优化问题的一种新方法动态规划。多阶段决策问题是指这样一类活动的过程,由于他的特殊性,可将其分为若干个互相联系的阶段,在它的每一个阶段都需作出决策,并且一个阶段的决策决定后,常常影响下一个阶段的决策,从而使整个过程达到最好的活动效果。,这样一个前后关联具有链状结构的多阶段过程就称为多
2、阶段决策过程,也称为序贯决策过程。例1(最短路线问题)如图,给出一个线路网络,A为始点,G为终点,两点之间的连线可以表示道路、管道等,连线上的数字表示两点间的距离(或费用),试选择一条由A到G的线路,使总距离(或费用)为最小。,例2 (生产存贮问题)某工厂根据市场调研情况,需制定今后四个月的生产计划,据估计,在这四个月内,市场对该产品的需求量如下表所示:假定市场每批产品的固定成本费用为3千元,每单位产品成本费用为1千元,库存费用每月为0.5千元.并且规定1月月初和4月月底均无产品库存.试问该厂如何安排各个月的生产与库存,使总费用最小.,二、动态规划的基本概念和基本方程动态规划的基本概念1、阶段
3、(stage)k: 把所给问题的过程,恰当地分成若干个相互联系的阶段(步骤).描述阶段的变量称为阶段变量,常用k表示.k = 1、2、3、2、状态(state)sk:状态表示每个阶段开始所处的状况,即是每一阶段的出发位置(阶段的起点).通常一个阶段有多个状态.描述状态的变量称为状态变量.第k阶段的状态变量记为sk,该阶段所有可能的状态的全体称为状态集合,记为Sk.如例1:S1=A,S2=B1,B2,S3=C1,C2,C3,C4,,3、决策(decision) uk(sk) :从一个阶段某状态演变到下一个阶段某状态的选择或决定称为决策。描述决策的变量称为决策变量,用uk(sk)表示第k阶段当状态
4、为sk时的决策变量,它是状态sk的函数。决策变量的取值范围称为决策集合,允许决策集用Dk(sk)表示。如例1:D1(s1)=u1(A)=B1,B2, s1=AD2(s2)=u2(B1)=C1,C2,C3, s2=B1D3(s3)=u3(B2)=C2,C3,C4,,4、状态转移方程:状态转移方程描述由一个状态到另一个状态的演变过程.因为某一阶段的状态变量及决策变量取定后,下一阶段的状态就随之而定.用 sk+1=T(sk,uk) 表示k阶段与k+1阶段的变化规律.5、策略由过程的第k阶段开始到终点为止的过程,称为问题的后部子过程,由每阶段的决策组成的决策函数序列uk(sk),uk+1(sk+1),
5、un(sn)称为子过程策略,简称子策略,记为Pk(sk),即:Pk(sk)= uk(sk),uk+1(sk+1),un(sn).当k=1时,则此决策函数序列称为全过程的一个策略,简称为策略,记为P(s1).,或者说全过程中各个阶段的决策uk组成的有序总体就称为策略.允许策略集合可供选择的策略范围,用P表示.最优策略从允许策略集合中找出的使问题达到最有效果的策略称为最优策略.6、指标函数和最优指标函数值阶段效益(指标)是衡量该阶段决策效果的数量指标,它是阶段状态和阶段决策的函数.用dk(sk,uk)表示在第k阶段由状态sk和执行决策uk(sk)所得的效益.,指标函数(目标函数)是用来衡量所实现过
6、程优劣的一种数量指标,它表示系统执行某一策略所产生的效益,它是定义在过程(可以是全过程,也可以是后部子过程)上的数量函数.用fk,n表示:当初始状态确定后,过程的策略就确定了,因而指标函数也就确定了,故指标函数是初始状态和策略的函数,即:最优指标函数值指标函数的最优值称为最优指标函数值,记为fk(sk).,动态规划的基本思想和基本方程最短路线的特性如果从起点到终点的最短路线在第k阶段通过点Pk,则最短路线上由点Pk出发到达终点的这一段子路线,对于从Pk到达终点的所有可能选择的不同路线来说,必定是最短的。动态规划的基本思想由后向前逐步推移计算.即从最后一段开始,由后向前逐步递推,求出各点到终点的
7、最短路线.下面我们利用动态规划基本思想来解决如下问题:,例3 、求由A到D的最短路线.,再按计算顺序反推之,可得最优决策函数序列uk,即:u1(A)=B1,u2(B1)=C1,u3(C1)=D.从最短路线问题的例子的计算过程,可以看到,用动态规划方法解决问题的关键是正确写出k阶段与k+1阶段之间的递推关系式(基本方程):由此得动态规划的一般模型为:,按照上述方法我们来求例1图中的最短路线解:,三、动态规划模型举例动态规划建模的一般步骤(1)划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一步,在确定多阶段特性后,按时间或空间先后顺序,将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 三节 动态 规划 ppt 课件
链接地址:https://www.31ppt.com/p-1626925.html