动态规划84067

1、精品文档你我共享AAAAAA第七章动态规划常见疑问解答1、动态规划是怎样产生的?1951年，R . Bellman等人，根据某类多阶段序贯决策问题的特点，提出了著名的“最优性原理”。在这个原理的指导下，他将此类多阶段决策问题转变 为一系列的互相联系的单阶段决策问题， 然后，逐个阶段予以解决，最后再形成总体解决。从而创建了求解优化问题的新方法一一动态规划。1957年，他的名著动态规划出版。2、动态规划的基本概念有哪些?阶段、（阶段）状态、状态变量 Si、状态集S、决策、决策变量Ui（Si）、决 策集D（Si）、状态转移方程、决策的指标函数、策略的指标函数、最优值函数等。3、什么是阶段?动态规划的

2、阶段指的是决策发生的时间或空间区隔。4、如何划分动态规划问题的阶段?动态规划问题的阶段划分一般可依据决策发生的次数和每次决策发生并作 用的时间段或空间段来定。5、什么是（阶段）状态?状态既可以指一个阶段上作决策时所依据的自然状况和客观条件，又可以指 一个阶段上所作决策后的结局状况， 故一个阶段的状态常有首、末状态之分，以 区别阶段上决策的出发点和结局状况。但，一般地，人们往往仅选择各阶段的首、 末状态之一，作为各阶段的状态，所以，当谈到各阶段的状态时，要么都指的是 各阶段的首状态，要么都指的是各阶段的末状态。6、什么是（阶段）状态变量?精品文档你我共享AAAAAA状态变量是对一个阶段上状态（多

3、种）取值情形的描述。人们常用符号Sk表示第k个阶段上的状态变量，k= 1,2,n.10、n.7、什么是动态规划问题的维数?动态规划问题的维数即指的是各阶段上状态变量的维数。8、各阶段上状态变量的维数是如何确定的?动态规划问题各阶段上的状态常常可能需要用几个属性才能描述清楚。如各 个阶段上都要依据资源状态作出生产数量决策时， 若生产资源有3种类型，则资 源状态就必须用三种类型的资源，即三个属性来共同描述。相应地，资源状态变 量就必须用三维向量表示各类资源的取值情形。因此，各阶段上状态变量的维数 是由各阶段上状态的属性数确定的。9、什么是动态规划问题的维数灾难?动态规划问题的维数即指的是各阶段上状

4、态变量的维数。当状态变量的维数 增加时，动态规划问题的计算量会呈指数倍增长，限制了人们用动态规划研究问 题和解决问题的能力。故，人们把这种情形称为“维数灾难”。*化解动态规划问题的维数灾难，可以利用的思想是什么?人们一般采取了降维的办法，即通过一些特殊技巧或算法把一个高维的动态 规划问题逐步分解为一些低维的动态规划问题，以此来减轻维数灾难。11、什么是状态集?一个阶段上状态可有多种取值情形，各种取值情形的集合被称为该阶段上的 状态集。人们常用符号S表示第k个阶段上的状态集，k= 1,2, 12、什么是（阶段）决策?决策是指依据某个阶段的某种状态，从各种可能的方案中作出选择。精品文档你我共享AA

5、AAAASk可能作出的所有决策行为的集合，k= 1,2,n.13、什么是（阶段）决策变量?决策变量描述了一个阶段上依据某种状态，可能发生的多种决策行为。人们 常用符号Uk （Sk）表示第k个阶段上基于状态Sk作出的决策行为，k= 1,2,n.14、什么是（允许）决策集?一个阶段上依据某种状态，可能发生的多种决策行为的集合被称为（允许）决策集。人们常用符号 a（ Sk）表示第k个阶段上基于状态精品文档你我共享AAAAAA15、什么是状态转移律?当从一个阶段的某个状态出发，在该阶段上作出决策后,其决策后果就直接决定了相邻的下一个阶段上的状态取值，这种状态决定规律,被称为状态转移律。状态转移律可通过

6、状态转移方程予以描述。16、如果以每个阶段的首状态作为每个阶段的状态，那么其状态转移方程是怎样的?其各阶段的状态转移方程为氣1 乞念卫血）m“心*1二无（$以）1 “f近二恥曲侃）.17、如果以每个阶段的末状态作为每个阶段的状态，那么其状态转移方程是怎样的?其各阶段的状态转移方程为I H I Mil1创血儿HW)叫! 士Fg 小IMR*I.-18、动态规划问题具有什么特征?动态规划问题具有如下四个特征。精品文档你我共享AAAAAAa.是各阶段前后关联且呈链状结构的多阶段决策序列;b.C.d.具有边界条件。a.若阶段状态为各阶段的首状态，则图形常可如下画出。第一阶段心b.若阶段状态为各阶段的末状

7、态，则图形常可如下画出。具有无后效性（马尔可夫性），即某个阶段上的状态，只受该阶段相邻的前一个阶段状态的影响，而与以前各阶段状态无关。这个特征决定了动 态规划问题的状态转移规律。策略的指标函数具有可分离性，即策略的指标函数一般是各阶段指标函数的和或积的形式。19、分析一个动态规划问题时，人们常画出其链状结构的多阶段决策示意图,反映阶段划分、状态变量、决策变量以及考察途径，那么这种图形形式是怎样的？鼻卜尸赵冷旳阳H -* 5=L 1（服b 1（5I 严1；（$左皿亦胖比产旳）卡纠旳（打）十 .I第耳阶段屮20、什么是决策的指标函数?决策的指标函数是一个阶段上所作决策产生的效益或成本费用等决策效果

8、 的一种测度。一个阶段上决策的指标函数常用符号,瓜弘临（辺）或Ktfcub弧（3加1）表示。精品文档你我共享AAAAAAa.若阶段状态为各阶段的首状态，则策略常可表示为,b.若阶段状态为各阶段的末状态，则策略常可表示为,a.21、什么是策略?所谓策略指的是在动态规划问题中，从开始阶段的某个状态出发，连贯地在各阶段上作决策所形成的决策序列。一个 n阶段动态规划问题的策略,P 1n(Sl)= Sl, Ul(Sl), S 2, U2(S2),，S n, Un(Sn), Sn+l或Pln( Sl)= Ul(Sl), U2(S2),，Un(Sn) .P n 1 (Sn+1)= S n+1, Un( Sn

9、+1),Sn, Un1( Sn),S2,U1( S2), S1或P n 1 ( Sn+l)= Un( Sn+l),Un-l(Sn),Ul ( S2) .22、什么是策略集?在动态规划问题中，从开始阶段的某个状态出发的所有策略的集合被称为关于这个初始状态的策略集。一个 n阶段动态规划问题的策略集，常可表示为,Pln( Sl) Pln( Sl) 或 Pn1 ( Sn+1) Pn 1 ( Sn+1).23、什么是子策略?所谓子策略指的是在动态规划问题中，从某个阶段的某个状态出发，连贯地在其后各阶段上作决策所形成的决策序列。一个 n阶段动态规划问题,若阶段状态为各阶段的首状态，则后部 k子策略（从第k

10、个阶段的Sk状态出发到第n个阶段为止的序贯决策序列）常可表示为,Pkn( Sk)= Sk,Uk ( Sk), S k+i, U k +i ( S k +i),，S n, Un( Sn),Sn+i或精品文档你我共享AAAAAAPkn(Sk)= Uk ( Sk), U k+1 ( S k+1), ，Un(Sn) .精品文档你我共享AAAAAA若阶段状态为各阶段的末状态，则前部 k子策略（从第k个阶段的Sk+1状态出发到第1个阶段为止的序贯决策序列）常可表示为，b.Pk1( Sk+ 1 )= Sk+1,Uk (Sk + 1),S k,Uk 1(Sk),，S 2,U1(S2),S1或Pk1( Sk+

11、1)= Uk ( Sk+1), U k1 (Sk),，u 1( S2).24、什么是子策略集?在动态规划问题中，从某个阶段的某个状态出发的所有子策略的集合被称为关于这个状态的子策略集。一个 n阶段动态规划问题的子策略集，常可表示为,Pkn( Sk) Rn( Sk)或 Pk1 ( Sk+1) Pk 1 ( Sk+1).25、什么是（子）策略的指标函数?子策略的指标函数是对一个子策略所产生的效益或成本费用等策略效果的一种测度。a.k子策略若阶段状态为各阶段的首状态，一个 n阶段动态规划问题的后部（从第k个阶段的Sk状态出发到第n个阶段为止的序贯决策序列）的指标函数,常可表示为,b.九 =山1円（毗

12、 切旳（辺）”,片（耳）,片+1）.当k=1时,耐帘=%饥呛1）, 32,臥巧5泌為）,如）即为策略的指标函数。若阶段状态为各阶段的末状态，一个 n阶段动态规划问题的前部k子策略（从第k个阶段的Sk +1状态出发到第1个阶段为止的序贯决策序列）的指标函数，常可表示为,精品文档你我共享AAAAAA当k=n时,a.b.吃冷如弧何+1）, % %依），,3屮1（轴星）%1&+1,吗厲+1）,轴咖-1（%）, ，旳1（竝 L 肉）即为策略的指标函数。26、最优（子）策略指标函数的表达式是怎样的?若阶段状态为各阶段的首状态，则最优后部k子策略指标函数的表达式一般写为如下形式,AbJ= opt% （弘收（

13、砧 ijt+b,釘）,3斟 1）当 k=i,/1W=如f% （毎切5）,冷如勺备吟氯）,条+1）即为最优策略指标函数的表达式。若阶段状态为各阶段的末状态，则最优前部k子策略指标函数的表达式一般写为如下形式,A為+】*Qpf叫（3林山%岭-xh.抵出L旳）d）当 k=n,/1 &+1 卜opt厲 J% 吗一仏 hr 西屮屁），51）即为最优策略指标函数的表达式。27、最优性原理是如何表述的?精品文档你我共享AAAAAA作为整个决策过程的最优策略具有这样的性质：即无论前面的状态和决策如 何，对前面的决策所形成的某个阶段的状态而言， 余下的诸决策必须构成最优子 策略。简言之，最优策略的子策略总是最优

14、的。28、如何理解最优性原理?不妨设一个n阶段的动态规划问题的最优策略为Pln*( Sl*)= Sl*, Ul*( Sl*), S2,U2*(S2*),-, Sn*, Un*( Sn*),Sn + 1*,则从最优策略上的任一个阶段状态 Sk*出发，所截取出的后部k子策略Pkn*( Sk*)= Sk*, Uk*( Sk*),Sk+1*,U k+1*( S k+1*),S n*, Un*( Sn*), Sn+1* ,必是从Sk*出发的所有后部k子策略中最优的。或者，当一个n阶段的动态规划问题的最优策略为P n 1*( Sn+1*)=Sn + 1*Un* ( Sn+1*), Sn*,Un-1* (

15、Sn*),S2*,Ul*(S2*),Sl*.则从最优策略上的任一个阶段状态Sk+1*出发，所截取出的前部k子策略Pki*( Sk+i*)= Sk+1*, Uk*( Sk+1*), Sk*,Uk1*( Sk*),，S 2*,Ui*( S2*), Si*,必是从Sk+1*出发的所有前部k子策略中最优的。简言之，最优策略的子策略总是最优的。由此，可以看到，最优性原理是对策略为最优策略时的性质总结。故，最优 性原理不过是最优策略的必要条件而已。29、动态规划有哪两类主要方法?一个是逆推法，一个是顺推法。精品文档你我共享AAAAAA30、动态规划逆推法的数学模型是如何表述的?一般应首先进行阶段的划分和各

16、阶段状态变量、决策变量的认定，以及状态转移方程和状态集、决策集的分析、指标函数的设计，然后用数学的语言写出模 型。逆推法下的模型如下,逆推法状态转移方程:耳=人-1（耳-1心-1）,1 .= Eh沖必.吐=耳（旳山2）递推公式= 陀1卩丄仏叫）人-14-1）=QPf叫-1（片+人（务） 用昭=甲叫（听）+禹1血31、动态规划顺推法的数学模型是如何表述的?一般应首先进行阶段的划分和各阶段状态变量、决策变量的认定，以及状态转移 方程和状态集、决策集的分析、指标函数的设计，然后用数学的语言写出模型。顺推法下的模型如下,顺推法伏态转移方程：诃=邛农卜整），= g（古陌*吐），*.宀丁；（务+叫）递雄公

17、式/oU）=0/iCa）-吋 W*泸耳山）A （另）=卯出（也尼】）+ 71（52）JiieAOl ）AGjt+i） = opf败何+】血）+A（S】叫耳以*L）精品文档你我共享AAAAAAAG+i) = opt际片+1戶J +几“(片)aMd 亦1)32、离散动态规划与连续动态规划有何区别?精品文档你我共享AAAAAAa.写出逆推法下的数学模型。b.按照逆推法递推公式，从后往前逐步推导出从第k个阶段的Sk状态出发到第n个阶段为止的最优后部k子策略，pkn* ( Sk)= Sk, Uk*(Sk), s k+1*,U k+1*( Sk+1*),，S n*, Un* ( Sn*), Sn + 1*

18、, k = n,门一1,.2,1C.利用初始边界条件，从前往后逐步顺定出最优策略中各阶段的状态和决策变量值。36、顺推法求解动态规划问题的一般步骤是怎样的?(逆推法)离散动态规划与连续动态规划的区别主要表现在决策和状态变量是离散还 是连续取值。33、静态规划用动态规划法求解的前提条件是什么?静态规划用动态规划法求解的前提条件是能够进行空间的分离。34、逆推法和顺推法解决问题的对象有何不同?选择逆推法还是顺推法有时会带来求解过程的复杂性不同。为使求解过程尽 可能的简化，可依据一个简单规则做出判断，如果越后的阶段指标函数越复杂, 则选用顺推法；反之，则选用逆推法。如下面的例子中，根据不同特点，分别

19、选择了不同方法。(顺推法)itiax 2 =+弘扌 +2七2可 +42 +3巾 1035、逆推法求解动态规划问题的一般步骤是怎样的?逆推法求解动态规划问题的一般步骤如下,精品文档你我共享AAAAAAa.写出顺推法下的数学模型。b.按照顺推法递推公式，从前往后逐步推导出从第k个阶段的Sk+1状态出发到第1个阶段为止的最优前部k子策略，Pki*(Sk+1)= Sk +1, Uk*( Sk+1),Sk*, Uk1*( Sk*),，s 2*, U1*( S2*), S1*,k=1,2,n.C.利用终端边界条件，从后往前逐步逆定出最优策略中各阶段的状态和决策变量值。37、如何用动态规划方法求解如下的连续

20、静态规划问题?答：此非线性规划问题可按维数进行空间分离，故可用动态规划方法求解。a.动态规划数学模型S3=S4 3x3S2=S3 4x2Si=S2 2xiD 1= xi I 0 xiS2/2 顺推法求解动态规划问题的一般步骤如下,(a)状态转移方程和决策集S 4 10,D3= X3 I 0 X3 S4/3 D2= X2 I 0 X2 0,整数C.逆定精品文档你我共享AAAAAAa.答：逆推法求解过程如下,逆推精品文档你我共享AAAAAA(b)网叫叫辭沁严十恥十勿净点g/2(13+SOXO+34 J3=O为(罚+呂(M+辽 /I(c)b.yy 135+30 x0+E =1(133+75x 0 +

21、30 x 0 +5 = 15Dx 1 +75x 0 +30X 0 +85=235 比=q jqJ (6(? +75x 1 +80 x0 +S5= 150 x0+75x 1 +80 x0+E5=1SQ x尸I,珂=0 , =235b用血1+85#(+75=0+和+8575(W+巧训+勿+85=1勿屯冲=0/3(50)+35x2 -150 x 0+75x0 +30 x0 +5x2-LJQxy-O,x立-Q=0.1顺定综上(a), (b), (c),Xi=3, X2= X3=X4=0,为取优解。rtuax丹(220) +S5xO = 为询 +S5Kb 汎)+S5x 2 =mo150X1 + l-SOx + Q,max150 x1 + 15x +30;? +35,70si 心 403 220-85x1ittax150X1+