文档介绍：本讲内容?什么是动态规划? ?动态规划求解方法?动态规划的应用实例 1什么是动态规划? 动态规划是 1951 年美国学者 Bellman 等在解决多阶段决策问题时提出。该方法在进行多阶段决策时,先将问题变成一系列相互联系的单阶段问题,在解决了这些单阶段问题后,在最优性原理基础上解决多阶段决策问题。 23 动态规划是现代企业管理中的一种重要决策动态规划是现代企业管理中的一种重要决策方法,可用于方法,可用于: :??最优路径问题最优路径问题??资源分配问题资源分配问题??生产计划生产计划??库存问题库存问题??投资问题投资问题??装载问题装载问题??排序问题排序问题??生产过程的最优控制生产过程的最优控制??…… 45一个例子例2:最短路径问题如图所示,要从①地到⑩地,如何走才能使总路程最短, 最短路程是多少? 5 3 1 234 567 9 8 10 24 743 632441 14633 34 6多阶段决策问题多阶段决策过程多阶段决策过程是指这样一类特殊的是指这样一类特殊的活动过程,它们可按时间顺序分解成活动过程,它们可按时间顺序分解成若干若干相互联系的相互联系的阶段阶段,在每个阶段都要做出决,在每个阶段都要做出决策,全部过程的决策是一个策,全部过程的决策是一个决策序列决策序列,所,所以多阶段决策问题也称为以多阶段决策问题也称为序贯决策序贯决策问题问题。 7动态规划的基本概念?阶段?状态?决策?策略?状态转移?指标函数 8动态规划的基本概念 1. 阶段对多阶段决策问题,可将所给问题的过程, 对多阶段决策问题,可将所给问题的过程, 按时间或空间特征分解成若干个相互联系的阶按时间或空间特征分解成若干个相互联系的阶段,描述阶段的变量称为阶段变量,常用段,描述阶段的变量称为阶段变量,常用 k k表示。表示。 9 第一阶段第二阶段第三阶段第四阶段例如前面最短路径问题可看成四个阶段的问题 K=1,2,3,4 1 234 567 9 8 10 24 743 632441 14633 34 5 3 10