运筹学7动态规划.ppt

《运筹学7动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主要内容:§7.1多阶段决策过程的最优化§7.2动态规划的基本概念和基本原理§7.3动态规划模型的建立与求解§7.4动态规划应用举例第七章动态规划教学要求：1．掌握动态规划的基本概念：阶段、状态、决策、策略、状态转移方程、指标函数和最优值函数、最优策略、最优轨线2．了解动态规划的基本理论：最优性定理和最优性原理3．掌握动态规划基本思想和基本方程4．牢固掌握动态规划的顺序解法和逆序解法。会处理动态与静态规划的关系5．了解和掌握若干典型问题的动态规划模型及求解技巧：如最短路线、资源分配、生产计划、货物存储、设备更新与系统可靠性问题、背包问题、推销商问题等6．了解多维动态规划降维方

2、法和减少离散状态点数方法7．了解随机性问题的动态规划求解方法重点：动态规划顺序解法和逆序解法；若干典型问题动态规划模型及求解技巧；难点：建立动态规划数学模型的状态转移方程。§7.1多阶段决策过程的最优化动态规划（DynamicProgramming）是运筹学的一个重要分支，它是解决多阶段决策过程最优化的一种方法。美国数学家贝尔曼（R.E.Bellman）等人在50年代初提出了解决多阶段决策问题的“最优性原理”（PrincipleofOptimality）。1957年贝尔曼出版了专著“动态规划”，该书是动态规划的第一本著作。目前动态规划已经用于解决最优路径问题、资源分配问题、生

3、产调度问题、设备更新问题、复合系统可靠性问题及生产过程最优控制等，并且取得了显著的效果。回本章目录动态规划是求解问题的一种方法，而不是算法（线性规划是一种算法），因而没有标准的数学表达式，对于具体问题需要具体分析。一、多阶段决策问题在生产经营活动中，某些问题决策过程可以划分为若干相互联系的阶段，每个阶段需要做出决策，从而使整个过程取得最优。由于各个阶段不是孤立的，而是有机联系的，也就是说，本阶段的决策将影响过程下一阶段的发展，从而影响整个过程效果，所以决策者在进行决策时不能够仅考虑选择的决策方案使本阶段最优，还应该考虑本阶段决策对最终目标产生的影响，从而做出对全局来讲是最优的

4、决策。当每个阶段的决策确定以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决策问题。多阶段决策问题中，各个阶段一般是按照时间来划分的，随着时间的发展而产生各个阶段的决策，从而形成决策序列，这就是动态的含义。在一些与时间无关的静态问题中（如非线性规划等），可以人为地赋予时间的概念，使其成为一个多阶段决策问题，再用动态规划方法处理。12n状态决策状态决策状态状态决策二、多阶段决策问题举例属于多阶段决策类的问题很多，例如：例1工厂生产过程：由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐

5、季度地根据库存和需求情况决定生产计划安排。例2设备更新问题：一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费．因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。例3连续生产过程的控制问题：一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使

6、总产量最大。以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。例4资源分配问题：便属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配

7、量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题)。例5运输网络问题：如图7-1所示的运输网络，点间连线上的数字表示两地距离(也可是运费、时间等)，要求从fk(sk)至v10的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。1234图7-1运输网络图示（10）（14）（16）（15）（17）（22）（22）（21）（27）特别注意：动态规