动态规划.ppt

*第八章动态规划*动态规划Dynamicprogramming五十年代贝尔曼()为代表的研究成果属于现代控制理论的一部分以长远利益为目标的一系列决策最优化原理,*决策树法可以枚举出20条路径,其中最短的路径长度为16*“最优策略的一部分也是最优的因此我们可以从B向回搜索最短路标记法如何找出最短路径*:把过程分成n个阶段。状态:每个阶段开始处的条件,如第i阶段的状态就是第i阶段的所有起始点的集合。决策:当过程处于某一阶段的某一个状态时,可以作出不同的决定,称为决策。策略:按顺序排列的决策的集合。*,各个节点就是状态生产库存问题中,库存量是状态物资分配问题中,剩余的物资量是状态控制变量(决策变量)最短路问题中,走哪条路生产库存问题中,各阶段的产品生产量物资分配问题中,分配给每个地区的物资量阶段的编号与递推的方向一般采用反向递推,所以阶段的编号也是逆向的当然也可以正向递推*动态规划的步骤1、确定问题的阶段和编号2、确定状态变量用Sk表示第k阶段的状态变量及其值3、确定决策变量用xk表示第k阶段的决策变量,并以xk*表示该阶段的最优决策4、状态转移方程sk-1=g(sk,xk)反向编号sk+1=g(sk,xk)正向编号5、直接效果直接一步转移的效果dk(sk,xk)6、总效果函数指某阶段某状态下到终端状态的总效果,它是一个递推公式*动态规划的步骤hk是一般表达形式,求当前阶段当前状态下的阶段最优总效果(1)如最短路问题,是累加形式,此时有终端的边际效果一般为f0(s0,x0)=0(2)如串联系统可靠性问题,是连乘形式,此时有终端的边际效果一般为f0(s0,x0)=1从第1阶段开始,利用边际效果和边界条件,可以递推到最后阶段*,已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时,可以存储起来备以后各月销售,一件产品的月存储费为2元,试安排月生产计划并做到:1、保证满足每月的销售量,并规定计划期初和期末库存为零;2、在生产能力允许范围内,安排每月生产量计划使产品总成本(即生产费用加存储费)最低。*例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估计第一阶段,即第4月份初库存的可能状态:s1[0,5]