文档介绍：动态规划
*
第1页，共52页，2022年，5月20日，15点16分，星期一
§4-1　引言
■ 动态规划的研究对象
■ 动态规划问题的特点
■ 静态决策问题的动态处理
*
第2页，共52页，20信息，阶段k的状态变量表示为sk。比如：在最短路问题中，状态就是网络中各个节点。
2、状态和状态变量
*
第12页，共52页，2022年，5月20日，15点16分，星期一
状态变量的取值有一定的允许范围，称为状态可能集。状态可能集可以是一个离散取值的集合，也可以是一个连续的区间，视所给问题而定。
状态可能集是关于状态的约束条件。状态可能集用相应阶段状态sk的大写字母Sk表示，
其中sk ∈Sk
*
第13页，共52页，2022年，5月20日，15点16分，星期一
决策就是决策者从本阶段出发对下一阶段状态的选择。
多段决策过程的发展是用各个阶段的状态演变描述的。因此用状态描述的过程具有无后效性，因此在进行阶段决策时，只须根据当前的状态而无须考虑过去的历史。在阶段k如果给出了决策变量xk随状态变量sk变化的函数，称为决策函数，表示为：xk(sk)。
3、决策和决策变量和决策序列
*
第14页，共52页，2022年，5月20日，15点16分，星期一
决策变量的允许取值范围，称为允许决策集合。允许决策集合是决策变量的约束条件。xk的允许决策集合表示为Xk。xk ∈Xk，Xk要根据相应的状态可能集Sk并结合具体问题来确定。
决策序列就叫策略，策略有全过程策略和子策略之分。全过程策略是整个问题n个段决策过程依次进行的n个阶段决策构成的序列，简称策略，表示为：
{x1,x2,…,xn}
*
第15页，共52页，2022年，5月20日，15点16分，星期一
从阶段k到阶段n依次进行的阶段决策构成的决策序列称为k-子策略。表示为：
{xk,xk+1,…,xn}
当k=1时， k-子策略就是全过程策略。
在n段决策过程中，各阶段的状态可能集合和决策允许集合决定了决策的允许范围。
特别，过程的初始状态不同，决策和策略也就不同，即策略是初始状态的函数。
*
第16页，共52页，2022年，5月20日，15点16分，星期一
状态转移方程表示从阶段k到阶段k+1的状态转移规律的表达式。
多阶段过程的发展就是用阶段状态的演变来描述的。对具有无后效性的多阶段决策过程，系统由从阶段k到阶段k+1的状态转移方程表示为：
sk+1=Tk (sk ,xk(sk))
4、状态转移方程
*
第17页，共52页，2022年，5月20日，15点16分，星期一
即阶段的状态完全由阶段的状态和决策确定，与系统过去的状态s1,s2,…,sk-1及其决策x1(s1),x2(s2),…,xk-1(sk-1)无关。
Tk (sk ,xk)称为变换函数或变换算子。变换函数可以分为确定型和随机型两种类型，据此形成确定型动态规划和随机型动态规划。
问：状态转移方程是否一定是数学意义上的方程？
*
第18页，共52页，2022年，5月20日，15点16分，星期一
多阶段决策过程中，在阶段k状态sk执行决策xk，不仅带来系统状态的转移，而且也带来对目标函数的影响。阶段效应就是执行阶段决策时所带来的目标函数的增量。
在具有无后效性的多阶段决策过程中，阶段效应完全由阶段k的状态sk和决策xk决定，与阶段以前的状态和决策无关，表示为：
Tk (sk ,xk)
5、阶段效应和目标函数
*
第19页，共52页，2022年，5月20日，15点16分，星期一
多阶段决策过程关于目标函数的总效应是由各阶段的阶段效应积累形成。适应于动态规划求解的问题的目标，必须具有关于阶段效应的可分离形式、递推性。
*
第20页，共52页，2022年，5月20日，15点16分，星期一
1、构模条件
一个大前提：恰当的划分问题的阶段，把问题化为多阶段决策过程；
四个条件：
1）正确地选择状态变量
能描述过程的演变特征；
满足无后效性
可知性—各阶段状态变量的值直接和间接均为已知。
2）能确定决策变量及各阶段的允许决策集合：
二、多阶段决策过程的数学模型
*
第21页，共52页，2022年，5月20日，15点16分，星期一
3）能写出状态转移方程；
4）能根据题意列出阶段效应和目标函数；
在明确四个条件（或四个要素）的基础上，写出动态规划基本方程。DP模型的数学表达一般形式：
式中OPT指最优化，根据问题要求取Max或Min
*
第22页，共52页，2022年，5月20日，15点16分，星期一
问：动态规划模型有那些部分组成？
具体的DP模型包括：四个条件和一个方程（动态规划基本方程）
*
第23页，