动态规划运筹学基础及其应用胡运权第五版1.pptx

该【动态规划运筹学基础及其应用胡运权第五版1 】是由【小屁孩】上传分享，文档一共【34】页，该文档可以免费在线阅读，需要了解更多关于【动态规划运筹学基础及其应用胡运权第五版1 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第五章动态规划2021/10/101动态规划Dynamicprogramming五十年代贝尔曼()为代表的研究成果属于现代控制理论的一部分以长远利益为目标的一系列决策最优化原理,,其中最短的路径长度为162021/10/“最优策略的一部分也是最优的”每步的决策只与相邻阶段状态有关,而与如何达到这一状态无关因此我们可以从B向回搜索最短路标记法如何找出最短路径2021/10/(每阶段初始的出发点)最短路问题中,各个节点就是状态生产库存问题中,库存量是状态物资分配问题中,剩余的物资量是状态控制变量(决策变量)最短路问题中,走哪条路生产库存问题中,各阶段的产品生产量物资分配问题中,分配给每个地区的物资量阶段的编号与递推的方向一般采用反向递推,所以阶段的编号也是逆向的当然也可以正向递推2021/10/105动态规划的步骤1、确定问题的阶段和编号2、确定状态变量用Sk表示第k阶段的状态变量及其值3、确定决策变量用xk表示第k阶段的决策变量,并以xk*表示该阶段的最优决策4、状态转移方程sk-1=g(sk,xk)反向编号sk+1=g(sk,xk)正向编号5、直接效果直接一步转移的效果dk(sk,xk)6、总效果函数指某阶段某状态下到终端状态的总效果,它是一个递推公式2021/10/106动态规划的步骤hk是一般表达形式,求当前阶段当前状态下的阶段最优总效果(1)如最短路问题,是累加形式,此时有终端的边际效果一般为f0(s0,x0)=0(2)如串联系统可靠性问题,是连乘形式,此时有终端的边际效果一般为f0(s0,x0)=1从第1阶段开始,利用边际效果和边界条件,可以递推到最后阶段2021/10/,已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时,可以存储起来备以后各月销售,一件产品的月存储费为2元,试安排月生产计划并做到:1、保证满足每月的销售量,并规定计划期初和期末库存为零;2、在生产能力允许范围内,安排每月生产量计划使产品总成本(即生产费用加存储费)最低。2021/10/108例1产品生产计划安排设xk为第k阶段生产量,则有直接成本dk(sk,xk)=ckxk+2sk状态转移公式为sk-1=sk+xk-yk总成本递推公式第一阶段:(即第4月份)由边界条件和状态转移方程s0=s1+x1?y1=s1+x1?6=0得s1+x1=6或x1=6?s1?0估计第一阶段,即第4月份初库存的可能状态:0?s1?30?6?7?12=5,所以,s1?[0,5]2021/10/109第一阶段最优决策表第二阶段:最大可能库存量7件由状态转移方程:s1=s2+x2?12?0及x2?10,可知s2?[2,7],minx2=5由阶段效果递推公式有:f2(2,10)=d2(2,10)+f1*(0,6) =2?2+80?10+456=1260得第二阶段最优决策表,如下2021/10/1010