动态规划习题概要.doc

动向规划习题纲要第七章动向规划规划问题的最后目的就是确立各决议变量的取值，以使目标函数达到极大或极小性规划和非线性规划中，决议变量都是以会合的形式被一次性办理的；但是，有时我们也会面对决议变量需分期、分批办理的多阶段决议问题所谓多阶段决议问题是指这样一类活动过程：它能够分解为若干个相互联系的阶段，在每一阶段分别对应着一组可供选用的决议集合；即构成过程的每个阶段都需要进行一次决议的决议问题将各个阶段的决议综合起来构成一个决议序列，称为一个策略明显，因为各个阶段选用的决议不一样，对应整个过程能够有一系列不一样的策略当过程采纳某个详细策略时，相应能够获取一个确立的成效，采纳不同的策略，就会获取不一样的成效多阶段的决议问题，就是要在所有可能采纳的策略中选用一个最优的策略，以便获取最正确的成效动向规划（dynamicprogramming）同前面介绍过的各样优化方法不一样，它不是一种算法，而是观察问题的一种门路动向规划是一种求解多阶段决议问题的系统技术，能够说它横跨整个规划领域（线性规划和非线性规划）自然，因为动向规划不是一种特定的算法，因此它不象线性规划那样有一个标准的数学表达式和明确立义的一组规则，动向规划一定对详细问题进行详细的剖析办理。

在多阶段决议问题中，有些问题对阶段的区分拥有明显的时序性，动向规划的“动向”二字也由此而得名动向规划的主要首创人是美国数学家贝尔曼（Bellman）20世纪40年月末50年月初，当时在兰德企业（RandCorporation）从事研究工作的贝尔曼第一提出了动向规划的看法1957年贝尔曼发布了数篇研究论文，并第一版了他的第一部著作《动向规划》该著作成为了当时独一的进一步研究和应用动向规划的理论源泉1961年贝尔曼第一版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作第一版了第三部著作在贝尔曼及其助手们致力于发展和推行这一技术的同时，其余一些学者也对动向规划的发展做出了重要的贡献，此中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）爱尔思先后于1961年和1964年第一版了两部对于动向规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创立了办理分枝、循环性多阶段决议系统的一般性理论梅特顿提出了很多对动向规划此后发展有侧重要意义的基础性看法，而且对清晰动向规划路径的数学性质做出了巨大的贡献动向规划在工程技术、经济管理等社会各个领域都有着宽泛的应用，而且获取了明显的成效。

在经济管理方面，动向规划能够用来解决最优路径问题、资源分派问题、生产调动问题、库存管理问题、排序问题、设施更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决议技术很多规划问题用动向规划的方法来办理，常比线性规划或非线性规划更有效特别是对于失散的问题，因为分析数学没法发挥作用，动向规划便成为了一种特别实用的工具动向规划能够依照决议过程的演变能否确立分为确立性动向规划和随机性动向规划；也能够依照决议变量的取值能否连续分为连续性动向规划和失散性动向规划本教材主要介绍动向规划的基本看法、理论和方法，并经过典型的事例说明这些理论和方法的应用§7.1 动向规划的基本理论1.1多阶段决议过程的数学描绘有这样一类活动过程， 其整个过程可分为若干相互联系的阶段， 每一阶段都要作出相应的决议，以使整个过程达到最正确的活动成效任何一个阶段（ stage，即决议点）都是由输/入（input）、决议（decision）、状态转移律（transformation构成的，如图7-1（a）所示此中输入和输出也称为状态（function）和输出（outputstate），输入称为输入状态，）输出称为输出状态。

决 策 dn输入输出SnSn+1阶段Stagen状态转移gn=r(Sn,dn)（a）（b）图7-1因为每一阶段都有一个决议，所以每一阶段都应存在一个权衡决议效益大小的指标函数，这一指标函数称为阶段指标函数，用gn表示明显gn是状态变量Sn和决议变量dn的函数，即gn=r（Sn，dn），如图7-1（b）所示明显，输出是输入和决议的函数，即：Sn1f(Sn,dn)（7-1）式（7-1）即为状态转移律在由N个阶段构成的过程里，前一个阶段的输出即为后一个阶段的输入1.2动向规划的基本看法动向规划的数学描绘离不开它的一些基本看法与符号，所以有必需在介绍多阶段决议过程的数学描绘的基础上，系统地介绍动向规划的一些基本看法1．阶段（stage）阶段是过程中需要做出决议的决议点描绘阶段的变量称为阶段变量，常用k来表示阶段的区分一般是依据时间和空间的自然特点来进行的，但要便于将问题的过程转变为多阶段决议的过程对于拥有个阶段的决议过程，其阶段变量k＝1，2，，NN2．状态（state）状态表示每个阶段开始所处的自然状况或客观条件，它描绘了研究问题过程的状况状态既反应前面各阶段系列决议的结局，又是本阶段决议的一个出发点和依照；它是各阶段信息的传达点和联合点。

各阶段的状态往常用状态变量Sk来加以描绘作为状态应拥有这样的性质：假如某阶段状态给定后，则该阶段此后过程的发展不受此阶段从前各阶段状态的影响换句话说，过程的历史只好经过目前的状态来影响将来，目前的状态是过去历史的一个总结这个性质称为无后效性（thefutureisindependentofthepast）或健忘性（theprocessisforgetful）3．决议（decision）决议是指决议者在所面对的若干个方案中做出的选择决议变量dk表示第k阶段的决策决议变量dk的取值会遇到状态Sk的某种限制，用Dk（Sk）表示第k阶段状态为Sk时决策变量同意的取值范围，称为同意决议会合，因此有dk（Sk）Dk（Sk）4．状态转移律（transformationfunction）状态转移律是确立由一个状态到另一状态演变过程的方程，这种演变的对应关系记为Sk+1= Tk（Sk, dk）5．策略（policy）与子策略（sub-policy ）由所有阶段决议所构成的一个决议序列称为一个策略，拥有 N个阶段的动向规划问题的策略可表示为：{d1(S1),d2(S2), ,dN(SN)}从某一阶段开始到过程终点为止的一个决议子序列， 称为过程子策略或子策略。

从第k个阶段起的一个子策略可表示为：{dk(Sk),dk1(Sk1), ,dN(SN)}6．指标函数指标函数有阶段指标函数 和过程指标函数 之分阶段指标函数是对应某一阶段决议的效率胸怀，用 gk=r（Sk，dk）来表示；过程指标函数是用来权衡所实现过程好坏的数目指标，是定义在全过程（策略）或后续子过程（子策略）上的一个数目函数，从第 k个阶段起的一个子策略所对应的过程指标函数常用 Gk,N来表示，即：Gk,N R(Sk,dk,Sk1,dk1, ,SN,dN)构成动向规划的过程指标函数，应拥有可分性并知足递推关系；即：Gk,NgkGk1,N这里的表示某种运算，最常有的运算关系有以下二种：（1）过程指标函数是其所包含的各阶段指标函数的“和”，即：NGk,Ngjjk于是Gk,NgkGk1,N（2）过程指标函数是其所包含的各阶段指标函数的“积”，即：NGk,Ngjjk于是Gk,NgkGk1,N7．最优指标函数从第k个阶段起的 最优子策略 所对应的过程指标函数称为最优指标函数，能够用式（7-2）加以表示：fk(Sk) opt{gk gk1 gN} （7-2）d k~N此中“opt”是最优化“optimization”的缩写，可依据题意取最大“max”或最小“min”。

在不一样的问题中，指标函数的含义可能是不一样的，它可能是距离、利润、成本、产量或资源量等1.3动向规划的数学模型动向规划的数学模型除包含式（7-2）外，还包含阶段的区分、各阶段的状态变量和决议变量的选用、同意决议会合和状态转移律确实定等如何获取最优指标函数呢？一个 N阶段的决议过程，拥有以下一些特征：（1）恰好有N个决议点；（2）对阶段k而言，除了其所处的状态Sk和所选择的决议dk外，再没有任何其余要素影响决议的最优性了；（3）阶段k仅影响阶段k1的决议，这一影响是经过Sk1来实现的；（4）贝尔曼（Bellman）最优化原理：在最优策略的随意一阶段上，不论过去的状态和决议如何，对过去决议所形成的目前状态而言，余下的诸决议一定构成最优子策略依据贝尔曼（Bellman）最优化原理，能够将式（7-2）表示为递推最优指标函数关系式（ 7-3）或式（7-4）：fk(Sk)opt{gkgk1gN}opt{gkfk1(Sk1)}（7-3）dk~Ndkfk(Sk)opt{gkgk1gN}opt{gkfk1(Sk1)}（7-4）dk~Ndk利用式（7-3）和式（7-4）可表示出最后一个阶段（第N个阶段，即k=N）的最优指标函数：fN(SN)opt{gNfN1(SN1)}（7-5）dNfN(SN)opt{gNfN1(SN1)}（7-6）dN此中fN1(SN1)称为界限条件。

一般状况下，第N阶段的输出状态SN1已经不再影响本过程的策略，即式（7-5）中的界限条件fN1(SN1)0，式（7-6）中的界限条件fN1(SN1)1；。