4-2动态规划的 婷。基本概念和模型
4-2 动态规划的 基本概念和模型
基本概念 DP中描述多殿决策过程的基本概念主要有 ●阶段和阶段变量 ●状态和状态变量; ●决策、决策变量和决策序列 ●状态转移方程 ●阶段效应和目标函数等
一、基本概念 DP中描述多段决策过程的基本概念主要有： 阶段和阶段变量； 状态和状态变量； 决策、决策变量和决策序列； 状态转移方程； 阶段效应和目标函数等
1.阶段和阶段变量 把所研究的多段决策过程恰当地划分为着干 个相互独立又相互联系的部分,每一个部分 就称为一个阶段。事实上一个阶段也就是需 要作出一个决策的子问题部分。通常阶段是 按照过程进行的时间和空间上的先后顺序划 分的,并用阶段变量k表示。阶段数等于多段 决策过程中从开始到结束所需要作出决策的 数目,划分阶段的目的是便于求解
1. 阶段和阶段变量 把所研究的多段决策过程恰当地划分为若干 个相互独立又相互联系的部分，每一个部分 就称为一个阶段。事实上一个阶段也就是需 要作出一个决策的子问题部分。通常阶段是 按照过程进行的时间和空间上的先后顺序划 分的，并用阶段变量k表示。阶段数等于多段 决策过程中从开始到结束所需要作出决策的 数目，划分阶段的目的是便于求解
2.状态和状态变量 状态是描述系统状况所必须的信息。一般 定义为某一个阶段的初始点、初始位置或 初始情况。状态变量必须包含在给定的阶 段上确定全部允许决策所需要的信息,阶 段k的状态表示为X。比如:在最短路问 题中,状态就是网络中的各个节点
2. 状态和状态变量 状态是描述系统状况所必须的信息。一般 定义为某一个阶段的初始点、初始位置或 初始情况。状态变量必须包含在给定的阶 段上确定全部允许决策所需要的信息，阶 段k的状态表示为xk。比如：在最短路问 题中，状态就是网络中的各个节点
状态变量的取值有一定的允许范围, 称为状态可能集。状态可能集可以是 个离散取值的集合,也可以是一个 ∠连续的区间,视所给问题而定。 状态可能集是关于状态的约束条件 状态可能集用相应阶段状态x的大写 字母X表示,其中 Xk∈Nk
状态变量的取值有一定的允许范围， 称为状态可能集。状态可能集可以是 一个离散取值的集合，也可以是一个 连续的区间，视所给问题而定。 状态可能集是关于状态的约束条件。 状态可能集用相应阶段状态xk的大写 字母Xk表示，其中xkXk
3.决策、决策变量和决策序列 决策就是决策者从本阶段出发对下一阶 段状态的选择 多段决策过程的发展是用各个阶段的状态 演变来描述的。因为用状态描述的过程具有 无后效性,因此在进行阶段决策时,只须根 据当前的状态而无须考虑过去的历史。在阶 段k如果给出了决策变量u随状态变量x变 化的函数,称为决策函数,表示为uk(X
3. 决策、决策变量和决策序列 决策就是决策者从本阶段出发对下一阶 段状态的选择。 多段决策过程的发展是用各个阶段的状态 演变来描述的。因为用状态描述的过程具有 无后效性，因此在进行阶段决策时，只须根 据当前的状态而无须考虑过去的历史。在阶 段k如果给出了决策变量uk随状态变量 xk变 化的函数，称为决策函数，表示为uk (xk )
决策变量的允许取值范围,称为允许决策 集合。允许决策集合是决策的约束条件。 的允许决策集合表示为U kpuk∈uk U要根 据相应的状态可能集X并结合具体问题来确 定 °决策序列就叫策略。策略有全过程策略 和k-子策略之分。全过程策略是整个n段 决策过程中依次进行的n个阶段决策构成 的决策序列,简称策略,表示为 152
决策变量的允许取值范围，称为允许决策 集合。允许决策集合是决策的约束条件。 uk 的允许决策集合表示为Uk，ukUk 。 Uk要根 据相应的状态可能集Xk并结合具体问题来确 定。 u1 ,u2 , ,un 决策序列就叫策略。策略有全过程策略 和k-子策略之分。全过程策略是整个n段 决策过程中依次进行的n个阶段决策构成 的决策序列，简称策略，表示为：
从阶段k到阶段n依次进行的阶段决策构 成的决策序列称为k-子策略,表示为 k2k+15 当k=1时,k-子策略就是全过程策略。 在n段决策问题中,各阶段的状态可能集和 y决策允许集确定了决策的允许范围。 特别,过程的初始状态不同,决策和策略也 就不同,即策略是初始状态的函数
从阶段k到阶段n依次进行的阶段决策构 成的决策序列称为k-子策略，表示为： uk ,uk+1 , ,un 当k=1时，k-子策略就是全过程策略。 在n段决策问题中，各阶段的状态可能集和 决策允许集确定了决策的允许范围。 特别，过程的初始状态不同，决策和策略也 就不同，即策略是初始状态的函数
4.状态转移方程 状态转移方程表示从阶段k到阶段k+1 的状态转移视律的表达式 多阶段过程的发展就是用阶段状态的相 继演变来描述的。对具有无后效性的多段 y决策过程,系统由从阶段k到阶段k+1的状 态转移方程表示为 Xki=lk(Xk, uk(Xk)
4. 状态转移方程 状态转移方程表示从阶段k到阶段k+1 的状态转移规律的表达式。 多阶段过程的发展就是用阶段状态的相 继演变来描述的。对具有无后效性的多段 决策过程，系统由从阶段k到阶段k+1的状 态转移方程表示为： x T (x , u (x )) k+1 = k k k k
意即阶段的状态完全由阶段的状态和决 策确定,与系统过去的状态x1,X2x…,Xk1及 其决策u1(X1,u2(x2),,uk1(无关。 T(xu称为变换函数或变换算子。变换函 数可以分为确定型和随机型两种类型,据此 形成确定型动态规划和随机型动态规划。 间:状态转移方程是否一定是数学意义上的 0方程?
意即阶段的状态完全由阶段的状态和决 策确定，与系统过去的状态 x1 ,x2 ,…,xk-1及 其决策u1 (x1 )，u2 (x2 )，…,uk-1 (xk-1 )无关。 Tk ( xk ,uk )称为变换函数或变换算子。变换函 数可以分为确定型和随机型两种类型，据此 形成确定型动态规划和随机型动态规划。 问：状态转移方程是否一定是数学意义上的 方程？