运筹动态规划精.ppt

《运筹动态规划精.ppt》由会员分享，可在线阅读，更多相关《运筹动态规划精.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹动态规划第1页，本讲稿共42页动态规划动态规划（Dynamic Programming）R.Bellman50年代执教于普林斯顿和斯坦福大学，年代执教于普林斯顿和斯坦福大学，后进入兰德（后进入兰德（Rand）研究所。）研究所。1957年发表年发表“Dynamic Programming”一书，标识动态规划的正式诞生。一书，标识动态规划的正式诞生。动态规划是解决复杂系统优化问题的一种方法。动态规划是解决复杂系统优化问题的一种方法。是解决是解决动态系统多阶段动态系统多阶段决策过程的基本方法之一决策过程的基本方法之一。第2页，本讲稿共42页教学大纲教学大纲:理解理解动态规划基本概念、最优化原理和

2、动态规划基本概念、最优化原理和基本方程，通过资源分配和生产与存储等问题基本方程，通过资源分配和生产与存储等问题,学习应用动态规划解决多阶段决策问题。学习应用动态规划解决多阶段决策问题。重点重点:掌握动态规划掌握动态规划模型结构模型结构、逆序法、逆序法算法原理算法原理、资源分配、设备更新、生产于存贮资源分配、设备更新、生产于存贮等问题。等问题。难点难点为动态规划中为动态规划中状态变量状态变量等的确等的确定。定。第3页，本讲稿共42页123451.多阶段的决策问题多阶段的决策问题引例引例1 最短路问题最短路问题A12345678E75632515142534463333第4页，本讲稿共42页例例2

3、：生产与投入问题：生产与投入问题例例3：将一个单数：将一个单数C（C 0)分成分成 n 个部分个部分C1,C2 ,Cn之和，且之和，且Ci 0（i=1,n），问如何分割使其乘），问如何分割使其乘积为最大积为最大第5页，本讲稿共42页 包含包含随时间变化随时间变化的因素和变量的系统。的因素和变量的系统。系统在某个时刻的状态，往往要依某种形系统在某个时刻的状态，往往要依某种形式受过去某些决策的影响；式受过去某些决策的影响；将时间作为决策变量之一的决策问题称将时间作为决策变量之一的决策问题称为动态决策问题。为动态决策问题。如经济系统如经济系统,生产系统等生产系统等。动态系统动态系统：线性系统、非线性

4、系统。线性系统、非线性系统。动态系统动态系统的特点：的特点：动态决策动态决策 问题：问题：而系统的当前状态和决策又会影响而系统的当前状态和决策又会影响系统今后的发展。系统今后的发展。动态规划的研究对象第6页，本讲稿共42页即在系统发展的不同时刻（或阶段）根据系统所处的即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策；状态，不断地做出决策；每个阶段都要进行每个阶段都要进行决策决策,目的是使整个过程的决策目的是使整个过程的决策 达到最优效果。达到最优效果。动态决策问题的特点：动态决策问题的特点：系统所处的状态和时刻是进行决策的重要因素；系统所处的状态和时刻是进行决策的重要因素；找

5、到不同时刻的最优决策以及整个过程的最优策略。找到不同时刻的最优决策以及整个过程的最优策略。多阶段决策问题：多阶段决策问题：是动态决策问题的一种特殊形式；是动态决策问题的一种特殊形式；在多阶段决策过程中在多阶段决策过程中,系统的动态过程可以按照时间系统的动态过程可以按照时间进程分为进程分为状态状态相互相互联系联系而又相互而又相互区别区别的各个的各个阶段阶段；第7页，本讲稿共42页多阶段决策问题的典型例子：多阶段决策问题的典型例子：1.生产决策问题生产决策问题：企业在生产过程中，由于需求是：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，随时间变化的，因此企业为了获得

6、全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地就要在整个生产过程中逐月或逐季度地根据库存和需求决根据库存和需求决定生产计划。定生产计划。2.机机器器负负荷荷分分配配问问题题：某某种种机机器器可可以以在在高高低低两两种种不不同同的的负负荷荷下下进进行行生生产产。在在高高负负荷荷下下进进行行生生产产时时，产产品品的的年产量年产量g和投入生产的机器数量和投入生产的机器数量u1的关系为的关系为g=g(u1)12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策第8页，本讲稿共42页 这时，机器的年完好率为这时，机器的年完好率为a，即如果年初完好机器的数，即如果年初完好机器的数量为量为u

7、，到年终完好的机器就为，到年终完好的机器就为au,0a1。在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h和投入生产和投入生产的机器数量的机器数量u2的关系为的关系为 h=h(u2)假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s1。要求制定一。要求制定一个五年计划，在个五年计划，在每年开始时，决定如何重新分配每年开始时，决定如何重新分配完好的完好的机器在两种不同的负荷下生产的数量机器在两种不同的负荷下生产的数量，使在五年内产，使在五年内产品的总产量达到最高。品的总产量达到最高。相应的机器年完好率相应的机器年完好率b,0 b9/2当当当当时时时时矛盾，舍去矛盾，舍去

8、。（最优决策）（最优决策）S20第40页，本讲稿共42页一般动态规划应用第41页，本讲稿共42页动态规划的优缺点动态规划的优缺点优点优点:.最优解是全局最优解。最优解是全局最优解。.能得到一系列（包括子过程）的最优解。能得到一系列（包括子过程）的最优解。.不需要对系统状态转移方程、阶段效应函数等的不需要对系统状态转移方程、阶段效应函数等的解析性质作任何假设。解析性质作任何假设。缺点：缺点：.没有统一的标准模型和标准的算法可供使用。没有统一的标准模型和标准的算法可供使用。.应用的局限性，要求满足应用的局限性，要求满足“无后效性无后效性”。.“维数灾难维数灾难”问题。问题。第42页，本讲稿共42页