文档介绍：动动态态规规划划动态规划是解决多阶段决策过程最优化的数学方法某个系统的运行过程可以分为若干个阶段,为控制系统的运行沿着预期的方向发展,在每个阶段都要作出决策,这个决策依赖于当前面临的状态,又给随后的发展以影响。当每一个阶段的决策确定下来,构成一个决策序列。动态规划方法利用 最优性原理作出最优决策,使目标函数达到最优解。最短路径问题 A B1B2 C1C2C3C4 D1D2D3 E1E2 G 1、阶段把一个问题的过程,恰当地分为若干个相互联系的阶段,以便于按一定的次序去求解。描述阶段的变量称为阶段变量。阶段的划分,一般是根据时间和空间的自然特征来进行的,但要便于问题转化为多阶段决策。 2、状态表示每个阶段开始所处的自然状况,它应能描述过程的特征并且具有无后效性;即当某阶段状态给定时,这个阶段以后过程的演变与该阶段以前各阶段的状态无关;描述过程状态的变量称为状态变量。用表示第 K阶段的状态变量。变量允许取值的范围, 称为允许状态变量集合。动态规划的基本概念 kS 3、决策:当一阶段的状态确定后,可以作出不同的选择从而演变到下一阶段的某个状态,这种选择手段称为决策。在最优控制问题中也称为控制。描述决策的变量,称为决策变量。决策变量的允许取值的范围称为允许决策集合。决策变量是状态变量的函数。用表示第 K 阶段处于状态时的决策变量; 表示的允许决策集合。 4、策略:决策组成的序列称为策略。由初始状态开始的全过程的策略记作,即由第 k阶段的状态开始到终止状态的子过程的策略记作; 可供选择的策略有一定的范围,称为允许策略集合, 用,,表示。)(u kkS kS )(U kkS kS 1S )(p 11nS??)( ),..., ( ),()(p 221111nnnsususuS? kS)(p knks)( 11nsP )( knksP )( kjksP 5、状态转移方程在确定性过程中,一旦某阶段的状态和决策为已知,下阶段的状态便完全确定。用状态转移方程表示为),,(S 1kkkkusT??n1,2,..., k? 6、指标函数和最优值函数指标函数是衡量过程优劣的数量指标。它是定义在在全过程或所有后部子过程上的数量函数,表示为动态规划模型的指标函数应具有可分离性,即可表示为的函数,记为) ;...; ,;,(V 111 kn???nkkkksususn1,2,..., k? knV nkkVu ,1k,,s ?) ;...; ,;,(V 111 kn???nkkkksusus)...., ,(,,( 111,1 k????? nkknkkksusVus?函数关于变量是严格单调的。 k? n1,kV ?),()( ,,)(p ,n k,nkknksP kkpsV opt s f knk??指标函数还可表示为状态和策略的函数 nk,V kS nk,p 即),(V ,nk,nkkps在给定时,指标函数对的最优值称为最优值函数,记作即 kS nk,V nk,p)(s f kk},,,{p **2 *1 *n k,nuuu??},,,{ *1 *2 *1?nsss? 7、最优策略和最优轨线使指标函数达到最优值的策略是从 k开始的后部子过程的最优策略,记作 nk,V是全过程的最优策略,简称为最优策略。从状态出发,过程按照和状态转移方程演变所经历的状态序列*1np)(s *11s?*1np称为最优轨线定理 1 若是最优策略,则对于任意的 k( 1<k<n) , 它的子策略对于由和确定的以为起点的第 k到n后部子过程而言, 也是最优策略。最优性原理)(p 11 *1nsP n?*nk,p 1s *1-k1,p *ks无论过去的状态和决策如何,相对于前面的决策所形成的状态而言,余下的决策序列必然构成最优子策略。即一个最优策略的子策略也是最优的。