'n(sk,Pn(s)》=Ψ(，4，V+n(s+,Pk+ln(sk+i》 其中P(S)={4,P+(}，41=T(S,山)，则同样地， f(Sk)=Vin(Sk P.n(S))=opt V.n(Sk Pi(S)) PA(S4)EP。(S) opt u(Sk,ug Vecin (Sk1 Pn(Sk1))}S=T(sk,ux) tugPi(5(5) opt w(Sk,ug,opt Vn (Sk,Ptn(Sk))}Sk=T(Ss,uk) 4∈U() P1n(a(i） =OpttΨ(Sk,uk,f+1(Sk+)}Sk+1=T(Sk,山) 4∈U(s） =opt wi(Sx,ugf(T(Sk,ug))} 4∈04(S4) 即f(S)=opt{x(Sk,4k,f(Tk(S,4)}。 对于动态规划顺序解法，用S%表示第k阶段末的状态。决策变量，(S)表示第k阶段末状态为S%时 第k阶段所做的决策，允许决策范围为UK(S)。状态转移方程为Sk-1=T(Sk,4)。策略 Pu(s)=((b4,(s)小…，4--b4(s》，其中5k-1=T(S,4)，…，S=T(s2,2），则 Px(S)={B-(S-),4},其中Sk-1=T(Sk,山)。阶段指标函数为以(Sk,山)，k前过程指标函数为 (S0,4,S…Sk-1,4k,S)，其中Sk-1=T(Sk,4s),，S0=T(S1,4)。(S0,4,…S-1,4,S)可记为 u(Pu(5.)5)。最优值函数为f(S)=p1,(P(Sbs)。 px(5 )ER(st) 若，4,4，)=)，则P,人)=P5)+,4)，其中 Sk-1=T(Sk,4)。于是，对k=1,…,n,有 f(S)=Vi(Pix (S ),5x)=opt V.(pL(Sk).S) pua(5)eRx(5) opt Vik-i(P(Sk-1),S-1)+v(Sk,ug)}S-1=T (Sx,ux) {PAk-(sk-b4e(g） opt{opt Vki(p-i(5k).5)+v(sxuk)5-=T (5,u) e(）Pnk-(s-)eB-(-t） =0pt{f-(sk-1)+(S,4)}s-1=Tg(sk,4g) 联eU(s) optf(T (skug))+v (Sk:ug 4∈U(s) 即 f(s)=optfT (sgug))+(sg,ug).k=1,....n 4∈U(s&) fo(so)=0 一一动态规划顺序解法的基本方程 最后求出f(Sn)。设上述递推关系中相应的最优解为(S.),则最优策略为 {4(S),4(S2)2…,4n-1(sm-i),4n(Sn)},sm-1=Tm(Sn,n(sn)…,S1=T(S2,4(S2) —逆序确定最优策略 个7 , , 1, 1 1, 1 ( , ( )) ( , , ( , ( ))) V s p s suV s p s kn k kn k k k k k n k k n k =ψ + ++ + 其中 , 1, 1 ( ) { , ( )} kn k k k n k p s up s = + + ， 1 (, ) k kk k s Tsu + = ，则同样地， , , 1, 1 , 1, 1 1, 1 * ,, ,, () () 1, 1 1, 1 1 { , ( )} ( ) ( ) ( )} ( ) ( ) ( , ( )) ( , ( )) { ( , , ( , ( ))} ( , ) { (, , kn k kn k k k n k kn k k kk knk knk k k kn k kn k kn k kn k p sPs k k k knk knk k k k k up s P s kkk uUs p s P s f s V s p s opt V s p s opt s u V s p s s T s u opt s u opt V ψ ψ + + ++ ++ ∈ + ++ + + ∈ ∈ ∈ = = = = = 1, 1 1, 1 1 11 1 ( ) 1 ( ) ( , ( ))} ( , ) { ( , , ( )} ( , ) { ( , , ( ( , ))} k kk k kk knk knk k k k k kkk k k k kkk uUs kk k k kk k uUs s p s s Tsu opt s u f s s T s u opt s u f T s u ψ ψ + ++ + + ++ + ∈ + ∈ = = = = 即 1 ( ) ( ) { ( , , ( ( , ))} k kk kk kk k k kk k uUs f s opt s u f T s u ψ + ∈ = 。 对于动态规划顺序解法，用 sk表示第 k 阶段末的状态。决策变量 uk(sk)表示第 k 阶段末状态为 sk时 第 k 阶段所做的决策，允许决策范围为 ( ) r U s k k 。状态转移方程为 1 (, ) r k k kk s T su − = 。策略 1, 1 1 2 2 1 1 ( ) ( ( ), ( ) , ( ), ( )) kk k k kk p s us us u s u s = " − − ，其中 1 (, ) r k k kk s T su − = ， … ， 1 2 22 (, ) r s = T su ， 则 1, 1, 1 1 ( ) { ( ), } kk k k k ps p s u = − − ，其中 1 (, ) r k k kk s T su − = 。阶段指标函数为 (, ) r kkk vsu ，k 前过程指标函数为 1, 0 1 1 1 (,, , , ) V sus s u s k k kk " − ，其中 1 (, ) r k k kk s T su − = ，…， 0 1 11 (, ) r s = T su 。 1, 0 1 1 1 (,, , , ) V sus s u s k k kk " − 可记为 1, 1, ( ( ), ) Vpss k kk k 。最优值函数为 1, 1, 1, 1, () () ( ) ( ( ), ) kk kk kk k kk k p s Ps f s opt V p s s ∈ = 。 若 1, 0 1 1 1 (,, , , ) (, ) k r k kk j j j j V sus u s vsu = " = ∑ ，则 1, 1, 1, 1 1, 1 1 1 ( ( ), ) ( ( ), ) ( , ) r V p s s V p s s vsu k kk k k k k k kk k = + − −− − ， 其中 1 (, ) r k k kk s T su − = 。于是，对 k n =1, , " ，有 1, 1, 1, 1 1 1, 1, 1 1 1, 1 1 * 1, 1, 1, 1, () () 1, 1 1, 1 1 1 1 { ( ), } ( ) 1, 1 ( ) ( )} ( ) ( ) ( ( ), ) ( ( ), ) { ( ( ), ) ( , )} ( , ) { kk kk k k k kk r k kk kk kk kk k kk k k kk k p s Ps r r k k k k kkk k k kk p s u Ps k uUs p s Ps f s V p s s opt V p s s opt V p s s v s u s T s u opt opt V − − −− −− ∈ − −− − − ∈ − ∈ ∈ = = = += = 1, 1 1 1 1 11 1 ( ) 1 ( ) ( ( ), ) ( , )} ( , ) { ( ) ( , )} ( , ) { ( ( , )) ( , )} r k kk r k kk r r k k k kkk k k kk r r k k kkk k k kk uUs r r k k kk kkk uUs p s s vsu s T su opt f s v s u s T s u opt f T s u v s u −− − − −− − ∈ − ∈ + = = += = + 即 1 ( ) 0 0 ( ) { ( ( , )) ( , )}, 1, , () 0 r k kk r r kk k k k k kk k uUs f s opt f T su vsu k n f s − ∈ ⎧ = += ⎪ ⎨ ⎪⎩ = " ——动态规划顺序解法的基本方程 最后求出 ( ) n n f s 。设上述递推关系中相应的最优解为 * ( ) k k u s ，则最优策略为 ** * * * * 11 22 1 1 1 1 2 2 22 { ( ), ( ), , ( ), ( )}, ( , ( )), , ( , ( )) r r n n nn n n n nn us us u s us s T sus s T sus " " −− − = = ——逆序确定最优策略