运筹学 第七章动态规划

运筹学课件

第7章 动态规划

一、基本概念

相关背景：

动态规划——Dynamic Programming 是运筹学的一个分支， 是解决多阶段决策过程最优化的一种数学方法。 1951年，美国数学家贝尔曼(B. E. Bellman)等人提出了 “最优性原理”，即根据一类多阶段决策问题的特点，把多 阶段决策问题变换为一系列相互联系的单阶段决策问题，然 后分阶段逐个加以解决，从而创建了解决最优化问题的一种 新的方法 —— 动态规划。

运筹学课件

属于现代控制理论的一部分 以长远利益为目标的一系列决策 最优化原理，可归结为一个递推公式

动态规划是解决某一类问题的一种方法，是分析问题的一种 途径，而不是一种特殊算法（如线性规划是一种算法）。 因此，在学习动态规划时，除了对基本概念和方法正确地 理解外，应以丰富的想象力去建立模型，用创造性的技巧去 求解。

运筹学课件

动态规划模型分类：

动态规划模型的分类，根据多阶段决策过程的时间参量是离

散的还是连续的变量，过程分为离散决策过程和连续决策过 程。根据决策过程的演变是确定性的还是随机性的，可分为 确定性决策过程和随机性决策过程。 组合起来就有：离散确定型、离散随机型、连续确定型、连 续随机型四种决策过程模型。

运筹学课件

多阶段决策过程（Multi-Stage decision process）

（又称为序贯决策过程）

整个决策过程可按时间或空间顺序分解成若干相互联系的阶段， 每一阶段都需作出决策，全部过程的决策是一个决策序列。 多阶段决策过程最优化的目标： 达到整个活动过程的总体效果最优，而非各单个阶段最优的简单

总和。

决策u1 决策u2 决策uk 决策un

状态 阶段1 状态 阶段2 状态... 状态 阶段k 状态... 状态 阶段n 状态 s

s1

s2

s3

sk

sk+1

xn

n+1

运筹学课件

多阶段决策问题的典型例子：

1 . 生产决策问题：企业在生产过程中，由于需求是随时间变化

的，因此企业为了获得全年的最佳生产效益，就要在整个生产过

程中逐月或逐季度地根据库存和需求决定生产计划。

2. 机器负荷分配问题：某种机器可以在高低两种不同的负荷下 进行生产。在高负荷下进行生产时，产品的年产量 g 和投入生产

的机器数量u1的关系为

3.

g=g(u1 )

航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变 化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地 决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实 现目的（如软着落问题）。 4 . 线性规划、非线性规划等静态的规划问题也可以通过适当地引 入阶段的概念，应用动态规划方法加以解决。

运筹学课件

最短路问题：给定

运筹学课件

运筹学课件

运筹学课件

运筹学课件

运筹学课件

运筹学课件

运筹学课件

运筹学课件

运筹学课件

运筹学课件