《动态规划法求解生产及存储问题》由会员分享，可在线阅读，更多相关《动态规划法求解生产及存储问题（21页珍藏版）》请在金锄头文库上搜索。
1、文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.动态规划一动态规划法的发展及其研究内容动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。 20 世纪 50 年代初美国数学家，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解创立了解决这类过程优化问题的新方法动态规划。 1957 年出版的他的名著 Dynamic Proggramming ，这是该领域的第一本著作。动态规划问世以来，在经济管理生产调度工程技术和最优控制等方面得到了广泛的应用。例如最短路线库存管理资源分配设备更新组合排序装载等问题，采用动态规划法求解比用其他方法更为简便。二动态规划
2、法基本概念一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素：1阶段阶段（ stage）是对整个过程的自然划分。通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。阶段变量一般用k=1.2.n.表示。文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.1. 状态状态 (state)是我们所研究的问题（也叫系统）在过个阶段的初始状态或客观条件。它应能描述过程的特征并且具有无后效性， 即当某阶段的状态给定时，这个阶段以后的过程的演变与该阶段以前各阶段的状
3、态无关。 通常还要求状态是可以直接或者是间接可以观测的。 描述状态的变量称为状态变量（ State Virable ）用 s 表示，状态变量的取值集合称为状态集合， 用 S 表示。变量允许取值的范围称为允许状态集合 (set of admissble states).用 x(k) 表示第k 阶段的状态变量，它可以是一个数或者是一个向量。用n 个阶段的决策过程有 n+1 个状态变量， x(n+1) 是 x(n)的演变的结果。根据演变过程的具体情况，状态变量可以是离散的或是连续的。 为了计算方便有时将连续变量离散化，为了分析的方便有时又将离散的变量视为连续的。2决策当一个阶段的状态确定后，可以做出
4、各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision ），在最优控制问题中也称为控制（control ）描述决策的变量称为决策变量（decisionvirable ）。变量允许取值的范围称为允许决策集合（set of admissble文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.decisions）。用表示第策变量， 它是 x(k) 的函数， 用决策集合决策变量简称决策。4.策略决策组成的系列称为策略（x1 开始的全过程的策略记作k阶段处于阶段x(k) 的决表示 x(k) 的允许。policy ）。由初始状态.由第k 阶段的状态x(k) 开始到终
5、止状态的后部子过程的策略,;k=2,n-1.可供选择的策略有一定的范围，（set of admissble polices）,用称为允许策略集合,等表示。5.状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态偏完全可以确定。用状态转移方程（ state transfer equations）表示这种演变规律，写作：6.阶段指标函数对于 k 阶段的状态x(k) ，当执行了决策时，除带来系统状态的转移之外，还产生第k 阶段的局部利益，它是总效益的一部分，称为阶段指标函数（stage文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.effective fucti
6、on ），记作.7.过程指标函数用来衡量策略或者是子策略执行效果的数量指标称为过程指标函数 （ process effective fuction ），它定义在所有k 后部子过程上，常用用表示，即k=1,2,n.当 k=1 时，就是全过程指标函数。如果状态x(k) 和子策略给定，那么也就被确定了，所以是 x(k) 和的函数，记为：常见的过程指标函数是连和形式或连积形式：8.最优指标函数过程指标函数最优指标函数(optimumeffectivefuction的最优值称为），记为f(x(k). 它表示，采取了最优子策略之后，后部子过程所获得的总效益，表示为：式 中opt 是 optimizatio
7、n 的缩写，意为最优化，可以根据具体问题去 max 或 min文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.三动态规划法的最优性原理和基本函数方程在动态规划中起核心作用的是最优性原理： “作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，相对于前面决策所形成的状态而言，余下的决策系列必须构成最优子策略。 ”动态规划解法的关键在于给出一种递推关系，一般把这种关系称为基本函数方程，注意到无后效性，最优指标函数为当 k=n 时，由于 x(n+1) 是整个决策过程的终止状态，以后不再做出决策，因此，这样就得到了可以用来递推的基本函数方程：f(x(n+1)=0.类似的
8、，可以得到乘法形式的基本函数方程：f(x(n+1)=1.四建立动态规划模型的基本步骤1. 阶段；2. 状态变量及可能状态集合；3. 决策变量及允许决策集合；4. 状态转移方程；5. 阶段指数函数；文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.6. 基本函数方程；建立动态规划模型基本上是上面6 个步骤，按上述顺序逐步确定 16 的内容。五动态规划法的递推方向及求解形式1. 递推解法基本方程：f(x(n+1)=0状态转移方程为计算步骤是，利用终端条件从k=n 开始由后向前递推基本方程，求得各阶段的最优决策和最优函数，最后算出f(x(1)就得到了最优决策系列时再按照状态转移方程
9、从k=1开始确定， k=1,2,n为 最 优 轨 迹 线 ，为最优策略。2. 顺推解法使用顺推解法时，一些概念的含义须做相应调整。状态变量 x(k) 表示第 k 阶段末系统的形态状况，最优值函数 f(x(k) 表示从第一阶段到第k 阶段总效益的最优值，状态文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.转移方程为基本函数方程为f(x(0)=0 或 13. 求解形式求解动态规划问题，一般有两种形式： 解析形式和表格形式，解析形式是利用函数的解析表达式，在每个阶段用经典求极值的方法得到最优解。表格形式是指各阶段的计算过程均在表格中进行，这种形式便于分析和比较，操作过程直观且简练
10、，适用于没有解析表达式的离散型问题。4.动态规划的适用条件适用动态规划的问题通常应满足如下3 点：1 最优化原理(最优子结构性质)。如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构性质，即满足最优化原理。由于对于有些问题的某些递归式来讲并不一定能保证最优化原则，因此在求解问题时有必要对它进行验证。若不能保持最优原则，则不可以应用动态规划法求解。在得到最优解的递归式之后，需要执行回溯以构造最优解。2 无后效性。应用动态规划法的一个重要条件就是将各阶段按照一定的次序排好，阶段 i 的状态只能由阶段 i+1 的状态来确定，与其他状态没有关系，尤其是于未发生的状态没有关系。换言之
11、，每个状态都是“过去历史的一个完整总结”。文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.这就是无后效性。3 子问题的重叠性。子问题的重叠性是指在利用递归算法自顶向下对问题进行求解时，每次产生的问题并不总是新问题，有些子问题可能会被重复计算多次。动态规划法正是利用子问题的这种重叠性质，对每一个问题只计算一次，然后将其计算结果保持起来，当再次需要计算已经计算过的子问题时，只要简单的查看一下以往的计算结果，从而获得较高的解题效率。子问题的的重叠性并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就无优势可言了。5.解决问题的步骤利用动态规划法求解问
12、题的算法通常包含如下几个步骤。1 分析。对原始的问题进行分析，找到问题的最优解的结构特征。2 分解。将所给问题按时间或空间特征分解成相互关联的阶段，并确定出计算局部最优解的递推关系，这是利用动态规划法解决问题的关键和难点所在。需要注意的是，分解后的各个阶段一定是有序的或者是可以排序的，即无后向性。否则问题就无法用动态规划求解。阶段之间相互联系方式是通过状态和状态转移体现的。每个阶段通常包含若干个状态，可以描述问题发展到这个阶段时文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持.所处在的一种客观情况。每个阶段的状态都由以前阶段的状态以某种方式“变化”来的，这样的“变化”称为状态转移。状态转移是导出状态的途径，也是联系各阶段的方式。3 解决。对于每个阶段通过自底向上的方法求得局部最优解。由于这一步骤通常是通过递推实现的，因此，需要
