美国数学家贝尔曼
（ Richard,Bellman)
创始时间上个世纪 50年代创始人
是运筹学的一个主要分支
是解决 多阶段决策过程 的最优化的一种方法多阶段决策过程：
资源分配问题，
生产计划与库存问题，
,投资问题,装载问题排序问题生产过程的最优控制等是一类特殊的活动过程，
这类活动可以按时间顺序分解成若干个相互联系的阶段，每个阶段都有若干个方案可供选择。
多阶段决策过程的 最优化的目标,
达到整个活动过程的总体效果最优
主要用于解决：最优路径问题，
动态规划
离散确定型离散随机型连续确定型连续随机型
4.1 动态规划的基本概念和方法一、几个典型的例题例 1 设从甘肃要铺一条煤气管道到北京，途中须经过三个省：陕西、山西、河北，每省设一个中间站。各省建站可供选择的地点及各段距离如下图，现要求选择一条甘肃到北京的铺管线路，
使总距离最短。
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9
○ 10
北京河北山西 陕西甘肃
8
4
5 8
9
6
16
10
9
6
7
7
38
4
2
3
最短路问题 多阶段决策问题
○ 1 ○ 3 ○ 5 ○ 8 ○ 10
路长 =21
○ 1 ○ 4 ○ 6 ○ 9 ○ 10路长 =
16
每一个阶段的决策合在一起构成一个铺设方案铺设方案 1：
铺设方案 2：
一个策略每个策略对应一个路长寻找 最优策略寻找路长最短的铺设方案策略例 2 （多阶段资源分配问题）
设有数量为 y的某种资源，将它分别投入两种生产方式 A和 B,已知收益函数分别是 g(x)和
h(x),x为资源投入量。设这种资源用于生产后还可以回收一部分用于生产,A,B的回收率分别为 a和 b（ 0≤a≤1,0≤b≤1 ），
问：对总数量为 y的资源进行 n个阶段的生产，
应如何分配每个阶段投入 A,B的资源数量，才能使总收益最大？
n个阶段的决策问题例 3（生产与存储问题）某工厂生产并销售某种产品。
已知今后四个月市场需求预测及每月生产 j个单位产品的费用如下：
每月库存 i个单位产品的费用 E(i)=0.5i(千元），该厂最大库存容量为 3个单位，每月最大生产能力为 6
个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。
6,2,13
00
jj
jjc
每个月视为一个阶段，
每个阶段都须决定生产几个、库存几个上一个阶段的决策直接影响下一个阶段的决策四个阶段的决策问题月 1 2 3 4
需求 2 3 2 4
例 4（投资决策问题）某公司现有资金 Q万元，在今后 5年内决定给 A,B,C,D四个项目投资，这些项目的投资期限、回报率均不相同，问应如何确定这些项目每年的投资额，使到第 5年末拥有资金的本利总额最大。
5个阶段的决策问题例 5（设备更新问题）某企业要决定一台设备未来 8年的更新计划，已预测了第 j年的购买设备的价格为 Kj,Gj为设备经过 j年后的残值,Cj为设备连续使用 j-1年后在第 j年的维修费 (j=1,2,…,8 ),问应在哪一年更新设备可使总费用最小每一年视为一个阶段，
每个阶段都须做决策：
继续使用旧设备还是购买新设备？
上一个阶段的决策直接影响下一个阶段的决策
8个阶段的决策问题二、基本概念
1、阶段
2,状态
3、决策
4、策略
5、状态转移方程
6、指标函数
1,阶段,
阶段是指对整个过程的自然划分
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9○
10
北京河北 山西 陕西甘肃
8
4
5 8
96
16
109
67
7
38
42
3
如最短路问题：
问题分成 4个阶段：
通常用 k表示阶段
k=1,2,3,4
1 2,1 3,1 4
5 8,7 96 8，5 9,6 9,7 8，
划分阶段的规则：
根据时间顺序或空间特征来划分阶段目的：以便按次序来解优化问题线路：
第一阶段，甘肃 陕西第三阶段：山西 河北线路：
k=1：
k=3：
2,状态,
第一阶段的状态,○ 1
第二阶段的状态,○ 2 ○ 3 ○ 4
状态变量 描述各阶段状态的变量
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9○ 10北京河北 山西 陕西甘肃
8
4
5 8
96
16
109
67
7
38
42
3
如最短路问题：
sk 第 k阶段的状态变量
s4 第 4阶段的状态变量 s4=8 第 4阶段的状态 ○ 8
Sk ={sk} 第 k阶段的状态集合
S3 ={s3}={5,6,7}
变量注,n个阶段的决策过程有个 n+1状态变量
sn+1,表示 sn演变的结果
，简称为状态各阶段开始时所处的自然状况
S5 ={10}
例 3（生产与存储问题）某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产 j个单位产品的费用为每月库存 i个单位产品的费用 E(i)=0.5i(千元），
该厂最大库存容量为 3个单位，每月最大生产能力为 6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。
6,2,13
00
jj
jjc
阶段 k=1,2,3,4
第 k阶段的 状态变量 sk
i月 1 2 3 4
g(i)需求 3 2 4
S1={0},S2={0,1,2,3},S3={0,1,2,3},S4={0,1,2,3}
=第 k个月月初的库存量动态规划中的 状态应具有以下性质,
1、能描述过程的特征
2、具有无后效性无后效性：
当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9○ 10北京河北 山西 陕西甘肃
8
4
5 8
96
16
109
67
7 3
8
42
3
3、状态是直接或间接可以观测的
3、决策,当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9○ 10北京河北 山西 陕西甘肃
8
4
5 8
96
16
109
67
7 3
8
42
3
决策变量 描述决策的变量
kk su 时的决策变量阶段处于状态第 ksk
32u
决策第 2阶段当状态为 3时的决策变量可取值为,5,6,7
732?u
kk sU 允许取值的范围决策变量 )( kk su
32U ={5,6,7}
，简称为决策
73?
允许决策集合例 3（生产与存储问题）某工厂生产并销售某种产品。
已知今后四个月市场需求预测及每月生产 j个单位产品的费用如下：
6,2,13
00
jj
jjc
月 1 2 3 4
需求 2 3 2 4
k=1,2,3,4 sk=第 k个月月初的库存量
S1={0} S2={0,1,2,3} S3={0,1,2,3} S4={0,1,2,3}
时产品的产量月月初库存量为第决策变量 kkk sksu?
={2,3,4,5}
每月库存 i个单位产品的费用 E(i)=0.5i(千元），该厂最大库存容量为 3个单位，每月最大生产能力为
6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，
使总费用最小。
={2,3,4,5} ={0,1,2,3} ={3}0
1U12U23U14U
4、策略,由各阶段的决策组成的序列称为策略
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9○ 10北京河北 山西 陕西甘肃
8
4
5 8
96
16
109
67
7
38
42
3
最短路问题：
策略 =铺设方案如 { }
阶段全过程的策略第开始到从第一阶段初始状态
n
ssp n 11,1
nnn susususp?,,22111,1?即
14,1p?
策略?P —— 允许策略集合最优策略,使整个问题达到最优效果的策略策略,{ }
最优策略 =最短的铺设路线
,31?,73?,97? 109?
,21?,52?,95? 109?
策略
14,1p?
例 3（生产与存储问题）某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产 j个单位产品的费用为每月库存 i个单位产品的费用 E(i)=0.5i(千元），该厂最大库存容量为 3个单位，每月最大生产能力为 6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。
6,2,13 00?jj jjc
i月 1 2 3 4
g(i)需求 2 3 2 4
阶段产品的产量第决策变量 ku k?
k=1,2,3,4 sk=第 k个月月初的库存量一个 策略 =一个 生产方案
04,1p 2,5,0,4
04,1p 2,3,2,4
费用,21（千元）
费用,23（千元）
最优策略,使总费用最小的生产方案策略,由各阶段的决策组成的序列称为策略
nnn susususp?,,22111,1?即原过程,一个 n段决策过程，从 1到 n叫作问题的原过程原过程的一个后部子过程：
对于任意给定的 k（ 1 ≤ k≤n）,从第 k段到第 n段的过程称为原过程的一个后部子过程
1,1 sp n 原过程的策略原过程的一个后部子过程的策略：
开始的策略：初始状态阶段个阶段的决策过程从第即有
ks
kn
knk sp,
策略,由各阶段的决策组成的序列称为策略
nnn susususp?,,22111,1?即原过程的一个后部子过程：
原过程的一个 后部子过程的策略,
..决策组成的序列阶段的开始到第阶段初始状态从第 nsk k
knk sp,记为：
阶段全过程的策略第开始到从第一阶段初始状态
n
ssp n 11,1
原过程,一个 n阶段决策过程，从 1到 n叫作问题的原过程对于任意给定的 k（ 1 ≤ k≤n）,从第 k段到第
n段的过程称为原过程的一个后部子过程原过程的策略
{ }
{ }
{ }
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9○ 10北京河北 山西 陕西甘肃
8
4
5 8
96
16
109
67
7
38
42
3最短路问题：
原过程的一个策略：
14,1p?
34,2p
74,3p
94,4p
{ }
,31?,73?,97? 109? 后部子过程的策略{ },73?,97? 109?
,97? 109? 后部子过程的策略
109?
后部子过程的策略54,3p,85? 108?
,95? 109?or{ }
（ Richard,Bellman)
创始时间上个世纪 50年代创始人
是运筹学的一个主要分支
是解决 多阶段决策过程 的最优化的一种方法多阶段决策过程：
资源分配问题，
生产计划与库存问题，
,投资问题,装载问题排序问题生产过程的最优控制等是一类特殊的活动过程，
这类活动可以按时间顺序分解成若干个相互联系的阶段，每个阶段都有若干个方案可供选择。
多阶段决策过程的 最优化的目标,
达到整个活动过程的总体效果最优
主要用于解决：最优路径问题，
动态规划
离散确定型离散随机型连续确定型连续随机型
4.1 动态规划的基本概念和方法一、几个典型的例题例 1 设从甘肃要铺一条煤气管道到北京，途中须经过三个省：陕西、山西、河北，每省设一个中间站。各省建站可供选择的地点及各段距离如下图，现要求选择一条甘肃到北京的铺管线路，
使总距离最短。
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9
○ 10
北京河北山西 陕西甘肃
8
4
5 8
9
6
16
10
9
6
7
7
38
4
2
3
最短路问题 多阶段决策问题
○ 1 ○ 3 ○ 5 ○ 8 ○ 10
路长 =21
○ 1 ○ 4 ○ 6 ○ 9 ○ 10路长 =
16
每一个阶段的决策合在一起构成一个铺设方案铺设方案 1：
铺设方案 2：
一个策略每个策略对应一个路长寻找 最优策略寻找路长最短的铺设方案策略例 2 （多阶段资源分配问题）
设有数量为 y的某种资源，将它分别投入两种生产方式 A和 B,已知收益函数分别是 g(x)和
h(x),x为资源投入量。设这种资源用于生产后还可以回收一部分用于生产,A,B的回收率分别为 a和 b（ 0≤a≤1,0≤b≤1 ），
问：对总数量为 y的资源进行 n个阶段的生产，
应如何分配每个阶段投入 A,B的资源数量，才能使总收益最大？
n个阶段的决策问题例 3（生产与存储问题）某工厂生产并销售某种产品。
已知今后四个月市场需求预测及每月生产 j个单位产品的费用如下：
每月库存 i个单位产品的费用 E(i)=0.5i(千元），该厂最大库存容量为 3个单位，每月最大生产能力为 6
个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。
6,2,13
00
jj
jjc
每个月视为一个阶段，
每个阶段都须决定生产几个、库存几个上一个阶段的决策直接影响下一个阶段的决策四个阶段的决策问题月 1 2 3 4
需求 2 3 2 4
例 4（投资决策问题）某公司现有资金 Q万元，在今后 5年内决定给 A,B,C,D四个项目投资，这些项目的投资期限、回报率均不相同，问应如何确定这些项目每年的投资额，使到第 5年末拥有资金的本利总额最大。
5个阶段的决策问题例 5（设备更新问题）某企业要决定一台设备未来 8年的更新计划，已预测了第 j年的购买设备的价格为 Kj,Gj为设备经过 j年后的残值,Cj为设备连续使用 j-1年后在第 j年的维修费 (j=1,2,…,8 ),问应在哪一年更新设备可使总费用最小每一年视为一个阶段，
每个阶段都须做决策：
继续使用旧设备还是购买新设备？
上一个阶段的决策直接影响下一个阶段的决策
8个阶段的决策问题二、基本概念
1、阶段
2,状态
3、决策
4、策略
5、状态转移方程
6、指标函数
1,阶段,
阶段是指对整个过程的自然划分
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9○
10
北京河北 山西 陕西甘肃
8
4
5 8
96
16
109
67
7
38
42
3
如最短路问题：
问题分成 4个阶段：
通常用 k表示阶段
k=1,2,3,4
1 2,1 3,1 4
5 8,7 96 8，5 9,6 9,7 8，
划分阶段的规则：
根据时间顺序或空间特征来划分阶段目的：以便按次序来解优化问题线路：
第一阶段，甘肃 陕西第三阶段：山西 河北线路：
k=1：
k=3：
2,状态,
第一阶段的状态,○ 1
第二阶段的状态,○ 2 ○ 3 ○ 4
状态变量 描述各阶段状态的变量
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9○ 10北京河北 山西 陕西甘肃
8
4
5 8
96
16
109
67
7
38
42
3
如最短路问题：
sk 第 k阶段的状态变量
s4 第 4阶段的状态变量 s4=8 第 4阶段的状态 ○ 8
Sk ={sk} 第 k阶段的状态集合
S3 ={s3}={5,6,7}
变量注,n个阶段的决策过程有个 n+1状态变量
sn+1,表示 sn演变的结果
，简称为状态各阶段开始时所处的自然状况
S5 ={10}
例 3（生产与存储问题）某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产 j个单位产品的费用为每月库存 i个单位产品的费用 E(i)=0.5i(千元），
该厂最大库存容量为 3个单位，每月最大生产能力为 6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。
6,2,13
00
jj
jjc
阶段 k=1,2,3,4
第 k阶段的 状态变量 sk
i月 1 2 3 4
g(i)需求 3 2 4
S1={0},S2={0,1,2,3},S3={0,1,2,3},S4={0,1,2,3}
=第 k个月月初的库存量动态规划中的 状态应具有以下性质,
1、能描述过程的特征
2、具有无后效性无后效性：
当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9○ 10北京河北 山西 陕西甘肃
8
4
5 8
96
16
109
67
7 3
8
42
3
3、状态是直接或间接可以观测的
3、决策,当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9○ 10北京河北 山西 陕西甘肃
8
4
5 8
96
16
109
67
7 3
8
42
3
决策变量 描述决策的变量
kk su 时的决策变量阶段处于状态第 ksk
32u
决策第 2阶段当状态为 3时的决策变量可取值为,5,6,7
732?u
kk sU 允许取值的范围决策变量 )( kk su
32U ={5,6,7}
，简称为决策
73?
允许决策集合例 3（生产与存储问题）某工厂生产并销售某种产品。
已知今后四个月市场需求预测及每月生产 j个单位产品的费用如下：
6,2,13
00
jj
jjc
月 1 2 3 4
需求 2 3 2 4
k=1,2,3,4 sk=第 k个月月初的库存量
S1={0} S2={0,1,2,3} S3={0,1,2,3} S4={0,1,2,3}
时产品的产量月月初库存量为第决策变量 kkk sksu?
={2,3,4,5}
每月库存 i个单位产品的费用 E(i)=0.5i(千元），该厂最大库存容量为 3个单位，每月最大生产能力为
6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，
使总费用最小。
={2,3,4,5} ={0,1,2,3} ={3}0
1U12U23U14U
4、策略,由各阶段的决策组成的序列称为策略
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9○ 10北京河北 山西 陕西甘肃
8
4
5 8
96
16
109
67
7
38
42
3
最短路问题：
策略 =铺设方案如 { }
阶段全过程的策略第开始到从第一阶段初始状态
n
ssp n 11,1
nnn susususp?,,22111,1?即
14,1p?
策略?P —— 允许策略集合最优策略,使整个问题达到最优效果的策略策略,{ }
最优策略 =最短的铺设路线
,31?,73?,97? 109?
,21?,52?,95? 109?
策略
14,1p?
例 3（生产与存储问题）某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产 j个单位产品的费用为每月库存 i个单位产品的费用 E(i)=0.5i(千元），该厂最大库存容量为 3个单位，每月最大生产能力为 6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。
6,2,13 00?jj jjc
i月 1 2 3 4
g(i)需求 2 3 2 4
阶段产品的产量第决策变量 ku k?
k=1,2,3,4 sk=第 k个月月初的库存量一个 策略 =一个 生产方案
04,1p 2,5,0,4
04,1p 2,3,2,4
费用,21（千元）
费用,23（千元）
最优策略,使总费用最小的生产方案策略,由各阶段的决策组成的序列称为策略
nnn susususp?,,22111,1?即原过程,一个 n段决策过程，从 1到 n叫作问题的原过程原过程的一个后部子过程：
对于任意给定的 k（ 1 ≤ k≤n）,从第 k段到第 n段的过程称为原过程的一个后部子过程
1,1 sp n 原过程的策略原过程的一个后部子过程的策略：
开始的策略：初始状态阶段个阶段的决策过程从第即有
ks
kn
knk sp,
策略,由各阶段的决策组成的序列称为策略
nnn susususp?,,22111,1?即原过程的一个后部子过程：
原过程的一个 后部子过程的策略,
..决策组成的序列阶段的开始到第阶段初始状态从第 nsk k
knk sp,记为：
阶段全过程的策略第开始到从第一阶段初始状态
n
ssp n 11,1
原过程,一个 n阶段决策过程，从 1到 n叫作问题的原过程对于任意给定的 k（ 1 ≤ k≤n）,从第 k段到第
n段的过程称为原过程的一个后部子过程原过程的策略
{ }
{ }
{ }
○ 1
○ 2
○ 3
○ 4
○ 5
○ 6
○ 7
○ 8
○ 9○ 10北京河北 山西 陕西甘肃
8
4
5 8
96
16
109
67
7
38
42
3最短路问题：
原过程的一个策略：
14,1p?
34,2p
74,3p
94,4p
{ }
,31?,73?,97? 109? 后部子过程的策略{ },73?,97? 109?
,97? 109? 后部子过程的策略
109?
后部子过程的策略54,3p,85? 108?
,95? 109?or{ }
