动态规划84067Word文件下载.docx
《动态规划84067Word文件下载.docx》由会员分享，可在线阅读，更多相关《动态规划84067Word文件下载.docx（13页珍藏版）》请在冰点文库上搜索。
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、分析一个动态规划问题时，人们常画出其链状结构的多阶段决策示意图，反映阶段划分、状态变量、决策变量以及考察途径，那么这种图形形式是怎样的？
若阶段状态为各阶段的首状态，则图形常可如下画出。
若阶段状态为各阶段的末状态，则图形常可如下画出。
20、什么是决策的指标函数？
决策的指标函数是一个阶段上所作决策产生的效益或成本费用等决策效果的一种测度。
一个阶段上决策的指标函数常用符号，
或
表示。
21、什么是策略？
所谓策略指的是在动态规划问题中，从开始阶段的某个状态出发，连贯地在各阶段上作决策所形成的决策序列。
一个n阶段动态规划问题的策略，
若阶段状态为各阶段的首状态，则策略常可表示为，
p1n（s1）={s1,u1（s1）,s2,u2（s2）,…,sn,un（sn）,sn+1}或
p1n（s1）={u1（s1）,u2（s2）,…,un（sn）}.
若阶段状态为各阶段的末状态，则策略常可表示为，
pn1（sn+1）={sn+1,un（sn+1）,sn,un－1（sn）,…,s2,u1（s2）,s1}或
pn1（sn+1）={un（sn+1）,un－1（sn）,…,u1（s2）}.
22、什么是策略集？
在动态规划问题中，从开始阶段的某个状态出发的所有策略的集合被称为关于这个初始状态的策略集。
一个n阶段动态规划问题的策略集，常可表示为，
p1n（s1）∈P1n（s1）或pn1（sn+1）∈Pn1（sn+1）.
23、什么是子策略？
所谓子策略指的是在动态规划问题中，从某个阶段的某个状态出发，连贯地在其后各阶段上作决策所形成的决策序列。
一个n阶段动态规划问题，
若阶段状态为各阶段的首状态，则后部k—子策略（从第k个阶段的sk状态出发到第n个阶段为止的序贯决策序列）常可表示为，
pkn（sk）={sk,uk（sk）,sk+1,uk+1（sk+1）,…,sn,un（sn）,sn+1}或
pkn（sk）={uk（sk）,uk+1（sk+1）,…,un（sn）}.
若阶段状态为各阶段的末状态，则前部k—子策略（从第k个阶段的sk＋1状态出发到第1个阶段为止的序贯决策序列）常可表示为，
pk1（sk＋1）={sk＋1,uk（sk＋1）,sk,uk－1（sk）,…,s2,u1（s2）,s1}或
pk1（sk＋1）={uk（sk＋1）,uk－1（sk）,…,u1（s2）}.
24、什么是子策略集？
在动态规划问题中，从某个阶段的某个状态出发的所有子策略的集合被称为关于这个状态的子策略集。
一个n阶段动态规划问题的子策略集，常可表示为，
pkn（sk）∈Pkn（sk）或pk1（sk+1）∈Pk1（sk+1）.
25、什么是（子）策略的指标函数？
子策略的指标函数是对一个子策略所产生的效益或成本费用等策略效果的一种测度。
若阶段状态为各阶段的首状态，一个n阶段动态规划问题的后部k—子策略（从第k个阶段的sk状态出发到第n个阶段为止的序贯决策序列）的指标函数，常可表示为，
.
当k=1时，
即为策略的指标函数。
若阶段状态为各阶段的末状态，一个n阶段动态规划问题的前部k—子策略（从第k个阶段的sk＋1状态出发到第1个阶段为止的序贯决策序列）的指标函数，常可表示为，
当k=n时，
26、最优（子）策略指标函数的表达式是怎样的？
若阶段状态为各阶段的首状态，则最优后部k—子策略指标函数的表达式一般写为如下形式，
当k=1,
即为最优策略指标函数的表达式。
若阶段状态为各阶段的末状态，则最优前部k—子策略指标函数的表达式一般写为如下形式，
当k=n,
27、最优性原理是如何表述的？
作为整个决策过程的最优策略具有这样的性质：
即无论前面的状态和决策如何，对前面的决策所形成的某个阶段的状态而言，余下的诸决策必须构成最优子策略。
简言之，最优策略的子策略总是最优的。
28、如何理解最优性原理？
不妨设一个n阶段的动态规划问题的最优策略为
p1n*（s1*）={s1*,u1*（s1*）,s2,u2*（s2*）,…,sn*,un*（sn*）,sn+1*},
则从最优策略上的任一个阶段状态sk*出发，所截取出的后部k—子策略
pkn*（sk*）={sk*,uk*（sk*）,sk+1*,uk+1*（sk+1*）,…,sn*,un*（sn*）,sn+1*},
必是从sk*出发的所有后部k—子策略中最优的。
或者，当一个n阶段的动态规划问题的最优策略为
pn1*（sn+1*）={sn+1*,un*（sn+1*）,sn*,un－1*（sn*）,…,s2*,u1*（s2*）,s1*}.
则从最优策略上的任一个阶段状态sk+1*出发，所截取出的前部k—子策略
pk1*（sk＋1*）={sk＋1*,uk*（sk＋1*）,sk*,uk－1*（sk*）,…,s2*,u1*（s2*）,s1*},
必是从sk+1*出发的所有前部k—子策略中最优的。
简言之，最优策略的子策略总是最优的。
由此，可以看到，最优性原理是对策略为最优策略时的性质总结。
故，最优性原理不过是最优策略的必要条件而已。
29、动态规划有哪两类主要方法？
一个是逆推法，一个是顺推法。
30、动态规划逆推法的数学模型是如何表述的？
一般应首先进行阶段的划分和各阶段状态变量、决策变量的认定，以及状态转移方程和状态集、决策集的分析、指标函数的设计，然后用数学的语言写出模型。
逆推法下的模型如下，
31、动态规划顺推法的数学模型是如何表述的？
顺推法下的模型如下，
32、离散动态规划与连续动态规划有何区别？
离散动态规划与连续动态规划的区别主要表现在决策和状态变量是离散还是连续取值。
33、静态规划用动态规划法求解的前提条件是什么？
静态规划用动态规划法求解的前提条件是能够进行空间的分离。
34、逆推法和顺推法解决问题的对象有何不同？
选择逆推法还是顺推法有时会带来求解过程的复杂性不同。
为使求解过程尽可能的简化，可依据一个简单规则做出判断，如果越后的阶段指标函数越复杂，则选用顺推法；
反之，则选用逆推法。
如下面的例子中，根据不同特点，分别选择了不同方法。
（顺推法）
（逆推法）
35、逆推法求解动态规划问题的一般步骤是怎样的？
逆推法求解动态规划问题的一般步骤如下，
写出逆推法下的数学模型。
按照逆推法递推公式，从后往前逐步推导出从第k个阶段的sk状态出发到第n个阶段为止的最优后部k—子策略，pkn*（sk）={sk,uk*（sk）,sk+1*,uk+1*（sk+1*）,…,sn*,un*（sn*）,sn+1*},k=n,n－1,…,.2,1
利用初始边界条件，从前往后逐步顺定出最优策略中各阶段的状态和决策变量值。
36、顺推法求解动态规划问题的一般步骤是怎样的？
顺推法求解动态规划问题的一般步骤如下，
写出顺推法下的数学模型。
按照顺推法递推公式，从前往后逐步推导出从第k个阶段的sk＋1状态出发到第1个阶段为止的最优前部k—子策略，pk1*（sk＋1）={sk＋1,uk*（sk＋1）,sk*,uk－1*（sk*）,…,s2*,u1*（s2*）,s1*},k=1,2,…,n.
利用终端边界条件，从后往前逐步逆定出最优策略中各阶段的状态和决策变量值。
37、如何用动态规划方法求解如下的连续静态规划问题？
答：
此非线性规划问题可按维数进行空间分离，故可用动态规划方法求解。
动态规划数学模型
（a）状态转移方程和决策集
s4≤10,
s3=s4－3x3D3=｛x3∣0≤x3≤s4/3｝
s2=s3－4x2D2=｛x2∣0≤x2≤s3/4｝
s1=s2－2x1D1=｛x1∣0≤x1≤s2/2｝
（b）递推公式：
顺推过程
逆定
38、*如何用动态规划方法求解如下的离散静态规划问题？
max150x1+75x2+80x3+85x4
70x1+75x2+80x3+85x4≤220
x1,x2,x3,x4≥0,整数
逆推法求解过程如下，
逆推
（a）
a
b
c
（b）
（c）
顺定
综上（a）,（b）,（c）,x1=3,x2=x3=x4=0,为最优解。
出师表
两汉：
诸葛亮
先帝创业未半而中道崩殂，今天下三分，益州疲弊，此诚危急存亡之秋也。
然侍卫之臣不懈于内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。
诚宜开张圣听，以光先帝遗德，恢弘志士之气，不宜妄自菲薄，引喻失义，以塞忠谏之路也。
宫中府中，俱为一体；
陟罚臧否，不宜异同。
若有作奸犯科及为忠善者，宜付有司论其刑赏，以昭陛下平明之理；
不宜偏私，使内外异法也。
侍中、侍郎郭攸之、费祎、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗陛下：
愚以为宫中之事，事无大小，悉以咨之，然后施行，必能裨补阙漏，有所广益。
将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰“能”，是以众议举宠为督：
愚以为营中之事，悉以咨之，必能使行阵和睦，优劣得所。
亲贤臣，远小人，此先汉所以兴隆也；
亲小人，远贤臣，此后汉所以倾颓也。
先帝在时，每与臣论此事，未尝不叹息痛恨于桓、灵也。
侍中、尚书、长史、参军，此悉贞良死节之臣，愿陛下亲之、信之，则汉室之隆，可计日而待也。
臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。
先帝不以臣卑鄙，猥自枉屈，三顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。
后值倾覆，受任于败军之际，奉命于危难之间，尔来二十有一年矣。
先帝知臣谨慎，故临崩寄臣以大事也。
受命以来，夙夜忧叹，恐托付不效，以伤先帝之明；
故五月渡泸，深入不毛。
今南方已定，兵甲已足，当奖率三军，北定中原，庶竭驽钝，攘除奸凶，兴复汉室，还于旧都。
此臣所以报先帝而忠陛下之职分也。
至于斟酌损益，进尽忠言，则攸之、祎、允之任也。
愿陛下托臣以讨贼兴复之效，不效，则治臣之罪，以告先帝之灵。
若无兴德之言，则责攸之、祎、允等之慢，以彰其咎；
陛下亦宜自谋，以咨诹善道，察纳雅言，深追先帝遗诏。
臣不胜受恩感激。
今当远离，临表涕零，不知所言。
升级会员 