2动变规划的基本概 (二)状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物 (或系统)在某特定的时间与空间域中所处 位置及运动特征的量,称为状态。反映状 态变化的量叫做状态变量。状态变量些须 包含在给定的阶段上确定全部允许决策所 需要的信息。按照过程进行的先后,每个 阶段的状态可分为初始状态和终止状态 或称输入状态和输出状态,阶段k的初始 状态记作S,终止状态记为S但为了 清楚起见,通常定义阶段的状态即指其初 始状态
21 2.动态规划的基本概念 （二）状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物 (或系统)在某特定的时间与空间域中所处 位置及运动特征的量，称为状态。反映状 态变化的量叫做状态变量。状态变量必须 包含在给定的阶段上确定全部允许决策所 需要的信息。按照过程进行的先后，每个 阶段的状态可分为初始状态和终止状态， 或称输入状态和输出状态，阶段k的初始 状态记作sk，终止状态记为sk+1。但为了 清楚起见，通常定义阶段的状态即指其初 始状态
2.动恋规划的基本概A 2.可能状态集 般状态变量的取值有一定的范围或允许集 合,称为可能状态集,或可达状态集。可能状态 集实际上是关于状态的约束条件。通常可能状态 集用相应阶段状态S的大写字母S表示,S∈S, 可能状态集可以是一离散取值的集合。也可以为 连续的取值区间,视具体问题而定,在图5-1 所示的最短路问题中,第一阶段状态为Ⅵ,状态 变量S1的状态集合S1={h;第二阶段则有三个状 态:V 状态变量S的状态集合 第三阶段也有三个状 态:v,而,v,状态变量S3的状态集合 5 第四阶段则有二个状态 ,状态变量s的状态集合S4={vs,V
22 2.动态规划的基本概念 2．可能状态集 一般状态变量的取值有一定的范围或允许集 合，称为可能状态集，或可达状态集。可能状态 集实际上是关于状态的约束条件。通常可能状态 集用相应阶段状态sk的大写字母Sk表示，sk∈Sk， 可能状态集可以是一离散取值的集合，也可以为 一连续的取值区间，视具体问题而定．在图5—1 所示的最短路问题中，第一阶段状态为v1，状态 变量s1的状态集合S1={v1}；第二阶段则有三个状 态 ： v2 ,v3 ,v4 , 状态变量 s2 的 状 态 集 合 S2={v2 ,v3 ,v4} ； 第 三 阶 段 也 有 三 个 状 态 :v5 ,v6 ,v7 ， 状 态 变 量 s3 的 状 态 集 合 S3={v5 ,v6 ,v7} ； 第 四 阶 段 则 有 二 个 状 态 ： v8 ,v9 , 状态变量s4的状态集合S4={v8 ,v9} ；
2.动变规划的基本概龙 (三)决策、决耽变量和允许决策集合 所谓决策,就是确定系统过程发展的方案。 决策的实质是关于状态的选择·是决策者从给定 阶段状态出发对下一阶段状态作出的选择。 用以描述决策变化的量称之决策变量和状 态变量一样,决策变量可以用一个数,一组数或 向量來描述,也可以是状恋变量的函数,记以 =uk(S),表示于阶段k状态S时的决策变量。 决策变量的取值往往灺有一定的允许范围 称之允许决策集合。决策变量uk(S)的允许决策 集用(S)表示,(S∈(5)允许决策集合 实际是决策的约束条件
23 （三）决策、决策变量和允许决策集合 所谓决策，就是确定系统过程发展的方案。 决策的实质是关于状态的选择，是决策者从给定 阶段状态出发对下一阶段状态作出的选择。 用以描述决策变化的量称之决策变量和状 态变量一样，决策变量可以用一个数，一组数或 一向量来描述，也可以是状态变量的函数，记以 uk= uk(sk)，表示于阶段k状态sk时的决策变量。 决策变量的取值往往也有一定的允许范围， 称之允许决策集合。决策变量uk(sk)的允许决策 集用Uk(sk)表示, uk(sk)∈ Uk(sk)允许决策集合 实际是决策的约束条件。 2.动态规划的基本概念
2.动变规划的基本概龙 (四)、策略和允许簟略集合 策略( Policy)也叫决策序列.策略有全过程 策略和k部子策略之分,全过程策略是指具有个 阶段的全部过程,由依次进行的1阶段决策构 成的决策序列简称策略.表示为 n、n{u,l,灬,un}。从k阶段到第l阶段,依次进行 的阶段决策构成的决策序列称为部子策略,表示 为k,n },显然当k=1时的k部子策略 就是全过程策略。 在实际问题中,由于在各个阶段可供选择的决策 有许多个,因此,它们的不同组合就构成了许多 可供选择的决策序列(策略),由它们组成的集合, 称之允许策略集合,记作B、n,从允许策略集中, 找出具有最优效果的策略称为最优策略。 24
24 （四）、策略和允许策略集合 策略(Policy)也叫决策序列．策略有全过程 策略和k部子策略之分，全过程策略是指具有n个 阶段的全部过程，由依次进行的n个阶段决策构 成 的 决 策 序 列 ， 简 称 策 略 ， 表 示 为 p1,n{u1,u2,…,un}。从k阶段到第n阶段，依次进行 的阶段决策构成的决策序列称为k部子策略,表示 为pk,n{uk,uk+1,…,un} ，显然当k=1时的k部子策略 就是全过程策略。 在实际问题中，由于在各个阶段可供选择的决策 有许多个，因此，它们的不同组合就构成了许多 可供选择的决策序列(策略)，由它们组成的集合， 称之允许策略集合，记作P1,n ，从允许策略集中， 找出具有最优效果的策略称为最优策略。 2.动态规划的基本概念
2.动变规划的基本概龙 (五)状态转移方程 系统在阶段k处于状态S,执行决策l1(Sk 的结果是系统状态的转移,即系统由阶段k的初 始状态S转移到终止状态Sk1,或者说,系统由 k阶段的状态Sk转移到了阶段什1的状态SA1,多 阶段决策过程的发展就是用阶段状态的相继演变 来描述的。 对于具有无后效性的多阶段决策过程,系统 由阶段k到阶段1的状态转移完全由阶段A的状 态S和决策(S所确定,与系统过去的状态 及其决策1(s1),l2(S2).h21(Sk 元关。系统状态的这种转移,用数学公式描述即 有 Sk+1=TK(Sk,u()) (5-1) 25
25 （五）状态转移方程 系统在阶段k处于状态sk，执行决策uk(sk) 的结果是系统状态的转移，即系统由阶段k的初 始状态sk转移到终止状态sk+1 ，或者说，系统由 k阶段的状态sk转移到了阶段k+1的状态sk+1 ，多 阶段决策过程的发展就是用阶段状态的相继演变 来描述的。 对于具有无后效性的多阶段决策过程,系统 由阶段k到阶段k+1的状态转移完全由阶段k的状 态sk和决策uk(sk)所确定，与系统过去的状态 s1,s2,… ,sk-1及其决策u1(s1), u2(s2)…uk-1(sk-1) 无关。系统状态的这种转移，用数学公式描述即 有： 2.动态规划的基本概念 ( , ( )) k 1 k k k k s = T s u s + (5-1)