动态规划算法原理与的应用_.docx

《动态规划算法原理与的应用_.docx》由会员分享，可在线阅读，更多相关《动态规划算法原理与的应用_.docx（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划算法原理与的应用_动态规划算法原理与的应用动态规划算法原理与的应用动态规划算法原理及其应用研究系别：xxx姓名：xxx指导教员：xxx2021年5月20日动态规划算法原理与的应用动态规划算法原理与的应用摘要：动态规划是解决最优化问题的基本方法，本文介绍了动态规划的基本思想和基本步骤，并通过几个实例的分析，研究了利用动态规划设计算法的详细途径。关键词：动态规划多阶段决策1.引言规划问题的最终目的就是确定各决策变量的取值，以使目的函数到达极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决

2、策问题是指这样一类活动经过：它能够分解为若干个相互联络的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成经过的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个经过能够有一系列不同的策略。当经过采取某个详细策略时，相应能够得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划是一种求解多阶段决策问题的系统技术，能够讲它横跨整个规划领域线性规划和非线性规划。在多阶段决策问题中，有些问题对阶段的划分具有明显的时

3、序性，动态规划的“动态二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼Bellman。20世纪40年代末50年代初，当时在兰德公司RandCorporation从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作（动态规划）。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的奉献，其中最值得一提的是爱尔思Aris和梅特顿Mitten。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔Nemhaus

4、er、威尔德Wild一道创立了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了很多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划途径的数学性质做出了宏大的奉献。动态规划问世以来，在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划能够用来解决最优途径动态规划算法原理与的应用动态规划算法原理与的应用问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产经过最优控制问题等，是经济管理中一种重要的决策技术。很多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。十分是对于离散的问题，由于解析数学

5、无法发挥作用，动态规划便成为了一种非常有用的工具。动态规划能够根据决策经过的演变能否确定分为确定性动态规划和随机性动态规划；可以以根据决策变量的取值能否连续分为连续性动态规划和离散性动态规划。固然动态规划主要用于求解以时间划分阶段的动态经过的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策经过，可以以用动态规划方法方便地求解。2.动态规划的基本思想一般来讲，只要问题能够划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解，则能够考虑用动态规划解决。动态规划的本质是分治思想和解决冗余，因而，动态规划是一种将问题实例分解为更小

6、的、类似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、类似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依靠已经作出的所有选择，但不依靠于有待于做出的选择和子问题。因而贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的(即不包含公共的子子问题)，因而一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但缺乏的是，假如当前选择可能要依靠子问题的解时，则难以通过局部的贪心策略到达全局最优解；假如各子问题是不独立的，则分治法要做很

7、多不必要的工作，重复地解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解经过中，该方法也是通过求解局部子问题的解到达全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，也允许其通过本身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。因而，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树动态规划算法原理与的应用动态规划算法原理与的应用中的子问题呈现大量

8、的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次碰到时加以求解，并把答案保存起来，让以后再碰到时直接引用，不必重新求解。3.动态规划的基本概念动态规划的数学描绘离不开它的一些基本概念与符号，因而有必要在介绍多阶段决策经过的数学描绘的基础上，系统地介绍动态规划的一些基本概念。3.1多阶段决策问题假如一类活动经过能够分为若干个相互联络的阶段，在每一个阶段都需作出决策，一个阶段的决策确定以后，经常影响到下一个阶段的决策，进而就完全确定了一个经过的活动道路，则称它为多阶段决策问题。各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因此就有很多策略供我们选取

9、，对应于一个策略能够确定活动的效果，这个效果能够用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在能够选择的那些策略中间，选取一个最优策略，使在预定的标准下到达最好的效果.3.2动态规划问题中的术语阶段：把所给求解问题的经过恰当地分成若干个互相联络的阶段，以便于求解，经过不同，阶段数就可能不同描绘阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。假如经过能够在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。状态：状态表示每个阶段开场面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因

10、素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。经过的状态通常能够用一个或一组数来描绘，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态能够有多个分量(多维情形)，因此用向量来代表；而且在每个阶段的状态维数能够不同。动态规划算法原理与的应用动态规划算法原理与的应用无后效性：我们要求状态具有下面的性质：假如给定某一阶段的状态，则在这一阶段以后经过的发展不受这阶段以前各段状态的影响，所有各阶段都确定时

11、，整个经过也就确定了。换句话讲，经过的每一次实现能够用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开场，当这段的始点给定时，不受以前线路所通过的点的影响。状态的这个性质意味着经过的历史只能通过当前的状态去影响它的将来的发展，这个性质称为无后效性。决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择行动称为决策。在最优控制中，也称为控制。在很多间题中，决策能够自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描绘决策的变量称决策变量，因状态知足无后效性，故在每个阶段选择决策时只需考虑当前的状

12、态而无须考虑经过的历史。决策变量的范围称为允许决策集合。策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策经过，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中到达最优效果的策略称为最优策略。给定k阶段状态变量x(k)的值后，假如这一阶段的决策变量一经确定，第k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么能够把这一关系看成(x(k)，u(k)与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k)表示。这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程。最优性原

13、理:作为整个经过的最优策略，它知足：相对前面决策所构成的状态而言，余下的子策略必然构成“最优子策略。4.动态规划求解的基本步骤动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开场，通过对中间阶段决策的选择，到达结束状态。这些决策构成了一个决策序列，同时确定了完成整个经过的一条活动道路(通常是求最优的活动道路)。如下图。动态规划的设计都有着一定的形式，一般要经历下面几个步骤。初始状态决策决策决策结束状态动态规划算法原理与的应用动态规划算法原理与的应用动态规划决策经过示意图(1)划分阶段：，根据问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可

14、排序的，否则问题就无法求解。(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要知足无后效性。(3)确定决策并写出状态转移方程：由于决策和状态转移有着天然的联络，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以假如确定了决策，状态转移方程也就可写出。但事实上经常是反过来做，根据相邻两段各状态之间的关系来确定决策。(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。(5)程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据上述动态规划设计的步骤，可得到大体解

15、题框架如下图。动态规划设计的一般形式图上述提供了动态规划方法的一般形式，对于简单的动态规划问题，能够按部动态规划算法原理与的应用动态规划算法原理与的应用就班地进行动态规划的设计。下面，给出一个利用动态规划方法求解的典型例子。上图示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。任务一：假设三角形行数10，键盘输入一个确定的整数值M，编程确定能否存在一条途径，使得沿着该途径所经过的数字的总和恰为M，若存在则给出所有途径，若不存在，则输出“NOAnswer!字样。任务二：假设三角形行数100，编程求解从最顶层走到最底层的

16、一条途径，使得沿着该途径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，任务一中文件第一行是三角形的行数N和整数值M。以后的N行分别是从最顶层到最底层的每一层中的数字。任务二中文件数据格式同任务一，只是第一行中没有整数值M。在例子中任务二的文件数据表示如下：输入：57输出：输出途径和最大值387或“NoAnswer!字样。810382774810452652744图3数字三角形45265【分析】对于这一问题，很容易想到用枚举的方法去解决，即列举出所有途径并记录每一条途径所经过的数字总和。然后判定数字总和能否等于给定的整数值M或寻找出最大的数字总和，这一想法很直观，而且对于任务一，

17、由于数字三角形的行数不大(动态规划算法原理与的应用动态规划算法原理与的应用对于任务一，合理地确认枚举的方法，能够优化问题的解法。由于从塔顶到底层每次都只要两种走法，即左或右。设“0表示左，“1表示右，对于层数为N的数字塔，从顶到底的一种走法可用一个N-1位的二进制数表示。如例中二进制数字串1011，其对应的途径应该是：8146。这样就能够用一个Nl位的二进制数来模拟走法和确定解的范围。穷举出从0到2n-1个十进制数所对应的N-1位二进制串对应的途径中的数字总和，断定其能否等于M而求得问题的解。对于任务二，采用动态规划中的顺推解法。按三角形的行划分阶段，若行数为n，则可把问题看做一个n-1个阶段

18、的决策问题。从始点出发，依顺向求出第一阶段、第二阶段第n1阶段中各决策点至始点的最佳途径，最终求出始点到终点的最佳途径。设：fk(Uk)为从第k阶段中的点Uk至三角形顶点有一条最佳途径，该途径所经过的数字的总和最大，fk(Uk)表示为这个数字和；由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因而设：Uk1为k-1阶段中某点Uk沿左斜线向下的点；Uk2为k-1阶段中某点Uk沿右斜线向下的点；dk(Uk1)为k阶段中Uk1的数字；dk(Uk2)为k阶段中Uk2的数字。因此可写出顺推关系式(状态转移方程)为：fk(Uk)=maxfk-1(Uk)+dk(Uk1)，fk-1(Uk)+dk(U

19、k2)(k=1，2，3，n)f0(U0)0经过一次顺推，便可分别求出由顶至底N个数的N条途径，在这N条途径所经过的N个数字和中，最大值即为正确答案。5.动态规划的应用实例5.1最短道路问题例1美国黑金石油公司TheBlackGoldPetroleumCompany近期在阿拉斯加Alaska的北斯洛波NorthSlope发现了大的石油储量。为了大规模开发这一油田，首先必须建立相应的输运网络，使北斯洛波生产的原油能运至美国的3个装运港之一。在油田的集输站结点C与装运港结点P1、P2、P3之间需要若干个中间站，中间站之间的联通情况如图7-2所示，图中线段上的数字代动态规划算法原理与的应用动态规划算法

20、原理与的应用表两站之间的距离单位：10千米。试确定一最佳的输运线路，使原油的输送距离最短。解：最短道路有一个重要性质，即假如由起点A经过B点和C点到达终点D是一条最短道路，则由B点经C点到达终点D一定是B到D的最短路贝尔曼最优化原理。此性质用反证法很容易证实，由于假如不是这样，则从B点到D点有另一条距离更短的道路存在，不妨假设为BPD；进而可知道路ABPD比原道路ABCD距离短，这与原道路ABCD是最短道路相矛盾，性质得证。根据最短道路的这一性质，寻找最短道路的方法就是从最后阶段开场，由后向前逐步递推求出各点到终点的最短道路，最后求得由始点到终点的最短路；即动态规划的方法是从终点逐段向始点方向

21、寻找最短道路的一种方法。根据动态规划的方法，将此经过划分为4个阶段，即阶段变量1,2,3,4k；取经过在各阶段所处的位置为状态变量S，按逆序算法求解。k动态规划算法原理与的应用动态规划算法原理与的应用当4=k时：由结点M31到达目的地有两条道路能够选择，即选择P1或P2；故：668min)(3144=?=MSf选择P2,由结点M32到达目的地有三条道路能够选择，即选择P1、P2或P3；故：3734min)(3244=?=MSf选择P2,由结点M33到达目的地也有三条道路能够选择，即选择P1、P2或P3；故：5567min)(3344=?=MSf选择P3,由结点M34到达目的地有两条道路能够选择

22、，即选择P2或P3；故：343min)(3444=?=MSf选择P2当3k=时：由结点M21到达下一阶段有三条道路能够选择，即选择M31、M32或M33；故：105637610min)(2133=?+=MSf选择M32由结点M22到达下一阶段也有三条道路能够选择，即选择M31、M32或M33；故：10553769min)(2233=?+=MSf选择M32或M33，由结点M23到达下一阶段也有三条道路能够选择，即选择M32、M33或M34；故：93654311min)(2333=?+=MSf选择M33或M34当2k=时：由结点M11到达下一阶段有两条道路能够选择，即选择M21或M22；故：161

23、06108min)(1122=?+=MSf选择M22,由结点M12，到达下一阶段也有两条道路能够选择，即选择M22或动态规划算法原理与的应用动态规划算法原理与的应用M23；故：19911109min)(1222=?+=MSf选择M22，当1k=时：由结点C到达下一阶段有两条道路能够选择，即选择M11或M12；故：2819101612min)(11=?+=CSf选择M11,，而通过顺序计算的反顺序追踪黑体标示能够得到两条最佳的输运线路：CM11M22M32P2；CM11M22M33P3。最短的输送距离是280千米。5.2资源分配问题所谓资源分配问题，就是将一定数量的一种或若干种资源如原材料、机器

24、设备、资金、劳动力等恰当地分配给若干个使用者，以使资源得到最有效地利用。设有m种资源，总量分别为bii=1,2,?,m，用于生产n种产品，若用xij代表用于生产第j种产品的第i种资源的数量j=1,2,?,n，则生产第j种产品的收益是其所获得的各种资源数量的函数，即gj=fx1j,x2j,?,xmj。由于总收益是n种产品收益的和，此问题可用如下静态模型加以描绘：=njjgz1max1nijijxb=(1,2,)im=0ijx(1,2,;1,2,imjn=若ijx是连续变量，当jg=f1jx,2jx,?,mjx是线性函数时，该模型是线性规划模型；当jg=f1jx,2jx,?,mjx是非线性函数时，

25、该模型是非线性规划模型。若ijx是离散变量或和jg=f1jx,2jx,?,mjx是离散函数时，此模型用线性规划或非线性规划来求解都将是非常费事的。然而在此情况下，由于这类问题的特殊构造，能够将它看成为一个多阶段决策问题，并利用动态规划的递推关系来求解。本例只考虑一维资源的分配问题，设状态变量ks表示分配于从第k个阶段至经过最终第N个阶段的资源数量，即第k个阶段初资源的拥有量；决策变量xk表示第k个阶段资源的分配量。于是有状态转移律：kkkxSS-=+1动态规划算法原理与的应用动态规划算法原理与的应用允许决策集合：0|)(kkkkkSxxSD=最优指标函数动态规划的逆序递推关系式：110()ma

26、x()()kkkkkkkkxSfSgxfS+=+(,1,2,1kNNN=-0)(11=+NNSf利用这一递推关系式，最后求得的11()fS即为所求问题的最大总收益，下面来看一个详细的例子。例2某公司拟将500万元的资本投入所属的甲、乙、丙三个工厂进行技术改造，各工厂获得投资后年利润将有相应的增长，增长额如表7-1所示。试确定500万元资本的分配方案，以使公司总的年利润增长额最大。解：将问题按工厂分为三个阶段k=1，2，3，设状态变量kS1,2,3k=代表从第k个工厂到第3个工厂的投资额，决策变量kx代表第k个工厂的投资额。于是有状态转移率1kkkSSx+=-、允许决策集合()|0kkkkkDS

27、xxS=和递推关系式：10()max()()kkkkkkkkkxSfSgxfSx+=+-(3,2,1k=0)(44=Sf当3=k时：)(max0)(max)(330330333333xgxgSfSxSx=+=动态规划算法原理与的应用动态规划算法原理与的应用于是有表7-2，表中3x*表示第三个阶段的最优决策。当2=k时：2222223220()max()()xSfSgxfSx=+-。于是有表7-3。当1=k时：)()(max)(1121101111xSfxgSfSx-+=动态规划算法原理与的应用动态规划算法原理与的应用然后按计算表格的顺序反推算，可知最优分配方案有两个：1甲工厂投资200万元，乙

28、工厂投资200万元，丙工厂投资100万元；2甲工厂没有投资，乙工厂投资200万元，丙工厂投资300万元。按最优分配方案分配投资资源，年利润将增长210万元。5.3用动态规划求解非线性规划问题非线性规划问题的求解是非常困难的；然而，对于有些非线性规划问题，假如转化为用动态规划来求解将是特别方便的。 例3用动态规划求解3221maxxxxz?=36321=+xxx0,321xxx解：阶段：将问题的变量数作为阶段，即k=1，2，3；决策变量：决策变量kx；状态变量：状态变量kS代表第k阶段的约束右端项，即从kx到3x占有的份额；状态转移律：1kkkSSx+=-；边界条件：136S=，44()1fS=

29、；允许决策集合：0kkxS当3=k时：333333|max)(max)(330443033SxSxSxSxSfxSf=*=?=当2=k时：)(max)(max)(2222033220222222xSxSfxSfSxSx-=?=设2222()hxSx=-，2222222()dhdxxSxx=-0)(2222222=-=xxSxdxdh02=x2S又因x，所以：动态规划算法原理与的应用动态规划算法原理与的应用222202|20dhxdxS=，02=x是)(22Sf的极小值点2222222222()2226dhdxSxxxSx=-=-，2223xS=是22()fS的极大值点于是：222|)(3242

30、2SxSSf=*=当1=k时：)(max)(max)(311274102210111111xSxSfxSfSxSx-?=?=同上可得：946414164111111|2624436)36(=*=?=SxSSf由27936112=-=-=*xSS，有1827322322=?=*Sx由32227189SSx*=-=-=，有339xS*=于是得到最优解(9,18,9)X*=，最优值26244=*z。6.结束语从以上实例分析能够看出，用动态规划解决多阶段决策问题效率是很高的,而且思路明晰简便,同时易于实现，固然使用动态规划方法也有一定的限制，如状态变量必须知足无后效性，并且只适用一些维数相当低的问题等。但是，能够看到，动态规划方法的应用是很广的，已成功解决了很多实际问题，具有很强的实用性。动态规划算法原理与的应用动态规划算法原理与的应用参考文献1徐渝,贾涛.运筹学M.北京:清华大学出版社,2005.2韦兰用.最优控制问题研究综述D.吉林大学，2006.3谬慧芬,邵小兵.动态规划算法的原理及应用J.中国科技信息,2005(21).4解可新,韩立兴,林友联.最优化方法M.天津:天津大学出版社,1997.5赵旋.变分法、最小值原理、动态规划和最优控制J.自动化博览，1997