动态规划方法简介ppt课件.ppt

《动态规划方法简介ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划方法简介动态规划是解决多阶段决策过程最优化问题的一种方法。由美国数学家贝尔曼（Ballman）等人在20世纪50年代提出。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题。docin/sundae_meng动态规划是现代企业管理中的一种重要决策方法，可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。docin/sundae_meng一.多阶段决策过程最优化多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在

2、每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。动态规划的基本原理docin/sundae_meng12n状态决策状态决策状态状态决策图示多阶段决策问题，不论其本身是否与时间有关，由于分为阶段依次解决，这便具有明显的时序性，而在各阶段中所采取的决策是随阶段而变动的，不同阶段采取不同决策，这便是动态的含义.阶段往往可以用时段来表示，但动态规划在一定条件下也可以解决一些与时间无关的静态最优化问题，只要人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。docin/sundae_meng动态规划是用来解决多阶段决策过程最优化的一

3、种数量方法。其特点在于，它可以把一个n维决策问题变换为几个一维最优化问题，从而一个一个地去解决。需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。docin/sundae_meng二、多阶段决策问题举例1)工厂生产过程：由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。docin/sundae_meng2)设备更新问题：一般企业用于生产活动的设备，刚买来

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

5、sundae_meng4)运输网络问题（最短路问题）：如图1所示的运输网络，点间连线上的数字表示两地距离(也可是运费、时间等)，要求从v1至v10的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。docin/sundae_meng以上所举问题的发展过程都与时间因素有关，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非

6、动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。docin/sundae_meng三、动态规划方法导引例1：为了说明动态规划的基本思想方法和特点，下面以图1所示为例讨论的求最短路问题的方法。第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从v1到v10的路程可以分为4个阶段。第一段的走法有三种，第二三两段的走法各有两种，第四段的走法仅一种，因此共有3×2×2×1＝12条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是v1→v3→v7→v9→v10,

7、最短距离是18．docin/sundae_meng显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算．第二种方法即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是v1→v3→v5→v8→v10，全程长度是20；显然，这种方法的结果常是错误的．docin/sundae_meng第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将