42动态规划的基本概念 2.可能状态集 般状态变量的取值有一定的范围或允许集 合,称为可能状态集,或可达状态集。可能状态 集实际上是关于状态的约束条件。通常可能状态 集用相应阶段状态Sk的大写字母S表示,S∈ 可能状态集可以是一离散取值的集合,也可以为 连续的取值区间,视具体问题而定.在图5-1 所示的最短路问题中,第一阶段状态为,状态 变量s1的状态集合S={v};第二阶段则有三个状 态:V,3,V,状态变量s2的状态集 ;第三阶段也有三个状 状态变量s3的状态集 S3={v5,v6,;第四阶段则有二个状态: vg,vg,状态变量s的状态集合S={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时的决策变量。 决策变量的取值往往也有一定的允许范围, 称之允许决策集合。决策变量u(s)的允许决策 集用U(s)表示,(s)∈V(s)允许决策集合 实际是决策的约束条件
23 （三）决策、决策变量和允许决策集合 所谓决策，就是确定系统过程发展的方案。 决策的实质是关于状态的选择，是决策者从给定 阶段状态出发对下一阶段状态作出的选择。 用以描述决策变化的量称之决策变量和状 态变量一样，决策变量可以用一个数，一组数或 一向量来描述，也可以是状态变量的函数，记以 uk= uk(sk)，表示于阶段k状态sk时的决策变量。 决策变量的取值往往也有一定的允许范围， 称之允许决策集合。决策变量uk(sk)的允许决策 集用Uk(sk)表示, uk(sk)∈ Uk(sk)允许决策集合 实际是决策的约束条件。 2.动态规划的基本概念
2动态规划的基本概念 (四)、策略和允许策略集合 策略( Policy)也叫决策序列.策略有全过程 策略和k部子策略之分,全过程策略是指具有n个 阶段的全部过程,由依次进行的n个阶段决策构 成的决策序列,简称策略,表示为 从k阶段到第n阶段,依次进 的阶段决策构成的决策序列称为k部子策略,表示 为p,n{uUk1,…,un},显然当k=1时的k部子策略 就是全过程策略。 在实际问题中,由于在各个阶段可供选择的决策 有许多个,因此,它们的不同组合就构成了许多 可供选择的决策序列(策略),由它们组成的集合, 称之允许策略集合,记作β、n,从允许策略集中 找出具有最优效果的策略称为最优策略
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,执行决策uk(S 的结果是系统状态的转移,即系统由阶段k的初 始状态Sk转移到终止状态Sk1,或者说,系统由 k阶价段的状态S转移到了阶段k+1的状态sA1,多 阶段决策过程的发展就是用阶段状态的相继演变 来描述的。 对于具有无后效性的多阶段决策过程,系统 由阶段k到阶段k+1的状态转移完全由阶段k的状 s,.5,,561及其决策1(s),边(5)(s 无关。系统状态的这种转移,用数学公式描述即 有: +1=Tk(,4(S)
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)
2.动态规划的基本概念 通常称式(5-1)为多阶段决策过程的状态转移方 程。有些问题的状态转移方程不一定存在数学 表达式,但是它们的状态转移,还是有一定规 律可循的。 (六)指标函数 用来衡量策略或子策略或决策的效果的某 种数量指标,就称为指标函数。它是定义在全 过程或各子过程或各阶段上的确定数量函数。 对不同问题,指标函数可以是诸如费用、成本 产值、利润 耗量、距离、时间、效用, 等等。例如:图5-1的指标就是运费
26 通常称式(5-1)为多阶段决策过程的状态转移方 程。有些问题的状态转移方程不一定存在数学 表达式，但是它们的状态转移，还是有一定规 律可循的。 (六) 指标函数 用来衡量策略或子策略或决策的效果的某 种数量指标，就称为指标函数。它是定义在全 过程或各子过程或各阶段上的确定数量函数。 对不同问题，指标函数可以是诸如费用、成本、 产值、利润、产量、耗量、距离、时间、效用， 等等。例如：图5—1的指标就是运费。 2.动态规划的基本概念