第一节多阶段决策过程的最优化介绍.ppt

第七章 动态规划 7.1 多阶段决策过程的最优化 7.2 动态规划的基本概念和求解思路 7.3 离散型动态规划问题 7.4 连续型动态规划问题 7.5 动态规划方法应用举例 7.1 多阶段决策过程的最优化 　　动态规划是运筹学的重要分支，他的研究对象是多阶段决策问题。 　　所谓多阶段决策问题，是指问题本身可以按照时间、空间等划分为若干个相互联系的阶段． 动态规划模型的分类： 连续型 与 离散型 确定型 与 随机型 时间的 与 空间的 …… …… 实际问题常常是复合的。 本章主要研究动态与静态确定型的决策过程。 7.1.1 多阶段决策问题 　　动态规划的研究对象是多阶段决策问题。 　　对于多阶段决策问题，根据问题本身的特点可以将其求解过程划分为若干个相互联系的阶段。 　　每个阶段都有若干个方案可供选择，因此每一阶段都需要做出决策。 　　各个阶段确定的决策构成一个决策序列，称为一个策略． 　　在所有可供选择的策略中，对应效果最好的策略称为最优策略。 7.1.2 多阶段决策问题举例 （1）工厂生产过程 （2）设备更新问题 （3）连续生产过程的控制问题 （1）资源分配问题 （2）运输网络问题 与时间有关 与时间无关 7.1.3 动态规划求解的多阶段决策问题的特点 一般来说，系统在某个阶段的状态可能与系统过去经历的状态和决策有关． 能用动态规划方法求解的多阶段决策问题必须具有“无后效性”的特点。 所谓“无后效性”，即过去的历史不影响未来的发展． 过往的历史仅仅体现在本阶段的初始状态上． 例 最短线路问题 从 地到 地铺设一条管道，中间经过三个中间站；第一中间站可选 或 ，第二中间站可选 、 或 ，第三中间站可选 或 ，问如何选择可使管线最短？ 7.1.3 动态规划方法导引 枚举法 局部最优法 （贪婪算法） （动态规划的逆序法）： 1.先确定第四个阶段的最短子路线 记作： 其中， 表示从第k 阶段的起点 X 到终点E 的最短路线. （分四个阶段） 动态规划法 2.再确定最后两个阶段的最短子路线 3.确定后三个阶段的最短子路线 3.综合四个阶段的最短子路线 分析： 第四阶段的最短子路线 三四阶段的最短子路线 二三四 阶段的… 一至四 阶段的… √ √ √ √ 动态规划法的基本思路: 把复杂问题分解为一系列 同类型的便于求解的子问题 动态规划法的特点/优点: 整体最优蕴含阶段最优 例 设备分配问题 100台相同的机器被分配来加工两种不同的产品A 和B；已知： 加工A产品时，机器每周的损坏率为 ，加工B产品时，机器每周的损坏率为 ； 生产A产品时，每台每周的收益为1000元，B产品每台每周的收益为700元； 问采取怎样的分配方案可使四周内总收益最大？ 第一阶段（即第一周） 机器总台数为 设用于加工A产品的机器台数为 台 求得第一阶段的总收益为 则用于加工B产品的机器台数为 台 动态规划的顺序法： 第二阶段（即第二周） 机器总台数为 设该阶段用于加工A产品的机器台数为 台 求得该阶段的总收益为 则用于加工B产品的机器台数为 台 第三阶段（即第三周） 机器总台数为 设该阶段用于加工A产品的机器台数为 台 求得该阶段的总收益为 则用于加工B产品的机器台数为 台 第四阶段（即第四周） 机器总台数为 设该阶段用于加工A产品的机器台数为 台 求得该阶段的总收益为 则用于加工B产品的机器台数为 台 综上所述 每一阶段开始时机器总台数为 设该阶段用于加工A产品的机器台数为 台 该阶段的总收益为 则用于加工B产品的机器台数为 台 四个阶段的总收益为 问题就变为： 确定这四个阶段用于加工A产品的机器台数 使得四个阶段的总收益 为最大． 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * *