运筹学课件--动态规划.pdf

动态规划动态规划 88.11 多阶段决策问题与动态规划多阶段决策问题与动态规划 8.2 动态规划的基本概念 8.3 动态规划的步骤 8.4 动态规划的应用 11 求解静态规划问题求解静态规划问题 2 资源分配问题 3 不确定性采购问题 4 排序问题排序问题 2013-5-20 运筹学课件 8.1 多阶段决策问题与动态规划多阶段决策问题与动态规划 动态规划所研究的对象是多阶段决策问题。 所谓多阶段决策问题是指一类活动过程，它 可以分为若干个相互联系的阶段可以分为若干个相互联系的阶段，在每个阶段都在每个阶段都 需要作出决策。这个决策不仅决定这一阶段的效 益，而且决定下一阶段的初始状态。 每个阶段的决策确定以后每个阶段的决策确定以后，，就得到就得到一个决策个决策 序列，称为策略。多阶段决策问题就是求一个策 略，使各阶段的效益的总和达到最优。 2013-5-20 运筹学课件 安全过河问题安全过河问题 古代有古代有33位商人各自带了一个仆人外出来到位商人各自带了一个仆人外出来到 了一个渡口, 渡口只有一条小船每次只能乘 22人人,,仆人私下约定只要岸上的仆人人数超过仆人私下约定只要岸上的仆人人数超过 商人人数,就可杀人越货.但是过河的决策由 商人制定商人制定.. 问商人如何安全的渡过河去? 2013-5-20 运筹学课件 2013-5-20 运筹学课件 8.1 多阶段决策问题与动态规划多阶段决策问题与动态规划 一、多阶段决策问题 1. 时间阶段的例子（机器负荷问题） 某厂有某厂有1000台机器台机器，现需作现需作一个五年计划个五年计划， 以决定每年安排多少台机器投入高负荷生产（产 量大但损耗也大量大但损耗也大））可使五年的总产量最大可使五年的总产量最大。 vv vv vv vv vv 1 2 3 4 5 s s s s S =1000 2 3 4 5 1 1 2 3 4 5 x x x x x 1 2 3 4 5 2013-5-20 运筹学课件 2. 空间阶段的例子（最短路问题） 如图为一线路网络。现要从A点铺设一条管 道到道到EE点点 ，图中两点间连线上数字表示两点间距图中两点间连线上数字表示两点间距 离。现需选一条由A到E的铺管线路，使总距离 最短最短 。 12 B C 1 1 3 14 22