2动态规划的基本概念 1)阶段指标函数(也称阶段效应)。用 8(S,u)表示第k段处于s状态且所作决策为 k(s)时的指标,则它就是第k段指标函数,简记 为gk。图5-1的值就是从状态s到状态sA1的距 离。譬如,Bk(V2,V)=3,即吃到v的距离为3。 (2)过程指标函数(也称目标函数)。用 R(s2u)表示第k子过程的指标函数。如图51的 R(su)表示处于第k段s状态且所作决策为u时, 从S点到终点v0的距离。由此可见,R(s,u)不 仅跟当前状态s有关,还跟该子过程策略p(S) 有关,因此它是S和pk(S)的函数,严格说来, 应表示为: R(sk, Pk(sk))
27 (1) 阶段指标函数（也称阶段效应 ）。用 gk(sk,uk)表示第k段处于sk状态且所作决策为 uk(sk)时的指标，则它就是第k段指标函数，简记 为gk 。图5-1的gk值就是从状态sk到状态sk+1的距 离。譬如，gk(v2,v5)=3,即v2到v5的距离为3。 (2) 过程指标函数（也称目标函数 ）。用 Rk(sk,uk)表示第k子过程的指标函数。如图5-1的 Rk(sk,uk)表示处于第k段sk状态且所作决策为uk时， 从sk点到终点v10的距离。由此可见，Rk(sk,uk)不 仅跟当前状态sk有关，还跟该子过程策略pk(sk) 有关，因此它是sk和pk(sk)的函数，严格说来， 应表示为: 2.动态规划的基本概念 ( , ( )) k k k k R s p s
2动态规划的基本概念 不过实际应用中往往表示为R(sb,)或 R(s)。还跟第k子过程上各段指标函数有关 过程指标函数R(s)通常是描述所实现的全过 程或k后部子过程效果优劣的数量指标,它是 适于用动态规划求解的间题的过程指标函数 即目标函数),必须具有关于阶段指标的可 分离形式.对于部子过程的指标函数可以表示 为 R=R k,n(°kk°k+1k+1 gk(Sk2uk)gk+1(Sk+1,u4k+)④…⊕gn(Sn,un 式中,⊕表示某种运算,可以是加、减、乘 除、开方等。 28
28 不过实际应用中往往表示为Rk(sk,uk)或 Rk(sk)。还跟第k子过程上各段指标函数有关， 过程指标函数Rk(sk)通常是描述所实现的全过 程或k后部子过程效果优劣的数量指标，它是 由各阶段的阶段指标函数gk(sk,uk)累积形成的， 适于用动态规划求解的问题的过程指标函数 （即目标函数），必须具有关于阶段指标的可 分离形式．对于部子过程的指标函数可以表示 为： 式中，表示某种运算，可以是加、减、乘、 除、开方等。 2.动态规划的基本概念 ( , ) ( , ) ( , ) ( , , , , , , ) 1 1 1 , , 1 1 k k k k k k n n n k n k n k k k k n n g s u g s u g s u R R s u s u s u = = + + + + + (5-2)
2动态规划的基本概念 多阶段决策问题中,常见的目标函数形式之 是取各阶段效应之和的形式,即 Rk=∑g1(s,u1) i=k (5-3) 有些问题,如系统可靠性问题,其目标函数 是取各阶段效应的连乘积形式,如: Rk=I (5-4) k 总之,具体问题的目标函数表达形式需要视 具体问题而定。 29
29 多阶段决策问题中，常见的目标函数形式之 一是取各阶段效应之和的形式，即: (5-3) 有些问题，如系统可靠性问题，其目标函数 是取各阶段效应的连乘积形式，如： (5-4) 总之，具体问题的目标函数表达形式需要视 具体问题而定。 2.动态规划的基本概念 = = n i k k i i ui R g (s , ) = = n i k k i i ui R g (s , )
2动态规划的基本概念 (七)最优解 用4(s)表示第k子过程指标函数R(SA,p() 在状态S下的最优值,即 {R2(Sk,P(S),k=1,2,…,n 称fk(s)为第k子过程上的最优指标函数;与它 相应的子策略称为S状态下的最优子策略,记 为D*(s);而构成该子策赂的各段决策称为该 过程上的最优决策,记为n(l21(S)…;n( k+1k+1 1)…,un(Sn),=12,…,n 简记为 }2k=1,2
30 (七) 最优解 用fk(sk)表示第k子过程指标函数 在状态sk下的最优值,即 称fk(sk)为第k子过程上的最优指标函数；与它 相应的子策略称为sk状态下的最优子策略，记 为pk *(sk) ；而构成该子策赂的各段决策称为该 过程上的最优决策，记为 ； 有 简记为 2.动态规划的基本概念 ( , ( )) k k k k R s p s f s opt R s p s k n k k k k p P s k k k K k ( ) { ( , ( ))}, 1,2, , ( ) = = ( ), ( ), , ( ) k k k 1 k 1 n n u s u s u s + + p s u s u s u s k n k k k k k k n n ( ) { ( ), ( ), , ( )}, 1,2, , = 1 1 = + + pk = {uk ,uk 1 , ,un },k =1,2, ,n +
2动态规划的基本概念 特别当k1且s取值唯一时,f(s)就是问题的最 优值,而n*就是最优策略。如例只有唯一始点n 即s取值唯一,故f1(s)=18就是例的最优值,而 就是例的最优策略。 但若取值不唯一,则问题的最优值记为f有 fo =optf(s,))=fio 最优策略即为s1ˉs1*状态下的最优策略: p1(s1=S1)={1(S1),2…,ln 我们把最优策略和最优值统称为问题的最 优解
31 特别当k=1且s1取值唯一时，f1(s1)就是问题的最 优值，而p1 *就是最优策略。如例只有唯一始点v1 即s1取值唯一,故f1(s1)=18就是例的最优值，而 就是例的最优策略。 但若取值不唯一,则问题的最优值记为f0有 最优策略即为s1=s1 *状态下的最优策略： 我们把最优策略和最优值统称为问题的最 优解。 2.动态规划的基本概念 p1 = {v3 ,v7 ,v9 ,v10} { ( )} ( ) 0 1 1 1 1 1 1 1 f = opt f s = f s = s s S ( ) { ( ), , , } 1 1 1 1 1 2 = = u un p s s u s