文档介绍：运筹学
第五章动态规划
本章重点
动态规划的四大要素、一个方程
动态规划问题的建模与求解
动态规划概念(1)
前面介绍的线性规划研究的是一次性的决策
线性规划决策过程可以总结为
在给定资源和环境的情况下,决定变量的取值,使某个目标达到最大或最小值
这个决策过程可以表示如下图
决策
x1
x2
u
Z
其中u 表示决策变量
x1 表示决策所依赖的资源和环境
Z表示目标函数
x2 表示决策后的资源和环境状况
动态规划概念(2)
例如,前面讲过的生产计划问题就是一次决策
某工厂用三种原料生产三种产品,已知的条件如下表所示,试制订总利润最大的日生产计划
产品所需原料数量
(公斤/ 件)
产品Q1
(件)
产品Q2
(件)
产品Q3
(件)
原料可用量
(公斤/日)
原料P1
2
3
0
1500
原料P2
0
2
4
800
原料P3
3
2
5
2000
产品的利润
(千元/ 件)
3
5
4
动态规划概念(3)
在这个模型中
模型中的A、b和C就是x1
模型中的X就是u
模型中的f(X)=CX就是Z
A、C和剩余的原料为x2
设每天生产三种产品的件数分别为x1、x2、x3
其线性规划模型为
决策
x1
x2
u
Z
动态规划概念(4)
如果上例中的生产计划不是只在一天里进行,而是连续一周,每天投入一定量的原料,剩余的原料后面可以继续使用,每天只允许生产一种产品并获得相应的利润。问怎样决策才能使一周的总利润最大?
解决这样的问题需要将决策过程分为多个阶段,本问题需要分为如下的7个阶段。
周日
x1
x2
u1
r1
周一
x3
u2
r2
周六
x8
u7
r7
x7
…
动态规划概念(5)
uk(k=1,2,3,4,5,6,7)表示第k天生产三种产品中的哪一种以及生产多少
x1=技术环境A、市场环境C和原料b
xk+1=技术环境A、市场环境C和原料b +第k天剩余的原料(k=1,2,3,4,5,6,7)
rk=第k天生产产品获得的利润
总利润=r1+ r2+ r3+ r4+ r5+ r6+ r7
动态规划就是解决这种多阶段决策过程的方法
多阶段决策过程(1)
其中包含n个决策子问题,每个子问题称为一个阶段,用变量k表示,称为阶段变量
xk描述k 阶段初系统的状况,称为状态变量
每个阶段有一个输入状态和一个输出状态
一般把输入状态称为该阶段的阶段状态
Tn
T1
x1
x2
u1
r1
T2
x3
u2
r2
Tk
xk+1
uk
rk
xk
…
xn+1
un
rn
xn
…
一般的多阶段决策过程表示如下
多阶段决策过程(2)
uk 代表k 阶段对第k 子问题进行的决策,称uk为k阶段的决策变量,uk的一组确定的取值称为一个决策
rk 表示k 阶段从状态xk 出发做决策uk 之后产生的后果,称为k 阶段的阶段效应
若在上述的多阶段决策过程中,系统 k 阶段以后的决策只与 k 阶段系统的状态 xk 有关,而与系统以前的决策无关,则称该多阶段决策过程具有无后效性
注:动态规划的建模和求解都是针对具有无后效性的多阶段决策过程
多阶段决策过程(3)
在具有无后效性的多阶段决策过程中,uk由xk 决定,rk 和xk+1 由xk 和uk 决定,因此
决策可以写为 uk(xk )
阶段效应可以写为 rk(xk , uk )
状态xk+1=Tk(xk , uk ) 称为状态转移方程, 其中Tk 是已知函数
多阶段决策过程中,从第k阶段到最终阶段的过程称为k-后部子过程,简称k-子过程