文档介绍：第四章
动态规划(guīhuà)问题
第一页，共41页。
动态规划的概念(gàiniàn)与模型
静态(jìngtài)决策 一次性决策
动态决策(juécè) 多阶段决策(juécè)
决策
x1
x2
Z
u
输入
决策
输出
决策效应
第一月
x1
x2
r1
u1
第二月
x3
r2
u2
第三月
x4
r3
u3
第二页，共41页。
多段决策(juécè)过程
T1
x1
x2
r1
u1
T2
x3
r2
u2
Tk
xk
xk+!
rk
uk
Tn
xn
xn+1
rn
un
…
…
n个决策子问题(wèntí)
K称为阶段变量
xk描述k阶段初的状态，称为状态变量
一般把输入状态称为该阶段的阶段状态。
uk的取值代表k阶段对第k子问题(wèntí)所进行的决策，称为k阶段的决策变量
rk为k阶段从状况xk出发,做决策uk之后的后果，称为k阶段的阶段效应。
第三页，共41页。
具有无后效性的多段决策(juécè)过程
Xk+1=Tk (xk, uk)
系统从k阶段往后的决策只与k阶段系统的状态xk有关,而与系统以前(yǐqián)的决策无关，则称为具有无后效性的多段决策过程。
T1
x1
x2
r1 (x1, u1)
u1(x1)
T2
x3
r2 (x2 ,u2)
u2 (x2)
Tk
xk
xk+!
rk (xk,uk)
uk (xk)
Tn
xn
xn+1
…
…
rn (xn,un)
un (xn)
第四页，共41页。
K后部(hòu bù)子过程
多段决策(juécè)过程中从第k阶段到最终阶段的过程称为k-后部子过程，简称k-子过程。
Tk
xk
xk+!
rk (xk,uk)
uk (xk)
Tn
xn
xn+1
…
rn (xn,un)
un (xn)
第五页，共41页。
动态(dòngtài)规划模型
Opt表示求优
Xk是一个集合，表示k阶段状态可能取值的范围，称为状态可能集合。
Uk是一个集合，表示k阶段决策可能取值的范围，称为决策允许集合，一般来说对于不同状态，可以作的决策的范围是不同的。因此(yīncǐ)决策允许集合一般写为Uk(xk)。
第六页，共41页。
动态(dòngtài)规划的建模
动态规划建模
①确定阶段与阶段变量
②明确状态变量和状态可能集合。
③确定决策变量和决策允许集合。
④确定状态转移方程(fāngchéng)。
⑤明确阶段效应和目标。
第七页，共41页。
动态(dòngtài)规划的建模
①确定阶段与阶段变量
阶段的划分一般是按照决策进行的时间或空间上的先后顺序划分的，阶段数等于多段决策过程中从开始到结束所需要作出决策的数目，阶段变量用k表示(biǎoshì)。
②明确状态变量和状态可能集合。
状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。状态变量的确定决定了整个决策过程是不是具有无后效性，因而也决定着能不能用动态规划方法来求解。状态可能集是关于状态的约束条件，因此为了求解必须正确地确定状态可能集。
第八页，共41页。
动态(dòngtài)规划的建模
③确定决策变量(biànliàng)和决策允许集合。
与静态问题相同，决策变量(biànliàng)应能够反映对问题所作的决策，决策变量(biànliàng)也应有其相应的约束条件，在建模时应明确决策允许集合Uk(xk)。
④确定状态转移方程。
系统k阶段从状态xk出发作了决策uk(xk)之后的结果之一是系统状态的转移，这一结果直接影响系统往后的决策过程，因此必须明确状态的转移过程，即根据问题的内在关系，明确xk+1=Tk(xk,uk)中的函数Tk（ ）。
第九页，共41页。
动态(dòngtài)规划的建模
⑤明确阶段效应和目标。
阶段效应rk(xk,uk)是在阶段k以xk出发作了决策uk之后所产生的后果，必须(bìxū)明确rk与xk，uk的关系，才能构成目标函数。目标函数是由阶段效应经过某种集结而得到的，如何集结视具体问题而定，同时还应根据问题确定目标是求最大还是最小。
由于在经济系统中的大多数情况下，目标的集结方法都是求和，因此，在不作说明的情况下，往后的讨论都针对目标为和的形式进行。
第十页，共41页。