文档介绍：第七章动态规划常见疑问解答
1、动态规划是怎样产生的?
1951年,R . Bellman 等人,根据某类多阶段序贯决策问题的特点,提出了著名的“最优性原理”。在这个原理的指导下,他将此类多阶段决策问题转变为一系列的互相联系的单阶段决策问题,然后,逐个阶段予以解决,最后再形成总体解决。从而创建了求解优化问题的新方法——动态规划。1957年,他的名著《动态规划》出版。
2、动态规划的基本概念有哪些?
阶段、(阶段)状态、状态变量si、状态集Si、决策、决策变量ui(si)、决策集Di(si)、状态转移方程、决策的指标函数、策略的指标函数、最优值函数等。
3、什么是阶段?
动态规划的阶段指的是决策发生的时间或空间区隔。
4、如何划分动态规划问题的阶段?
动态规划问题的阶段划分一般可依据决策发生的次数和每次决策发生并作用的时间段或空间段来定。
5、什么是(阶段)状态?
状态既可以指一个阶段上作决策时所依据的自然状况和客观条件,又可以指一个阶段上所作决策后的结局状况,故一个阶段的状态常有首、末状态之分,以区别阶段上决策的出发点和结局状况。但,一般地,人们往往仅选择各阶段的首、末状态之一,作为各阶段的状态,所以,当谈到各阶段的状态时,要么都指的是各阶段的首状态,要么都指的是各阶段的末状态。
6、什么是(阶段)状态变量?
状态变量是对一个阶段上状态(多种)取值情形的描述。人们常用符号sk 表示第k个阶段上的状态变量,k= 1, 2, …, n.
7、什么是动态规划问题的维数?
动态规划问题的维数即指的是各阶段上状态变量的维数。
8、各阶段上状态变量的维数是如何确定的?
动态规划问题各阶段上的状态常常可能需要用几个属性才能描述清楚。如各个阶段上都要依据资源状态作出生产数量决策时,若生产资源有3种类型,则资源状态就必须用三种类型的资源,即三个属性来共同描述。相应地,资源状态变量就必须用三维向量表示各类资源的取值情形。因此,各阶段上状态变量的维数是由各阶段上状态的属性数确定的。
9、什么是动态规划问题的维数灾难?
动态规划问题的维数即指的是各阶段上状态变量的维数。当状态变量的维数增加时,动态规划问题的计算量会呈指数倍增长,限制了人们用动态规划研究问题和解决问题的能力。故,人们把这种情形称为“维数灾难”。
10、* 化解动态规划问题的维数灾难,可以利用的思想是什么?
人们一般采取了降维的办法,即通过一些特殊技巧或算法把一个高维的动态规划问题逐步分解为一些低维的动态规划问题,以此来减轻维数灾难。
11、什么是状态集?
一个阶段上状态可有多种取值情形,各种取值情形的集合被称为该阶段上的状态集。人们常用符号Sk 表示第k个阶段上的状态集,k= 1, 2, …, n.
12、什么是(阶段)决策?
决策是指依据某个阶段的某种状态,从各种可能的方案中作出选择。
13、什么是(阶段)决策变量?
决策变量描述了一个阶段上依据某种状态,可能发生的多种决策行为。人们常用符号uk (sk) 表示第k个阶段上基于状态sk 作出的决策行为,k= 1, 2, …, n.
14、什么是(允许)决策集?
一个阶段上依据某种状态,可能发生的多种决策行为的集合被称为(允许)决策集。人们常用符号Dk (sk) 表示第k个阶段上基于状态sk 可能作出的所有决策行为的集合,k= 1, 2, …, n.
15、什么是状态转移律?
当从一个阶段的某个状态出发,在该阶段上作出决策后,其决策后果就直接决定了相邻的下一个阶段上的状态取值,这种状态决定规律,被称为状态转移律。状态转移律可通过状态转移方程予以描述。
16、如果以每个阶段的首状态作为每个阶段的状态,那么其状态转移方程是怎样的?
其各阶段的状态转移方程为
.
17、如果以每个阶段的末状态作为每个阶段的状态,那么其状态转移方程是怎样的?
其各阶段的状态转移方程为
.
18、动态规划问题具有什么特征?
动态规划问题具有如下四个特征。
a.       是各阶段前后关联且呈链状结构的多阶段决策序列;
b.       具有无后效性(马尔可夫性),即某个阶段上的状态,只受该阶段相邻的前一个阶段状态的影响,而与以前各阶段状态无关。这个特征决定了动态规划问题的状态转移规律。
c.       策略的指标函数具有可分离性,即策略的指标函数一般是各阶段指标函数的和或积的形式。
d.       具有边界条件。
19、分析一个动态规划问题时,人们常画出其链状结构的多阶段决策示意图,反映阶段划分、状态变量、决策变量以及考察途径,那么这种图形形式是怎样的?
a.       若阶段状态为各阶段的首状态,则图形常可如下画出。
b.       若阶段状