运筹学课件-动态规划.ppt

《运筹学课件-动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划8.1多阶段决策问题与动态规划8.2动态规划的基本概念8.3动态规划的步骤8.4动态规划的应用1求解静态规划问题2资源分配问题3不确定性采购问题4排序问题8/22/2021运筹学课件动态规划所研究的对象是多阶段决策问题。所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。8.1多阶段决策问题与

2、动态规划8/22/2021运筹学课件安全过河问题古代有3位商人各自带了一个仆人外出来到了一个渡口,渡口只有一条小船每次只能乘2人,仆人私下约定只要岸上的仆人人数超过商人人数,就可杀人越货.但是过河的决策由商人制定.问商人如何安全的渡过河去?8/22/2021运筹学课件8/22/2021运筹学课件一、多阶段决策问题1.时间阶段的例子（机器负荷问题）某厂有1000台机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大。12345S1=1000x1x2x5x4x3s5

3、v1v2v3v4v5s2s3s48.1多阶段决策问题与动态规划8/22/2021运筹学课件2.空间阶段的例子（最短路问题）如图为一线路网络。现要从A点铺设一条管道到E点，图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路，使总距离最短。AEB1B2B3C1C2C3D1D229531225156468101312111410阶段1阶段2阶段3阶段48/22/2021运筹学课件动态规划解决问题的基本特征1.动态规划一般解决最值（最优，最大，最小，最长……）问题；2.动态规划解决的问题一般是离散的，可以分

4、解（划分阶段）的；3.动态规划解决的问题必须包含最优子结构，即可以由（n－1）的最优推导出n的最优8/22/2021运筹学课件动态规划模型的分类：以“时间”角度可分成：离散型和连续型。从信息确定与否可分成：确定型和随机型。从目标函数的个数可分成：单目标型和多目标型。8/22/2021运筹学课件1.基本概念阶段（Stage）——分步求解的过程，用阶段变量k表示，k=1，，n状态（State）——每阶段初可能的情形或位置，用状态变量Sk表示。按状态的取值是离散或连续，将动态规划问题分为离散型和连续型。决策（Decis

5、ion）——每阶段状态确定后的抉择，即从该状态演变到下阶段某状态的选择，用决策变量xk表示。状态转移——由Sk转变为Sk+1的规律，记Sk+1=T(Sk，xk)。策略（Policy）——由各阶段决策组成的序列，记P1n={x1，…，xn}，称Pkn={xk，…，xn}为阶段k至n的后部子策略。8.2基本概念与方程8/22/2021运筹学课件当前状态以前状态决策显然,从上图可以看出,当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。KSkSk+1XkVk8/22/

6、2021运筹学课件过河:决策向量xk(I,J)初始状态s1是T(3,3)结束状态sn是T(0,0)可达状态有哪些?(3,J)(2,2)(1,1)(0,J)0321123AJII表示留在左岸的商人人数J表示留在左岸的仆人人数8/22/2021运筹学课件阶段指标——每阶段选定决策xk后所产生的效益，记vk=vk(Sk，xk)。指标函数——各阶段的总效益，记相应于Pkn的指标函数为vkn=vkn(Sk，Pkn)。其中最优的称最优指标函数，记fk=fk（Sk）=optvkn。问题：动态规划的最优解和最优值各是什么？——最

7、优解：最优策略P1n，最优值：最优指标f1。8/22/2021运筹学课件多阶段决策过程d1d2dNs1s2s3sNsN+112NV1V2VNN阶段决策系统示意图8/22/2021运筹学课件2.基本原理与基本方程（1）基本原理以最短路为例说明8/22/2021运筹学课件（2）基本方程根据最优性原理，可建立从后向前逆推求解的递推公式——基本方程：通常动态规划问题的最优值函数满足递推关系式.。边界条件8/22/2021运筹学课件动态规划求解的一般步骤：-确定过程的分段，构造状态变量；-设置决策变量，写出状态转移；-列

8、出阶段指标和指标函数；-写出基本方程，由此逐段递推求解。KSkSk+1XkVk8.3动态规划的求解方法8/22/2021运筹学课件例1用动态规划方法求解前面的最短路问题。AEB1B2B3C1C2C3D1D2295312251564681013121114101.离散型求解方法8/22/2021运筹学课件标号法求解在每个节点上标出从该节点到终点的最短距离AEB1B2B3C1