运筹学第5章.ppt

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

1、运筹学课件第五章动态规划制作：北京理工大学吴祈宗等1第五章动态规划多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点2一、多阶段决策问题(Multi-Stagedecisionprocess)多阶段决策过程特点:状态x1阶段1T1决策u1状态x2决策u2阶段2T2状态x3...状态xk决策uk阶段kTk状态xk+1...状态xn决策un阶段nTn状态xn+11.多阶段决策过程的最优化31.多阶段决策过程的最优化动态规划方法与“时间”关系很密切，随着时间过程的

2、发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。41.多阶段决策过程的最优化二、多阶段决策问题举例属于多阶段决策类的问题很多，例如：1)工厂生产过程：由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。51.多阶段决策过程的最优化2)设备更新问题：一般企业用于生产活动

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

4、入和输出，以使总产量最大。71.多阶段决策过程的最优化许多问题的发展过程都与时间因素有关。在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关。这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。81.多阶段决策过程的最优化4）资源分配问题：资源分配问题便属于这类静态问题。如

5、：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题)。91.多阶段决策过程的最优化5）运输网络问题：如图5-1所示的运输网络，点间连线上的数字表示两地距离(也可是运费、时间等)，要求从fk(sk)至v10的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为

6、4个阶段，而作为多阶段决策问题来研究。101.多阶段决策过程的最优化三、动态规划求解的多阶段决策问题的特点通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。111.多阶段决策过程的最优化无后效性（又称马尔柯夫性）无后效性（又称马尔柯夫性）是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系

7、统以前经历的状态和决策(历史)无关。121.多阶段决策过程的最优化四、动态规划方法导引为了说明动态规划的基本思想方法和特点，下面以图5-1所示为例讨论的求最短路问题的方法131.多阶段决策过程的最优化图5-11运输网络图示返回141.多阶段决策过程的最优化一般有三种思路求解全枚举法或穷举法：它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。可以计算：从v1到v10的路程可以分为4个阶段。第一段走法有3种，第二、三两段走法各有2种，第四段走法仅1种，共有3×2×2×1＝12条可能的

8、路线，分别算出各条路线的距离，最后进行比较，可知最优路线是v1→v3→v7→v9→v10,最短距离是18．用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算．151.多阶段决策过程的最优化局部最优路径法：某人从k点出发，并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是v1→v3→v5→v8→v1