运筹学-第6章动态规划.ppt

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

1、2021/7/291第六章动态规划DynamicProgramming，DP美国数学家贝尔曼（Richard.Bellman,(1920～1984))创始时间上个世纪50年代创始人动态规划是运筹学的一个主要分支,同时也是现代企业管理中的一种重要决策方法,它是解决多阶段决策过程的最优化的一种方法。2021/7/292动态规划模型分类离散确定型离散随机型连续确定型连续随机型动态规划解决问题的思路独特,在处理某些优化问题时,有时比线性规划或者非线性规划更有效.需要丰富的想象力去建立模型，并能用创造性的技巧去求解。其中离散确定性是最基本的,本章主要介绍这种类型的问题,介绍动态规划

2、的基本思想、原理和方法.2021/7/293本章主要内容多阶段决策过程及其问题举例最短路问题动态规划的基本概念和基本方程动态规划应用举例资源分配问题背包问题生产库存问题………2021/7/2946.1多阶段决策过程及其问题举例动态规划研究的问题-----多阶段决策问题（顺序决策问题）研究的问题可以在时间或空间上划分为若干个相互联系阶段，称为”时段”。在每一个时段都需要做出决策,每时段的决策将影响到下一时段的决策,因此决策者每段决策时,不仅要考虑本阶段目标最优,还应考虑最终目标的最优,最终达到整个决策活动的总体目标最优.12状态状态状态n…状态决策决策决策状态2021/7/

3、295动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。然而，它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。2021/7/2962511214106104131112396581052C1C3D1AB1B3B2D2EC2例1最短路径问题求从A到E的最短路径。显然，这种运输网络问题是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。2021/7/297第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生

4、的方案和结果，再对它们一一进行比较，求出最优方案。这里从A到E的路程共有3×3×2×1＝18条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线。显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算．第二种方法贪心算法，即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是AB3C3D1E.距离为：1+11+8+5=252021/7/2982511214106104131112396581052C1

5、C3D1AB1B3B2D2EC2第1阶段第4阶段第3阶段第2阶段状态第三种方法是动态规划方法。2021/7/299基本思想：如果起点A经过B1,C1,D1而到终点E，则由C1出发经D1到E点这条子路线，是从C1到E的最短路线。所以，寻找最短路线，应该从最后一段开始找，然后往前递推.设sk：第k阶段初的状态（所处的结点）;xk(sk)：在sk状态时第k阶段所作的决策,决定下一个状态的位置；d(sk,xk)：第k阶段，采取策略xk所发生的距离;fk(sk)：在第k阶段，由sk状态开始到终点E的最短距离.2021/7/291025112141061041311123965810

6、52C1C3D1AB1B3B2D2EC2f5(E)=02021/7/29112511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02021/7/29122511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52021/7/29132511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52021/7/291425112141061

7、04131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82021/7/29152511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72021/7/29162511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)