文档介绍：第五章动态规划
不要过河拆桥
1
动态规划 Dynamic programming
五十年代贝尔曼(B. E. Bellman)为代表的研究成果
属于现代控制理论的一部分
以长远利益为目标的一系列决策
最优化原理,可归结为一个递推公式
动态规划的最优化原理及其算法
求解多阶段决策过程的方法
最短路问题
2
决策树法
可以枚举出20条路径,其中最短的路径长度为16
3
最短路问题
表现为明显的阶段性
一条从A 到B 的最短路径中的任何一段都是最短的
最优性原理
“最优策略的一部分也是最优的”
每步的决策只与相邻阶段状态有关,而与如何达到这一状态无关
因此我们可以从B向回搜索最短路
标记法
如何找出最短路径
4
动态规划的基本概念及递推公式
状态(每阶段初始的出发点)
最短路问题中,各个节点就是状态
生产库存问题中,库存量是状态
物资分配问题中,剩余的物资量是状态
控制变量(决策变量)
最短路问题中,走哪条路
生产库存问题中,各阶段的产品生产量
物资分配问题中,分配给每个地区的物资量
阶段的编号与递推的方向
一般采用反向递推,所以阶段的编号也是逆向的
当然也可以正向递推
5
动态规划的步骤
1、确定问题的阶段和编号
2、确定状态变量
用 Sk 表示第 k 阶段的状态变量及其值
3、确定决策变量
用 xk 表示第 k 阶段的决策变量,并以 xk*表示该阶段的最优决策
4、状态转移方程
sk-1= g(sk, xk) 反向编号 sk+1= g(sk, xk) 正向编号
5、直接效果
直接一步转移的效果 dk(sk, xk)
6、总效果函数
指某阶段某状态下到终端状态的总效果,它是一个递推公式
6
动态规划的步骤
hk 是一般表达形式,求当前阶段当前状态下的阶段最优总效果
(1) 如最短路问题,是累加形式,此时有
终端的边际效果一般为 f0(s0, x0)=0
(2)如串联系统可靠性问题,是连乘形式,此时有
终端的边际效果一般为 f0(s0,x0)=1
从第1阶段开始,利用边际效果和边界条件,可以递推到最后阶段
7
动态规划模型举例
产品生产计划安排问题
例1 某工厂生产某种产品的月生产能力为10件,已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时,可以存储起来备以后各月销售,一件产品的月存储费为2元,试安排月生产计划并做到:
1、保证满足每月的销售量,并规定计划期初和期末库存为零;
2、在生产能力允许范围内,安排每月生产量计划使产品总成本(即生产费用加存储费)最低。
8
例1 产品生产计划安排
设xk为第k阶段生产量,则有直接成本
dk(sk, xk)= ck xk+2sk
状态转移公式为
sk-1= sk+ xk- yk
总成本递推公式
第一阶段:(即第4月份)
由边界条件和状态转移方程 s0=s1+x1y1= s1+x16=0 得
s1+x1= 6 或 x1= 6s10
估计第一阶段,即第4月份初库存的可能状态:
0 s1 306712=5,所以, s1 [0,5]
9
第一阶段最优决策表
第二阶段:最大可能库存量 7 件
由状态转移方程: s1=s2+x2120 及 x210,可知 s2[2,7],min x2=5
由阶段效果递推公式有:f2(2,10)=d2(2,10)+f1*(0,6) =22+8010+456=1260
得第二阶段最优决策表,如下
10