《动态规划的基本概念与方法课件.ppt》由会员分享，可在线阅读，更多相关《动态规划的基本概念与方法课件.ppt（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一节 动态规划的基本概念与方法一、多阶段决策问题1.时间阶段的例子（机器负荷问题）某厂有1000台机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大。123 4 5S1=1000 x1x2x5x4x3s5v1v2v3v4v5s2s3s42.空间阶段的例子（最短路问题）如图为一线路网络。现要从A点铺设一条管道到E点，图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路，使总距离最短。AEB1B2B3C1C2C3D1D229531225156468101312111410阶段1 阶段2 阶段3 阶段4二、基本概念与方程 1.基本概
2、念阶段分步求解的过程，用阶段变量k表示，k=1，n状态每阶段初可能的情形或位置，用状态变量Sk表示。按状态的取值是离散或连续，将动态规划问题分为 离散型和连续型。决策每阶段状态确定后的抉择，即从该状态演变到下阶 段某状态的选择，用决策变量xk表示。状态转移由Sk转变为Sk+1的规律，记Sk+1=T(Sk，xk)。策略由各阶段决策组成的序列，记P1n=x1，xn，称Pkn=xk，xn为阶段k至n的后部子策略。阶段指标每阶段选定决策xk后所产生的效益，记 vk=vk(Sk，xk)。指标函数各阶段的总效益，记相应于Pkn的指标函数 为vkn=vkn(Sk，Pkn)。其中最优的称最优 指标函数，记 f
3、k=fk（Sk）=opt vkn。问题：动态规划的最优解和最优值各是什么？最优解：最优策略P1n，最优值：最优指标f1。2.基本原理与基本方程（1）基本原理以最短路为例说明（2）基本方程 根据最优性原理，可建立从后向前逆推求解的递推公式基本方程：动态规划求解的一般步骤：-确定过程的分段，构造状态变量；-设置决策变量，写出状态转移；-列出阶段指标和指标函数；-写出基本方程，由此逐段递推求解。三、求解方法1.离散型（用表格方式求解）例1 用动态规划方法求解前面的最短路问题。AEB1B2B3C1C2C3D1D229531225156468101312111410AEB1B2B3C1C2C3D1D22
4、9531225156468101312111410解：设阶段k=1，2，3，4依次表示4个阶段选路的过程；状态sk表示k阶段初可能处的位置；决策xk表示k阶段初可能选择的路；阶段指标vk表示k阶段与所选择的路段相应的路长；指标函数 vk4=表示k至4阶段的总路长；AEB1B2B3C1C2C3D1D2295312251564681013121114104k Sk xk vk vkn=vk+fk+1 fk3C1C2C38712C1D1EC2D2EC3D2Ek Sk xk vk vkn=vk+fk+1 fkAEB1B2B3C1C2C3D1D2295312251564681013121114102B1
5、B2B320B1C1D1E14B2C1D1E19B3C2D2Ek Sk xk vk vkn=vk+fk+1 fkAEB1B2B3C1C2C3D1D2295312251564681013121114101A19AB2C1D1EP*14=AB2C1D1Ef1=19（最短路）（最短距）2.连续型（用公式递推求解）例2 用动态规划方法求解前面的机器负荷问题。某种机器可以在高、低两种负荷下进行生产。高负荷年产量8，年完好率0.7；低负荷年产量5，年完好率0.9。现有完好机器1000台，需制定一个5年计划，以决定每年安排多少台机器投入高、低负荷生产，使5年的总产量最大。解：设阶段k=1，5表示第k年安排机器的过程；状态sk表示第k年初的完好机器台数；决策xk表示第k年投入高负荷的机器台数；则投入低负荷的台数为sk-xk；状态转移sk+1=0.7xk+0.9(sk-xk)；阶段指标vk=8xk+5(sk-xk)表示第k年的产量；指标函数vkn=表示第k至5年的总产量；5年的最大总产量为23.721000=23720。