动态规划 课件.ppt

文档介绍：动态规划
--- 2009数学建模培训---
动态规划
1. 动态规划的最优化原理及其算法
求解多阶段决策过程的方法
动态规划的基本概念及递推公式
动态规划的步骤
2. 动态规划模型举例
产品生产计划安排问题
资源分配问题
串联系统可靠性问题
动态规划 Dynamic programming
五十年代贝尔曼(B. E. Bellman)为代表的研究成果
属于现代控制理论的一部分
以长远利益为目标的一系列决策
最优化原理,可归结为一个递推公式
1 动态规划的最优化原理及其算法
求解多阶段决策过程的方法
例1 最短路问题
决策树法
可以枚举出20条路径,其中最短的路径长度为16
例1 最短路问题
表现为明显的阶段性
一条从A 到B 的最短路径中的任何一段都是最短的
最优性原理
“最优策略的一部分也是最优的”
每步的决策只与相邻阶段状态有关,而与如何达到这一状态无关
因此我们可以从B向回搜索最短路
标记法
如何找出最短路径
例2 某工厂生产某种产品的月生产能力为10件,已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时,可以存储起来备以后各月销售,一件产品的月存储费为2元,试安排月生产计划并做到:
1、保证满足每月的销售量,并规定计划期初和期末库存为零;
2、在生产能力允许范围内,安排每月生产量计划使产品总成本(即生产费用加存储费)最低。
动态规划的基本概念
(产品生产计划安排问题)
例2 产品生产计划安排
设xk为第k阶段生产量,则有直接成本
dk(sk, xk)= ck xk+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]
第一阶段最优决策表
第二阶段:最大可能库存量 7 件
由状态转移方程: s1=s2+x2120 及 x210,可知 s2[2,7],min x2=5
由阶段效果递推公式有:f2(2,10)=d2(2,10)+f1*(0,6) =22+8010+456=1260
得第二阶段最优决策表,如下
第二阶段最优决策表
第三阶段:最大可能库存量 4 件
由状态转移方程: s2=s3+x372 及 x310,可知 s3[0,4],min x3=5
由阶段效果递推公式有:f3(1,10)=d3(1,10)+f2*(4,8) =21+7210+1104=1826
得第三阶段最优决策表,如下
第三阶段最优决策表
第四阶段:初始库存量 s4=0
由状态转移方程: s3=s4+x460
可知 x46,由阶段效果递推公式有:f4(0,6)=d4(0,6)+f3*(0,10) =706+1902=2322
得第四阶段最优决策表,如下
回
溯
得
此
表