g=g(u1)
这时，机器的年完好率为a，即如果年初完好机器的数量为 u，到年终完好的机器就为au, 0<a<1。
在低负荷下生产时，产品的年产量h和投入生产的机器数 量u2的关系为
h=h(u2)
相应的机器年完好率b, 0<b<1。
假定开始生产时完好的机器数量为s1。要求制定一个五
年计划，在每年开始时，决定如何重新分配完好的机器在 两种不同的负荷下生产的数量，使在五年内产品的总产量 达到最高。
10 9
○2
6
7 7
○3
4
2 ○1
3 甘肃
8 3○4
k=1：第一阶段，甘肃 陕西
山西 陕西
线路： 1 2，1 3，1 4
k=3：第三阶段：山西 河北
线路：5 8，5 9，6 8，6 9，7 8，7 9
2、状态： 各阶段开始时所处的自然状况或客观条件
状态变量 描述各阶段状态的变量，简称为状态
sk 第k阶段的状态变量
3 . 线性规划、非线性规划等静态的规划问题也 可以通过适当地引入阶段的概念，应用动态规划 方法加以解决。
不包含时间因素的静态决策问题（本质上 是一次决策问题）也可以适当地引入阶段的 概念，作为多阶段的决策问题用动态规划方 法来解决。
4 . 最短路问题：给定一个交通网络图如下，其中两 点之间的数字表示距离（或花费），试求从A点到G 点的最短距离（总费用最小）。
7
3 甘肃
8 3○4
陕西
铺设方案2：路长= 16
○1 ○4 ○6 ○9 ○10
一个策略
每一个阶段的决策合在一起构成一个铺设方案
每个策略对应一个路长
寻找路长最短的铺设方案
寻找最优策略
1、阶段： 通常用k表示阶段，是指对整个 过程的自然划分
划分阶段的规则：
根据时间顺序或空间特征来划分阶段
如k=最目问1，短的题2路：分，问以成3，题便4个4：按阶次段序：来解○1北0优京8化4 河○ ○问89北题566891○ ○○675
多阶段决策问题的典型例子：
1 .生产决策问题：企业在生产过程中，由于需 求是随时间变化的，因此企业为了获得全年的 最佳生产效益，就要在整个生产过程中逐月或 逐季度地根据库存和需求决定生产计划。
2. 机器负荷分配问题：某种机器可以在高低两种不同的负荷 下进行生产。在高负荷下进行生产时，产品的年产量g和投 入生产的机器数量u1的关系为
阶段
阶段
阶段
分类
离散确定型
动态规划
离散随机型
连续确定型
连续随机型
根据决策过程的时间参数是离散的还是连 续的、过程的演变是确定性的还是随机性的
注意：
动态规划是求解某类问题的一种方法， 是考察问题的一种途径，而不是一种算法。
必须对具体问题进行具体分析，运用 动态规划的原理和方法，建立相应的模型， 然后再用动态规划方法去求解。
动态规划
(Dynamic programming)
多阶段决策过程的最优化 基本概念和基本原理 动态规划模型的建立与求解 动态规划在经济管理中的应用
创始时间
上个世纪50年代
创始人
美国数学家贝尔曼 （Richard. Bellman)
第一节 多阶段决策过程的最优化
动态规划是用来解决多阶段决策过程最 优化的一种数量方法
5 A
3
1 B1 3
6பைடு நூலகம்
8 B2 7
6
C1 6 8
3 C2 5
3 C3 3
84 C4
2 D1
2
D2 1 2
3 D3
3
E1 3
5 5 E2 2
6 6
E3
F1 4
G 3 F2
1
2
3
4
5
6
第二节 基本概念和基本原理
决策 状态 状态
1
决策 2 状态 状态
决策 n
阶段
阶段
阶段
策略 状态转移
指标函数
基本概念
设从甘肃要铺一条煤气管道到北京，途中须经过三个省：
这类活动可以按时间顺序分解成若干个相互联 系的阶段，每个阶段都有若干个方案可供选择
多阶段决策过程的最优化的目标：
达到整个活动过程的总体效果最优
系统的动态过程可以按照时间进程分为状态相互 联系而又相互区别的各个阶段，每个阶段都要进行 决策,目的是使整个过程的决策达到最优效果。
决策 决策
决策
状态 1 状态 2 状态 状态 n
陕西、山西、河北，每省设一个中间站。各省建站可供选
最 择的地点及各段距离如下图，现要求选择一条甘肃到北京
短 路 问 题
的铺管线路 使总距离最短。
多阶段决策问题
○8
8
○10
5 ○5
8
6 9○6
铺设方案1：路长=策21略
○1 ○3 ○5 ○8 ○10
4 北京
○9
河北
6
1
○7
山西
10 9
○2
7
6
○3
4
2 ○1
Sk ={sk} 第k阶段的状态集合
如最短路问题：
第一阶段的状态：○1
○北10 京84
○8 ○9
河北
5 6
○5
8
6 9○6
1○7
山西
第二阶段的状态：○2 ○3 ○4
10 9
○2
7 76○3
2 4 ○1
3 甘肃
8 3○4
陕西
s4 第4阶段的初始状态变量
○ s4 =⑧ 第4阶段的初始状态为 8
S3 ={s3}={⑤，⑥，⑦} S5 ={⑩}
择从而演变到下一阶段的某个状态，这种选 择手段称为决策
决策变量 描述决策的变量 ，简称为决策
uk
sk
第k阶段处
于
状态s
时的决策
k
变
量
U k sk 决策变量uk (sk )允许取值的范围
○北10 京84
○8 ○9
河北
5 8 ○5 6 9○6 6 1○7
山西
10 9
○2
7
6 7
○3
8 3○4
2 4 ○1
注：n个阶段的决策过程有个n+1状态变量 sn+1,表示sn演变的结果
动态规划中的状态应具有以下性质：
1、能描述过程的特征 2、具有无后效性(马尔可夫性)
当某阶段的状态给定时，这个阶段以后过 程的演变与该阶段以前各阶段的状态无关 3、状态是直接或间接可以观测的
3、决策： 当一个阶段的状态确定后，可以作出各种选
P 策略 ——允许策略集合
最优策略：使整个问题达到最优效果的策略
最短路问题： 策略 =铺设方案
策○1北0略京84
○8
○9
河北
5 8 ○5 6 9○6
6 1○7
如{ 1 3, 3 7 , 7 9 , 9 10} p1,4 山1西
10 9
○2
7 76○3
3 甘肃
陕西
允许决 策集合
u2 3 第2阶段当状态为③时的决策变量
可取值为：⑤，⑥，⑦
u 2
3
7
决策3 7
U 2 3 ={⑤，⑥，⑦}
4、策略：由各阶段的决策组成的序列称为策略
p1,n s1 从第一阶段初始状态s1开始到
第n阶段全过程的策略
即p1,n s1 u1 s1 , u2 s2 , un sn
