－动态规划.ppt

文档介绍：Page Page Page :1管理运筹学动态规划 Page Page Page :2综述动态规划是解决多阶段决策过程最优化问题的一种方法。动态规划所研究的对象是多阶段决策问题。它把困难的多阶段决策问题变换成一系列互相联系较容易的单阶段问题。 Page Page Page :3综述多阶段决策问题是指一类活动过程,它可以分为若干个相互联系的阶段,在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益,而且决定下一阶段的初始状态。每个阶段的决策确定以后,就得到一个决策序列,称为策略。多阶段决策问题就是求一个策略,使各阶段的效益的总和达到最优。 Page Page Page :4综述动态规划可以解决管理中的最短路径、装载问题、库存问题、资源分配、生产过程最优化问题。 Page Page Page :5 §: Page Page Page :6 最短路径问题的应用 B A C B D B CD E C 2 123 123 12 51 12 14 106 10 4 13 12 11 39658 10 52找出 A到E的最短路径 Page Page Page :7 阶段划分 B A C B D B CD E C 2 123 123 1 2 51 12 14 106 10 4 13 12 11 39658 10 52I IV III II Page Page Page :8 将A到E的最短路径问题,转化为三个性质完全相同,但规模较小的子问题求解策略记S(x) 为节点 x到E的最短路??)( min )( ,iBAiBSdAS i????)( min )( ,jCBj iCSdBS ji????)( min )( ,kDCk jDSdCS kj??)( kDS Page Page Page :9 求解 S(D 1)=5, S(D 2)=2 SC SDSD CD () min ()() min , 1 12 11 39 3592 8 ???????????????????????????? SC SDSD CD () min ()() min , 2 12 22 65 6552 7 ???????????????????????????? SC SDSD CD () min ()() min , 3 12 32 8 10 85 102 12 ???????????????????????????? S(C 1 )=8 ; S(C 2 )=7 ; S(C 3 )=12 D1 ?E D2 ?E Page Page Page :10 SB SCSCSC BC () min ()()() min , 1 123 11 12 1410 1281471012 20 ?????????????????????????????????????? SB SCSCSC BC () min ()()() min , 2 123 21 6104 68107412 14 ?????????????????????????????????????? SB SCSCSC BC () min ()()() min , 3 123 32 13 1211 1381271112 19 ?????????????????????????????????????? S(C 1 )=8 ; S(C 2 )=7 ; S(C 3 )=12