欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    第二节最优化原理与动态规划优秀课件.ppt

    • 资源ID:53982598       资源大小:1.74MB        全文页数:32页
    • 资源格式: PPT        下载积分:18金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要18金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    第二节最优化原理与动态规划优秀课件.ppt

    第二节最优化原理与动态规第二节最优化原理与动态规划划第1页,本讲稿共32页一、动态规划方法导引一、动态规划方法导引 1.1.全全枚枚举举法法或或穷穷举举法法。共共有有18条条可可能能路路线线,进进行行比较,求得最优路线比较,求得最优路线Q A3 B1 C1T。QTA1A2A3B1B2B3C1C224374642442514633334第2页,本讲稿共32页2.“.“局局部部最最优优路路径径”法法:选选择择当当前前最最短短途途径径,“逢近便走逢近便走”。所所取取决决策策必必是是Q A1 B2 C2T,全全程程长长度度是是13。QTA1A2A3B1B2B3C1C224374642442514633334第3页,本讲稿共32页全枚举法全枚举法计算工作量将会十分庞大。计算工作量将会十分庞大。局部最优求出的解不一定是最优解。局部最优求出的解不一定是最优解。第4页,本讲稿共32页3.动态规划方法就是从终点逐段向始点方向寻找最短路线的方法。解题步骤如下:把问题划分为几个阶段。按阶段顺序首先考虑最后阶段如第四阶段的最优决策,也就是走哪条路线最短。按阶段顺序依次考虑第三、第二,第一阶段的最优决策,为此只需确定每一阶段上各初始点的最优决策即可。第5页,本讲稿共32页用动态规划方法逐段求解时,每个阶段上的求优方法基本相同,而且比较简单,每一阶段的计算都要利用上一阶段的计算结果,因而减少了很多计算量。阶段数愈多,这种效果愈明显。第6页,本讲稿共32页二、动态规划解题二、动态规划解题 标号法:标号法:最短路径:最短路径:Q A3 B1 C1TQTA1A2A3B1B2B3C1C224374642442514633334阶段阶段1阶段阶段2阶段阶段3阶段阶段40,T3,T4,T4,C17,C26,C111,B1,B28,B18,B111,A3 第7页,本讲稿共32页三、动态规划的基本概念。三、动态规划的基本概念。1.阶段阶段(stage)和阶段变量。和阶段变量。把所给问把所给问题恰当地划分为若干个相互联系又有区别的子问题,题恰当地划分为若干个相互联系又有区别的子问题,称之为多段决策问题的阶段。称之为多段决策问题的阶段。QTA1A2A3B1B2B3C1C224374642442514633334第8页,本讲稿共32页用以描述阶段的变量叫作用以描述阶段的变量叫作阶段变量阶段变量,一般以,一般以k表表示阶段量示阶段量阶段数阶段数k的编号法有两种:的编号法有两种:(1)(1)顺序编号;顺序编号;(2)(2)逆序编号法。逆序编号法。QTA1A2A3B1B2B3C1C224374642442514633334第9页,本讲稿共32页2.状态状态(state)、状态变量和可能状态集、状态变量和可能状态集(1)状态与状态变量。表示每个阶段开始所处状态与状态变量。表示每个阶段开始所处的自然状况或客观条件。的自然状况或客观条件。QTA1A2A3B1B2B3C1C224374642442514633334第10页,本讲稿共32页(2)动态规划维数动态规划维数。(3)可能状态集:用可能状态集:用S(sk)表示。表示。QTA1A2A3B1B2B3C1C224374642442514633334第11页,本讲稿共32页3.3.决策决策(decision)、决策变量和允许决策集合、决策变量和允许决策集合(1)决决策策。表表示示当当过过程程处处于于某某一一阶阶段段的的某某个个状状态态,可可以以作作出出不不同同的的决决定定(选选择择),从从而而确确定定下一阶段的状态。下一阶段的状态。QTA1A2A3B1B2B3C1C224374642442514633334第12页,本讲稿共32页(2)决策变量决策变量:xk=xk(sk)决决策策变变量量xk(sk)的的允允许许决决策策集集用用Dk(sk)表表示示,xk(sk)Dk(sk)允允许许决决策策集集合合实实际际是是决决策策的的约约束束条条件。件。QTA1A2A3B1B2B3C1C224374642442514633334第13页,本讲稿共32页4.策略和子策略和子策略策略(Policy)(1 1)全过程策略指具有)全过程策略指具有n个阶段全部过程,简称个阶段全部过程,简称策略。表示为策略。表示为 x1(s1),x2(s1),xn(sn)。k后后部子过程策略部子过程策略,表示为表示为pk(xk)QTA1A2A3B1B2B3C1C224374642442514633334第14页,本讲稿共32页(2)允许策略集合记作允许策略集合记作P。最优策略最优策略:从允许策略集中,找出的具有最优效从允许策略集中,找出的具有最优效果的策略。果的策略。QTA1A2A3B1B2B3C1C224374642442514633334第15页,本讲稿共32页5.状态转移方程状态转移方程(状态转移律状态转移律):多阶段决策过:多阶段决策过程的发展就是用阶段状态的相继演变来描述程的发展就是用阶段状态的相继演变来描述的。的。或简写为或简写为从上阶段的某一状态值到下阶段某一状态值的转从上阶段的某一状态值到下阶段某一状态值的转移规律成为移规律成为状态转移律状态转移律第16页,本讲稿共32页6.指标函数指标函数(1)阶段指标函数阶段指标函数(也称阶段收益也称阶段收益)(是对应某一阶(是对应某一阶段状态和从该状态出发的一个阶段的决策的某种效段状态和从该状态出发的一个阶段的决策的某种效益度量。)益度量。)vk(sk,xk)简记为简记为vk。(2)过程指标函数过程指标函数(指标函数指标函数)。(它所包含的它所包含的各阶段指标函数的函数。)各阶段指标函数的函数。)Vk,n(sk,xk,sk+1,xk+1,sn,xn)。简记为。简记为Vk,n。第17页,本讲稿共32页动态规划求解的问题的过程指标函数动态规划求解的问题的过程指标函数(指标函数指标函数),必须具有关于阶段指标的,必须具有关于阶段指标的可分离形式可分离形式(和、积和、积或其他形式或其他形式):表示某种运算,可为加、减、乘、除、开方等。表示某种运算,可为加、减、乘、除、开方等。第18页,本讲稿共32页常见有常见有:和和第19页,本讲稿共32页相相应的的子子策策略略称称为sk状状态下下的的最最优子子策策略略,记为pk*(sk);而而构构成成该子子策策略略的的各各段段决决策策称称为该过程上的最程上的最优决策,决策,记为7.最最优指指标函数:函数:fk(sk)有有简记为第20页,本讲稿共32页8.概念的关系。概念的关系。状态状态sk阶段阶段kT(sk,xk)决策决策xk(sk)vk(sk,xk)状态状态sk+1阶段阶段k+1T(sk+1,xk+1)决策决策xk+1(sk+1)vk+1(sk+1,xk+1)状态状态sk+2第21页,本讲稿共32页四、四、最优化原理与动态规划的数学模型最优化原理与动态规划的数学模型 1.1.最优化原理最优化原理 (贝尔曼最优化原理贝尔曼最优化原理)若某一全过程最优策略为:若某一全过程最优策略为:则则最最优化原理化原理:作为整个过程的最优策略具有这样:作为整个过程的最优策略具有这样的性质,无论过去的状态和决策如何,对先前决策的性质,无论过去的状态和决策如何,对先前决策所形成的状态而言,余下的诸决策必构成最优决策。所形成的状态而言,余下的诸决策必构成最优决策。第22页,本讲稿共32页2.动态规划的数学模型动态规划的数学模型(逆序法时逆序法时)(8.3a)(8.3b)第23页,本讲稿共32页(8.3c)(8.3d)或或(8.3b)和和(8.3d)称为边界条件。称为边界条件。第24页,本讲稿共32页五、五、动态规划方法的基本步骤动态规划方法的基本步骤1.阶段的划分阶段的划分2.正确地定义状态变量正确地定义状态变量sk第25页,本讲稿共32页(1)要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。(2)包包含含到到达达这这个个状状态态前前的的足足够够信信息息,且且满满足足无无后效性。后效性。(3)要满足可知性。要满足可知性。第26页,本讲稿共32页3.正确地定义决策变量及各阶段的允许决策集合正确地定义决策变量及各阶段的允许决策集合Dk(sk)4.能够正确地写出状态转移方程,至少要能能够正确地写出状态转移方程,至少要能正确反映状态转移规律。正确反映状态转移规律。第27页,本讲稿共32页5.根据题意根据题意,正确地构造出指标函数,应满足下正确地构造出指标函数,应满足下列性质:列性质:(1)可分性,可分性,(2)为了进行动态规划计算为了进行动态规划计算满足递推性,满足递推性,或或6.确立边界条件写出动态规划函数基本方程。确立边界条件写出动态规划函数基本方程。第28页,本讲稿共32页阶段阶段1阶段阶段2阶段阶段k阶段阶段k+1阶段阶段n状态状态S1决决策策x1状态状态S2v1决决策策x2状态状态S3v2决决策策xk状态状态Sk+1vk决决策策xk+1vk+1决决策策xnvn寻求最优解的方向寻求最优解的方向第29页,本讲稿共32页六、动态规划的分类六、动态规划的分类离散离散决策过程决策过程连续连续决策过程决策过程根据多阶段决策过程的根据多阶段决策过程的时间参量时间参量根据决策过程的根据决策过程的演变演变确定性确定性决策过程决策过程随机性随机性决策过程决策过程离散确定性离散确定性决策过程决策过程连续连续确定性确定性决策过程决策过程离散随机性离散随机性决策过程决策过程连续随机性连续随机性决策过程决策过程第30页,本讲稿共32页七七、学习方法建议、学习方法建议第一步第一步 先看问题,充分理解问题的条件、情况先看问题,充分理解问题的条件、情况及求解目标。及求解目标。第二步第二步 分析针对该动态规划问题的分析针对该动态规划问题的“四大要素、四大要素、一个方程一个方程”。第三步第三步 动手把求解思路整理出来,或者说,动手把求解思路整理出来,或者说,把该问题作为习题独立的来做。把该问题作为习题独立的来做。第31页,本讲稿共32页第四步第四步 把自己的求解放到一边,看书中的把自己的求解放到一边,看书中的求解方法,要充分理解教材中的论述。求解方法,要充分理解教材中的论述。第五步第五步 对照自己的求解,分析成败。对照自己的求解,分析成败。动态规划的四大要素动态规划的四大要素 状态变量及其可能集合状态变量及其可能集合 sk Sk 决策变量及其允许集合决策变量及其允许集合 xk Dk 状态转移方程状态转移方程 sk+1=Tk(sk,xk)阶段收益阶段收益 vk(sk,xk)第32页,本讲稿共32页

    注意事项

    本文(第二节最优化原理与动态规划优秀课件.ppt)为本站会员(石***)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开