1、(Dynamic programming)1主要内容一、多阶段决策问题二、动态规划的基本概念三、动态规划的基本思想四、动态规划递推求解方法五、动态规划的最优性原理六、动态规划问题应用举例2概述 1951年 Bellman提出， 1957 动态规划 动态规划 是解决 多阶段决策问题 的一种 数学方法 。动态规划思想 ：把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个 加以解决 。即：把 一个 n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决 。需指出 ：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方
2、法，建立相应的模型，然后再用 动态规划求解方法 去求解。应用 ：最短路线、资源分配、生产调度问题3一、多阶段决策问题 多阶段决策过程一类活动过程，可以按照时间进程分为 状态 相互 联系 而又相互 区别 的各个 阶段 ； 每个阶段 都要进行决策 ,目的是使整个过程的决策达到最优效果。 多阶段决策问题的特点（ 1）系统所处的 状态 和 时刻 是进行决策的重要因素，即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策；（ 2）目的是找到不同时刻的最优决策以及整个过程的最优策略。41 2 n状态 1决策 1状态 2决策 2状态 3 状态 n决策 n多阶段决策问题的典型例子：1 . 生产决
3、策问题 ：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据 库存和需求 决定 生产计划 。2. 机器负荷分配问题 ：某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量 g和投入生产的机器数量 u1的关系为g=g(u1)5这时，机器的年完好率为 a，即如果年初完好机器的数量为 u，到年终完好的机器就为 au, 0a1。在低负荷下生产时，产品的年产量 h和投入生产的机器数量 u2的关系为h=h(u2)假定开始生产时完好的机器数量为 s1。要求制定一个五年计划，在 每年开始时，决定如何重新分配 完好的 机
4、器在两种不同的负荷下生产的量 ，使在五年内产品的总产量达到最高。相应的机器年完好率 b, 0 b1。 63. 航天飞机飞行控制问题 ：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。4.不包含时间因素的线性规划、非线性规划等静态决策问题（本质上是一次决策问题）也可以适当地引入 “ 时间 ” 的概念，作为多阶段的决策问题用动态规划方法来解决。 75 . 最短路问题 ：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从 A到G的最短距离（总费用最小）。1 2 3 4 5 6AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338 422213335256643818（ 1）阶段（ 2）状态（ 3）决策（ 4）策略（ 5）状态转移方程（ 6）指标函数和最优值函数9二、动态规划的基本概念例一、从 A 地到 E地要铺设一条煤气管道 ,其中需经过三级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？
