运筹学动态规划.ppt

文档介绍：管理运筹学
动态规划
综述
动态规划是解决多阶段决策过程最优化问题的一种方法。动态规划所研究的对象是多阶段决策问题。它把困难的多阶段决策问题变换成一系列互相联系较容易的单阶段问题。
综述
多阶段决策问题是指一类活动过程,它可以分为若干个相互联系的阶段,在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益,而且决定下一阶段的初始状态。
每个阶段的决策确定以后,就得到一个决策序列,称为策略。多阶段决策问题就是求一个策略,使各阶段的效益的总和达到最优。
综述
动态规划可以解决管理中的最短路径、装载问题、库存问题、资源分配、生产过程最优化问题。
§
最短路径问题:
最短路径问题的应用
找出A到E的最短路径
阶段划分
I
IV
III
II
将A到E的最短路径问题,转化为三个性质完全相同,但规模较小的子问题
求解策略
记SE(x)为节点x到E的最短路
求解
S(D1)=5,
S(D2)=2
S(C1)=8;S(C2)=7; S(C3)=12
D1E
D2E
S(C1)=8;S(C2)=7; S(C3)=12