1
动态规划 Dynamic Programming（ DP）
第七章动态规划
2
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
引言动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。 1951年，美国数学家贝尔曼（ R,
Bellman ）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。贝尔曼等人在研究和解决了大量实际问题之后，提出了解决这类问题的 —— 所谓“最优性原理”，通常称为“贝尔曼最优化原理”，从而创建了解决最优化问题的一种新的方法 —— 动态规划 —— （ Dynamic Programming ）。 贝尔曼的名著,动态规划,
于 1957年出版，这成了动态规划的第一本著作。
3
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
引言动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，他是现代企业管理中的一种重要的决策方法。
许多实际问题采用动态规划方法去处理，常比线性规划或非线性规划更加有效。特别对于离散性的问题，由于解析数学无法施展其术，而动态规划的方法就成为一种非常有效的工具。
4
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
引言应特别指出的是，动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。正如贝尔曼本人所说：“由于动态规划的最优化原理仅仅是一种基本原理，正是它的某种不确定性为你提供了发挥你创造性思维的巨大空间 !
本部分我们主要研究离散决策过程，介绍动态规划的基本概念、
理论和方法，在通过一些典型的应用问题来说明它的应用。
5
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
多阶段决策过程的最优化多阶段决策过程：
整个决策过程可按时间或空间顺序分解成若干 相互联系 的阶段，
每一阶段都需作出决策，全部过程的决策是一个决策序列。
多阶段决策过程最优化的目标：
达到整个活动过程的总体效果最优，而非各单个阶段最优的简单总和。
Page 199 例 1,2,3
请看如下典例 —— 最短路线问题
6
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理请看如下典例 —— 最短路线问题
7
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理
B1
A
C3
F2
F1
E3
E2
E1
D3
D2
D1
C4
C2
C1
B2
G
第一阶段 第二阶段 第三阶段 第四阶段 第五阶段 第六阶段
5
3
1
3
6
8
7
6
6
8
3
5
3
4
2
1
3
8
2
2
3
3
3
5
5
2
6 6
4
3
4
3
7
5
9
7
6
8
13
10
9
12
13
16
18
该点到 G点的最短距离
8
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理
1,阶段（ stage）
对整个决策过程的自然划分，通常根据 时间顺序或空间特征 来划分阶段，以便按阶段的次序逐段解决整个过程的优化问题。阶段变量通常用 k表示（ k = 1,2,3,…,n）。
2,状态（ state）
每个阶段开始时过程所处的自然状况或客观条件。它应能描述过程的特征并具有,无后效性,，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。
状态变量 —— sk（ state variable）
状态集合 —— Sk（ set of admissible states）
9
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理
3,决策（ decision）
当一个阶段的状态确定后，可以作出不同的 决定或选择,
从而演变到下一阶段的某个状态，这种决定或选择称为决策。
决策变量 —— uk（ sk） （ decision variable）简记为 uk
决策集合 —— Dk（ sk）（ set of admissible decision）
4,策略（ policy）
一组有序的 决策序列 构成一个策略，从第 k阶段至第 n阶段的一个策略称为后部子策略记为 pk,n → （ uk,uk+1,…,un）。
10
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理
5,状态转移方程（ equation of state transition）
在确定型 多阶段决策过程中，一旦某阶段的状态和决策为已知，
下一阶段的 状态便完全确定，用 状态转移方程反映这种状态间的 演变规律,写作：
sk+1 = Tk（ sk,uk） k =1,2,…,n
6,阶段指标值（ objective value in a stage）
衡量在一个阶段某个状态下各决策所对应的某种 数量指标或效果,通常表示为 vk（ sk,uk）。
11
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理
7,指标函数（ objective function）
衡量在选定某策略时，其优劣的数量指标。定义在整个过程（ 1
到 n阶段）上的指标函数记为,V1,n（ s1,u1,s2,…,sn,un），
定义在 后部子 过程 （ k到 n阶段）上的指标函数记为,Vk,n（ sk，
uk,…,sn,un），或简记为,Vk,n（ sk,pk,n ）。
常见指标函数的形式：
Vk,n（ sk,pk,n ） = ∑ vi（ si,ui）
Vk,n（ sk,pk,n ） = ∏ vi（ si,ui）
12
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理
8,最优指标函数（ optimal value function）
从第 k阶段 状态 sk 出发，采用 最优策略 p*k,n 到终止时的后部子 过程指标函数值。
fk（ sk ） = Opt [ Vk,n（ sk,pk,n ） ]
pk,n? Pk,n（ sk ）
13
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本思想基本思想总结：例 —— 最短路线问题
1、划分阶段。
2、求解从边界条件开始，逆向逐段递推。
3、每段的最优是从全局考虑的，并非仅考虑本阶段。
Bellman 最优化原理：
“一个过程的最优策略具有这样的性质，即无论开始的状态及初始的决策如何，对先前决策所形成的状态而言，其以后所有的决策必构成最优决策 —— 后部子过程最优。”
14
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本思想动态规划发展的早期，从简单逻辑分析出发给出了所谓“最优性原理”，然后在最优策略存在的前提下导出了基本动态方程，再由此方程求解最优策略。后来，在其应用过程中发现，最优性原理并非对任何多阶段决策过程普遍成立，它与基本动态方程并不是无条件等价的，二者之间也不存在任何确定的蕴含关系,基本方程 在动态规划中起着更为本质的作用。
fk（ sk） = opt [ vk（ sk,uk） + fk+1（ sk+1） ],k=n,n-1,…,2,1
uk? Dk（ sk）
fn+1（ sn+1） =?（ sn+1） ——边界条件 （?为已知函数）
15
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解建立动态规划的模型，就是分析问题并建立问题的动态规划基本方程，成功地应用动态规划方法的关键，在于识别问题本身的多阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题，
或者说正确地建立具体问题的基本方程，这不仅需要 经验和技巧,
也需要对实际问题 敏锐的动察力 。而正确建立基本递推关系方程的关键又在于正确选择状态变量 sk+1 = Tk（ sk,uk），这是建立动态规划的模型的两个要点。
16
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解建立动态规划的模型的十步曲：
1,正确、明确地划分阶段 k,k =1,2,3,…,n。依据决策过程的时间和空间的顺序关系。
2,正确选择并确定状态变量 sk 及状态集合 Sk 。状态变量的确定有时并非显而易见，要确定它，通常可对问题作如下分析而帮助确定状态变量
a,什么关系将各个阶段联系在一起？
b,为了决定今后的最优（子）策略，需要事件现状的哪些信息？
17
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
3,确定决策变量 uk 及 决策集合 Dk（ sk）。
4,写出 状态转移方程 sk+1 = Tk（ sk,uk）。
5,定义阶段指标值（函数） vk（ sk,uk）。
6,定义第 k至 n 阶段（后部子过程）的最优指标（目标）函数
fk（ sk）。
7,作出动态规划结构图：
sk sk+1 = Tk（ sk,uk）
k阶段
fk（ sk）
k+1阶段
fk+1（ sk+1）
opt
（?,?）
vk（ sk,uk）
uk? Dk（ sk）
18
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
8,建立动态规划基本方程：（逆序递推方程）
fk（ sk） = opt [ vk（ sk,uk） + fk+1（ sk+1） ],k= n-1,…,2,1
uk? Dk（ sk）
fn（ sn） = opt [ vn（ sn,un） ]
或 fn+1（ sn+1） =?（ sn+1） —— 边界条件 （?为已知函数）
un? Dn（ sn）
或 k=n,n-1,…,1
19
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
9,逆序递推求解动态规划基本方程。
求出最优决策序列 u*n,u*n-1,…,u*2,u*1
10,顺序确定 最优策略。 p*1n = { u*1,u*2,…,u*n }
s1
u*1 u*2 u*n
sns2 = T2（ s2,u2） …
…
20
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解例 分配投资问题某公司有资金 10 万元，若投资于项目 k （ k = 1,2,3）的投资额为 xk 时，其收益分别为 g1（ x1） = 4x1,g2（ x2） = 9x2,
g3（ x3） = 2x32,问应该如何分配投资数额才能使总收益最大？
该问题表面上看与时间无明显关系，其静态模型：
Max z = 4x1 + 9x2 + 2x32
x1 + x2 + x3 = 10
xi ≥ 0 （ i = 1,2,3）
21
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解如何应用动态规划方法求解此类静态规划问题？一般我们可以人为地给它赋予,时段,的概念，将投资项目按任意顺序进行排序，
如首先考虑项目 1 的投资，然后考虑项目 2 的投资 ……,即将问题人为划分为若干个阶段，每个阶段只决定对一个项目应投资的金额。
这样，可以将上述问题转化为一个 n 阶段决策过程。
分配投资问题的分析求解如下：
22
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
1,阶段 k = 1,2,3，分别表示项目 1,2,3
2,状态变量 sk,第 k 段初拥有的资金总量（分配给第 k 至第 3
个项目的资金数量）
3,决策变量 uk,第 k 段的投资量（分配给第 k 个项目的资金数量）,决策集合 Dk（ sk） =? uk? 0 ≤ uk ≤ sk?
4,状态转移方程 sk+1 = sk - uk
5,阶段指标值（函数） vk（ sk,uk） = gk（ xk）
6,定义 fk（ sk）：第 k 段初拥有的资金总量为 sk 时，第 k 至第 3
段按最优投资策略所获得的第 k 至第 3 段的总收益。
23
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
7,动态规划结构图
sk sk+1 = sk - uk
k阶段
fk（ sk）
k+1阶段
fk+1（ sk+1）
max
（? ）
gk（ xk）
0 ≤ uk ≤ sk
8,建立动态规划基本方程：（逆序递推方程）
fk（ sk） = max [ gk（ xk） + fk+1（ sk+1） ],k = 3,2,1
0 ≤ uk ≤ sk
f4（ s4） = 0
24
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
9,逆序递推求解动态规划基本方程
k = 3
f3（ s3） = Max [ 2x32 + f4（ s4） ] = Max [ 2x32 + 0 ]
0 ≤ u3 ≤ s3 0 ≤ u3 ≤ s3
f3 *（ s3） = 2s32,uk* = s3
25
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
k = 2
f2（ s2） = Max [ 9x2 + f3（ s3） ] = Max [ 9x2 + 2s32 ]
0 ≤ u2 ≤ s2
= Max [ 9x2 + 2（ s2 – x2 ） 2 ]
可以证明极大值只可能在端点取得，即：
f2（ 0） = 2s22 f2（ s2） = 9s2
s2 ＞ 9/2 时,f2（ 0） ＞ f2（ s2），此时 x2* = 0
s2 ＜ 9/2 时,f2（ 0） ＜ f2（ s2），此时 x2* = s3
26
动态规划 Dynamic Programming（ DP）
动态规划求解
k = 1
当 f2（ s2 ） = 9s2,f1（ 10） = Max [ 4x1 + f2（ s2） ]
0 ≤ x1 ≤ 10
= Max [ 9s1 – 5x1 ] = 9s1,x1* = 0
但此时 s2 = s1 – x1 =10 - 0 ＞ 9/2 与 s2 ＜ 9/2 矛盾，故舍去。
27
动态规划 Dynamic Programming（ DP）
动态规划求解
k = 1
当 f2（ s2 ） = 2s22,f1（ 10） = Max [ 4x1 + f2（ s2） ]
0 ≤ x1 ≤ 10
= Max [ 4s1 + 2（ s1 – x1 ） 2 ]
同样可以证明极大值只可能在端点取得，比较两个端点：
x1 = 0 时,f1（ 10） = 200,x1 = 10 时,f1（ 10） = 40
所以 x1* = 0
28
动态规划 Dynamic Programming（ DP）
动态规划求解
10,顺序确定 最优策略。
s1= 10
x1* = 0
s2 = s1 – x1* = 10 ＞ 9/2
x2* = 0
s3 = s2 – x2* = 10
x3* = 10
最优投资方案为全部资金投资于第 3 个项目，可获最大收益 200 万元。
29
动态规划 Dynamic Programming（ DP）
动态规划求解方法逆序递推法 （ Backward Induction Method）
将寻优过程看做连续递推的过程，从最终阶段开始,逆着 实际决策过程的进展方向逐段求解，在每一段求解中都要利用刚刚求解完那段的结果，直到初始阶段求出结果回到始点为止。
顺序递推法 （ Forward Induction Method）
从初始阶段向前递推，直到最终阶段为止。
顺序递推法本质上并无新的建树，只是对某些实际问题的求解，
应用起来较为简便而已。
30
动态规划 Dynamic Programming（ DP）
动态规划求解方法连续变量的离散化当 sk 与 uk 都是连续变量，各阶段的指标 没有特殊性质而较为复杂时，要求出 会比较困难，因而求全过程的最优策略也就相当不容易，这时常常采用把连续变量 离散化 的办法求其数值解。具体做法如下：
1) 令 sk = 0,?,2?,…,m? = a,把区间? 0,a? 进行分割，
的大小可依据问题所要求的精度以及计算机的容量确定。
2) 规定状态变量 sk 以及决策变量 uk 只在 离散点 0,?,2?,…,
m? 上取值，相应的函数就被定义在这些 离散点 上。
3) 逐步递推求解。
31
动态规划 Dynamic Programming（ DP）
动态规划求解方法高维问题的降维法以多维资源分配问题为例，若资源种类增加（即问题的维数增加）或所分配的产品增加（即阶段数增加）都会使得计算量成指数倍增长。这就是动态规划的,维数灾难,。为计算可行，可利用计算机速度快的特点，采用以时间换空间的办法，对问题进行降维或简化以求其解或近似解。常用方法有：
1、拉格朗日乘子法
2、逐步逼近法
3、疏密格子点法
32
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用资源分配问题（背包问题）
资源分配问题是动态规划的典型问题之一，它的一般提法是：
有某种资源，总量为 a,用于 n 个项目，若分配数量 ui 用于第 i
个项目，则第 i 个项目所产生的效果（收益）为 gi（ ui）。问题是如何分配资源总量 a 才能获得 n 个项目所产生的 总效果 （收益）最优（ max ）？
静态规划问题
max Z = g1（ u1） + g2（ u2） + … + g n（ un）
u1 + u2 + … + u n ≤（ =） a
ui ≥ 0
33
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用例 1 某公司新引进了 6 台高效率生产设备，该设备可用于生产 4
种不同的产品，当生产每种产品所投入的设备数量不同时所带来的利润也不相同。其详细资料如下,利润表 单位：万元设备数量 4 种 产 品产 品 1 产 品 2 产 品 3 产 品 4
0
1
2
3
4
5
6
0
20
42
60
75
85
90
0
25
45
57
65
70
73
0
18
39
61
78
90
95
0
28
47
65
74
80
85
34
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用该公司这 6 台设备在 4 种产品的生产中能够发挥最大的效益，
应该如何分配这 6 台设备，才能获得最大的总利润？
分析、建模此决策问题如按 4 种产品的一种顺序（可以任意排列，不妨按产品的自然顺序），将产品 1 分配的设备数量作为 第一阶段 需作出的决策，将产品 2 分配的设备数量作为 第二阶段 需作出的决策，将产品 3 分配的设备数量作为 第三阶段 需作出的决策，将产品 4 分配的设备数量作为 第四阶段 需作出的决策，这显然就是一个多阶段决策问题。因此有：
35
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
1,阶段 k,第 k 种产品,k=1,2,3,4
2,状态变量 sk,当按顺序应第 k 种产品分配设备时所余有的总量。
3,决策变量 uk,分配给第 k 种产品的设备数量。
Dk（ sk） = { uk | uk =0,1,2,…,sk }
4,状态转移方程,sk+1 = sk - uk
5,定义阶段指标值（函数） vk（ sk,uk） = vk（ uk ）：即分配给第 k 种产品的设备数量为 uk 时，第 k 种产品所创造的利润
（如利润表）。
36
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
6,定义 fk（ sk）：第 k 种产品分配设备时所余有的设备数量为 sk,
第 k 种产品至第四种产品按 最优分配策略 分配所余有的设备，
第 k 种产品至第四种产品所创造的 利润总和 。（第 k 种产品至第四种产品按某种设备分配策略所创造的 最大总利润 。
7,作出动态规划结构图：
sk sk+1 = sk - uk
k阶段
fk（ sk）
k+1阶段
fk+1（ sk+1）
max
（? ）
vk（ uk）
uk =0,1,2,…,sk
37
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
8,建立动态规划基本方程：（逆序递推方程）
fk（ sk） = max [ vk（ uk） + fk+1（ sk+1） ],k= 3,2,1u
k = 0,1,2,…,sk
f4（ s4） = max [ v4（ u4） ]
u4 = 0,1,2,…,s4
9,逆序递推求解动态规划基本方程。
38
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k= 4 时，状态集合 —— S4={ 0,1,2,3,4,5,6 }
f4（ s4） = max [ v4（ u4） ]
u4
s4
v4（ u4） f
4（ s4） u*40 1 2 3 4 5 6
0 0 0 0
1 0 28 28 1
2 0 28 47 47 2
3 0 28 47 65 65 3
4 0 28 47 65 74 74 4
5 0 28 47 65 74 80 80 5
6 0 28 47 65 74 80 85 85 6
39
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k= 3 时，状态集合 —— S3={ 0,1,2,3,4,5,6 }
f3（ s3） = max [ v3（ u3） + f4（ s4） ]
u3
s3
v3（ u3） + f4（ s4） f
3（ s3） u*30 1 2 3 4 5 6
0 0+0 0 0
1 0+28 18+0 28 0
2 0+47 18+28 39+0 47 0
3 0+65 18+47 39+28 61+0 67 2
4 0+74 18+65 39+47 61+28 78+0 89 3
5 0+80 18+74 39+65 61+47 78+28 90+0 108 3
6 0+85 18+80 39+74 61+65 78+47 90+28 95+0 126 3
s4 0 1 2 3 4 5 6
f4（ s4） 0 28 47 65 74 80 85
40
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k= 2 时，状态集合 —— S2={ 0,1,2,3,4,5,6 }
f2（ s2） = max [ v2（ u2） + f3（ s3） ]
u2
s2
v2（ u2） + f3（ s3） f
2（ s2） u*20 1 2 3 4 5 6
0 0+0 0 0
1 0+28 25+0 28 0
2 0+47 25+28 45+0 53 1
3 0+67 25+47 45+28 57+0 73 2
4 0+89 25+67 45+47 57+28 65+0 92 1,2
5 0+108 25+89 45+67 57+47 65+28 70+0 114 1
6 0+126 25+108 45+89 57+67 65+47 70+28 73+0 134 2
s3 0 1 2 3 4 5 6
f3（ s3） 0 28 47 67 89 108 126
41
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k= 1 时，状态集合 —— S1={ 6 }
f1（ s1） = max [ v1（ u1） + f2（ s2） ]
u1
s1
v1（ u1） + f2（ s2） f
1（ s1） u*10 1 2 3 4 5 6
0 0+134 20+114 42+92 60+73 75+53 85+28 90+0 134 0,1,2
10,顺序确定 最优策略之一。
s2= 6s1= 6
u1= 0 u4= 1u2= 2 u3= 3
s4= 1s3= 4
s2 0 1 2 3 4 5 6
f2（ s2） 0 28 53 73 92 114 134
42
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用该公司设备分配的所有最优方案：
最大总利润
（万元）产品 1 产品 2 产品 3 产品 4
方案 1 0台 2台 3台 1台 134
方案 2 1台 1台 3台 1台 134
方案 3 2台 1台 1台 2台 134
方案 4 2台 2台 0台 2台 134
43
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用例 2 机器负荷分配问题某种机器可在两种负荷下进行生产。在高负荷下生产的产量函数为 g = 8 u1 （ u1 为投入的机器数量），年完好率为 a = 0.7 ；
在低高负荷下生产的产量函数为 h = 5y （ y 为投入的机器数量），
年完好率为 b = 0.9 。开始生产时完好机器数量 s1 = 1000台，问每年如何分配机器在两种负荷下进行生产，使五年内生产的产品总产量最高。
44
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用建立动态规划模型：
1,阶段 k,生产年度,k = 1,2,3,4,5
2,状态变量 sk,第 k 年度初安排时拥有的完好机器数量，（此也为第 k-1 年度末时的完好机器数量）。
3,决策变量 uk,第 k年度初安排在 高 负荷下进行生产的机器数量，
于是 sk-uk 为该年度中安排在 低 负荷下进行生产的机器数量。
决策集合 Dk（ sk） = { uk | 0 ≤ uk ≤ sk }
4,状态转移方程,sk+1 = 0.7 uk + 0.9（ sk - uk ）
5,定义阶段指标值（函数） vk（ sk,uk） = 8 uk + 5 （ sk - uk ）
45
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
6,定义 fk（ sk）：第 k 年度初拥有的完好机器数量为 sk 时，将其安排（分配）于第 k 至第 5 年中两种负荷下进行生产时所生产的 最大 产量。
7,作出动态规划结构图：
sk sk+1 = 0.7 uk + 0.9（ sk - uk ）
k阶段
fk（ sk）
k+1阶段
fk+1（ sk+1）
max
（? ）
8 uk + 5 （ sk - uk ）
0 ≤ uk ≤ sk
46
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
8,建立动态规划基本方程：（逆序递推方程）
fk（ sk） = max { 8 uk + 5（ sk - uk ） + fk+1（ sk+1） },k= 4,3,2,1
f5（ s5） = max { 8 u5 + 5 （ s5 - u5 ） }
9,逆序递推求解动态规划基本方程。
0≤ uk≤ sk
0≤ u5≤ s5
k = 5
f5（ s5） = max { 8 u5 + 5 （ s5 - u5 ） } = max { 3u5 + 5s5 } = 8s5
0≤ u5≤ s5
u*5（ s5） = s5
47
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 4
f4（ s4） = max { 8 u4 + 5（ s4 - u4 ） + f5（ s5） }
0≤ u4≤ s4
= max { 8 u4 + 5（ s4 - u4 ） + 8s5 }
= max { 8 u4 + 5（ s4 - u4 ） + 8（ 0.7 u4 + 0.9（ s4 - u4 ） }
= max { 1.4 u4 + 12.2 s4 } = 13.6s4 u*4（ s4） = s4
k = 3
f3（ s3） = max { 8 u3 + 5（ s3 - u3 ） + f4（ s4） }
0≤ u3≤ s3
= max { 8 u3 + 5（ s3 - u3 ） + 13.6s4 }
= max { 8 u3 + 5（ s3 - u3 ） + 13.6（ 0.7 u3 + 0.9（ s3 - u3 ） }
= max { 0.28 u3 + 17.24 s3 }≈ 17.5s3 u*3（ s3） = s3
48
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 2
f2（ s2） = max { 8 u2 + 5（ s2 - u2 ） + f3（ s3） }
0≤ u2≤ s2
= max { 8 u2 + 5（ s2 - u2 ） + 17.5s3 }
= max { 8 u2 + 5（ s2 - u2 ） + 17.5（ 0.7 u2 + 0.9（ s2 - u2 ） }
= max {- 2.5 u2 + 20.75 s2 }≈ 20.8s2 u*2（ s2） = 0
k = 1
f1（ s1） = max { 8 u1 + 5（ s1 - u1 ） + f2（ s2） }
0≤ u1≤ s1
= max { 8 u1 + 5（ s1 - u1 ） + 20.8s2 }
= max { 8 u1 + 5（ s1 - u1 ） + 20.8（ 0.7 u1 + 0.9（ s1 - u1 ） }
= max {-1.16 u1 + 23.72 s1 }≈ 23.7s1 u*1（ s1） = 0
49
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
10,顺序确定 最优策略。 p*15 = { u*1,u*2,…,u*5 }
s1=1000 s2=900 s5≈ 397s3=810 s4=567
u*1= 0 u*2= 0 u*3= 810 u*4= 567 u*5= 397
最大产量 f1（ s1=1000） = 23700,五年生产期结束时
（即第六年初还剩余）有完好机器 s6 = 0.7? 397 = 278（台）
50
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用例 3 生产与存储问题某厂经过调查知在未来四个月中每月市场对该厂产品的需求量如表，该厂每批产品的生产准备费（固定成本）为 3 千元，若不生产则为零。每件产品的生产成本（可变成本）为 1千元。该厂最大生产能力为每批不超过 6 件，每件产品每月的库存费用为 0.5 千元，
第一月初该厂没有此产品的库存，并要求第四月末也无库存剩余。
该厂每月初应如何计划产品的生产量及库存量，才能既满足市场对该厂产品的需求又使其总费用最低。 产品需求表
k（月） 1 月 2月 3 月 4 月
dk（需求量）件 2 3 2 4
51
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用建立动态规划模型：
1,阶段 k,第 k月,k = 1,2,3,4
2,状态变量 sk,第 k月初（ k-1月末）的库存量，已知 s1 = s5 = 0。
3,决策变量 uk,第 k月的生产量。
根据条件有,0 ≤ uk ≤ 6,min（ sk+1） ≤ sk+1 ≤ max（ sk+1 ）
4,状态转移方程,sk+1 = sk + uk - dk
因此，决策集合 Dk（ sk） = { uk | 0 ≤ uk ≤ 6,min（ sk+1） ≤ sk+1≤
max（ sk+1 ） } = { uk | max [ 0,dk - sk + min（ sk+1） ] ≤ uk ≤ min
[ 6,dk - sk + max（ sk+1） ] }
52
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
5,阶段指标值（函数）：
vk（ sk,uk） = uk + 3?( uk ) + 0.5sk,其中?( uk ) = 0 当 uk = 0
1 当 uk > 0
6,定义 fk（ sk）：第 k月初库存量为 sk 时，第 k月至第 四月末的最低 总费用。
7,作出动态规划结构图：
sk sk+1 = sk + uk - dk
k 阶段
fk（ sk）
k+1阶段
fk+1（ sk+1）
min
（? ）
uk + 3?( uk ) + 0.5sk
uk? Dk（ sk）
53
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
8,动态方程：（逆序递推方程）
fk（ sk） = min { uk + 3?( uk ) + 0.5sk + fk+1（ sk+1） },k= 4,3,2,1
f5（ s5） = f5（ 0 ） = 0 因为第 5月计划期已结束，没有费用产生了。
uk? Dk（ sk）
9,逆序递推求解动态规划方程。
k = 4,s4 取值集合为 0,1,2,3,4。 因 min s5 = max s5 = 0
D4（ s4） = { u4 | max [ 0,d4 - s4 ] ≤ u4 ≤ min [ 6,d4 - s4 ] }
= {u4 | u4 = d4 - s4 = 4 - s4 }
f4（ s4） = min { u4 + 3?( u4 ) + 0.5s4 + 0 }
54
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
f4（ s4） = min { u4 + 3?( u4 ) + 0.5s4 + 0 }
s4 0 1 2 3 4
u4 4 3 2 1 0
f4（ s4） 7 6.5 6 5.5 2
u*4 4 3 2 1 0
55
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 3,s3 取值集合为 0,1,2,3,4,5,6。
min s4 = 0,max s4 = 4
D3（ s3） = { u3 | max [ 0,d3 - s3 + min（ s4） ] ≤ u3 ≤ min [ 6,d3 –
s3 + max （ s4 ） ] }
= { u3 | max [ 0,2 - s3 ] ≤ u3 ≤ min [ 6,6 - s3 ] }
f3（ s3） = min { u3 + 3?( u3 ) + 0.5s3 + f4（ s4 = s3 + u3 - d3 ） }
56
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
f3（ s3） = min { u3 + 3?( u3 ) + 0.5s3 + f4（ s4 = s3 + u3 - d3 ） }
u3
s3
[ u3 + 3?( u3 ) + 0.5s3 ] + f4（ s4 ） f
3（ s3） u*30 1 2 3 4 5 6
0 5+7 6+6.5 7+6 8+5.5 9+2 11 6
1 4.5+7 5.5+6.5 6.5+6 7.5+5.5 8.5+2 10.5 5
2 1+7 5+6.5 6+6 7+5.5 8+2 8 0
3 1.5+6.5 5.5+6 6.5+5.5 7.5+2 8 0
4 2+6 6+5.5 7+2 8 0
5 2.5+5.5 6.5+2 8 0
6 3+2 5 0
s4 0 1 2 3 4
f4（ s4） 7 6.5 6 5.5 2
57
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 2,s2 取值集合为 0,1,2,3,4。 因 s1=0,u1 ≤ 6,d1=2
min s3 = 0,max s3 = 6
D2（ s2） = { u2 | max [ 0,d2 – s2 + min（ s3） ] ≤ u2 ≤ min [ 6,d2 –
s2 + max （ s3） ] }
= { u2 | max [ 0,3 – s2 ] ≤ u2 ≤ min [ 6,9 – s2 ] }
f2（ s2） = min { u2 + 3?( u2 ) + 0.5s2 + f3（ s3 = s2 + u2 – d2 ） }
58
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
f2（ s2） = min { u2 + 3?( u2 ) + 0.5s2 + f3（ s3 = s2 + u2 – d2 ） }
u2
s2
[ u2 + 3?( u2 ) + 0.5s2 ] + f3（ s3 ） f
2（ s2） u*20 1 2 3 4 5 6
0 6+11 7+10.5 8+8 9+8 16 5
1 5.5+11 6.5+10.5 7.5+8 8.5+8 9.5+8 15.5 4
2 5+11 6+10.5 7+8 8+8 9+8 10+8 15 3
3 1.5+11 5.5+10.5 6.5+8 7.5+8 8.5+8 9.5+8 10.5+5 12.5 0
4 2+10.5 6+8 7+8 8+8 9+8 10+5 12.5 0
S3 0 1 2 3 4 5 6
f3（ s3） 11 10.5 8 8 8 8 5
59
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 1,s1 取值集合为 0 。
min s2 = 0,max s2 = 4
D1（ s1） = { u1 | max [ 0,d1 – s1 + min（ s2） ] ≤ u1 ≤ min [ 6,d1 –
s1 + max （ s2 ） ] }
= { u1 | max [ 0,2 – s1 ] ≤ u1 ≤ min [ 6,6 – s1 ] }
= { u1 | 2 ≤ u1 ≤ 6 }
f1（ s1） = min { u1 + 3?( u1 ) + 0.5s1 + f2（ s2 = s1 + u1 – d1 ） }
60
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
f1（ s1） = min { u1 + 3?( u1 ) + 0.5s1 + f2（ s2 = s1 + u1 – d1 ） }
s1 0 1 2 3 4
f2（ s2） 16 15.5 15 12.5 12.5
u1
s1
[ u1 + 3?( u1 ) + 0.5s1 ] + f2（ s2 ） f
2（ s2） u*22 3 4 5
0 5+16 6+15.5 7+15 8+12.5 20.5 5
61
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
10,顺序确定 最优策略。 p*14 = { u*1,u*2,u*3,u*4 }
s1= 0 s2= 3 s3= 0 s4= 4
u*1= 5 u*2= 0 u*3= 6 u*4= 0
该厂按以上生产与库存方案计划其总费用将是最低的，为
20.5 千元。
62
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用复合系统可靠性问题
p1 p2 pn…
pk表示系统中第 k 个部件的可靠度，即在给定标准下正常工作的概率。根据系统可靠性理论知，提高整个系统可靠性的一种十分有效的方法是采用 冗余 （储备 ——并联）技术。当系统中第 k个部件的冗余数量为 uk时，则系统中第 k个部件的可靠度提高为：
pk（ uk） = 1 -（ 1 - pk） 1+ uk
63
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用复合系统可靠性问题当 系统中第 k 个部件（ 1,2,…,n） 的冗余数量为 uk时，
从而整个系统的可靠度为：
P =? pk（ uk）
下面研究一个简单例子
64
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用复合系统可靠性问题例 一台机器的三个重要部件对整台机器的正常运行起着至关重要的作用，他们的可靠度及成本分别为：
p1 = 0.9,p2 = 0.7,p3 = 0.6；
c1 = 2,c2 = 1,c3 = 3； （ 单位：万元）
如果采用冗余技术来提高整台机器的可靠度，而提供的冗余经费仅有 3 万元，这三个重要部件应该怎样冗余才能使整台机器的可靠度最高。
这实际上是一个 3 万元如何分配使用在这三个重要部件冗余的资源分配问题，其动态规划结构图如下：
65
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
7,动态规划结构图：
sk sk+1 = sk + ckuk
k阶段
fk（ sk）
k+1阶段
fk+1（ sk+1）
max
（? ）
pk（ uk）
0≤ uk ≤ sk /ck
且为整数
8,动态方程：（逆序递推方程）
fk（ sk） = max { [ 1 -（ 1 - pk） 1+ uk ] * fk+1（ sk+1） },k= 3,2,1
f4（ s4） = 1
uk? Dk（ sk）
66
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
9,逆序递推求解动态规划方程。
k = 3 s2 取值集合为,0≤ sk ≤ 3
f3（ s3） = max { [ 1 -（ 1 - p3） 1+ u3 ] * f4（ s4） }
f3（ 0≤ s3 < 3） = max { [ 1 -（ 1 - 0.6） 1 ] * 1 } = 0.6
u*3（ s3 < 3 ） = 0
f3（ s3 = 3 ） = max { [ 1 -（ 1 - 0.6） 1+1 ] * 1 } = 0.84
u*3（ s3 = 3 ） = 1
67
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 2 s2 取值集合为,1,3
f2（ 1） = max （ 1 - 0.3） * f3（ 1）
（ 1 - 0.32） * f3（ 0）
= max 0.7 * 0.6
0.91 * 0.6
=0.546
u*2（ 1） = 1
f2（ 3） = max
（ 1 - 0.3） * f3（ 3）
（ 1 - 0.32） * f3（ 2）
（ 1 - 0.33） * f3（ 1）
（ 1 - 0.34） * f3（ 0）
= max
0.7 * 0.84
0.91 * 0.6
0.973 * 0.6
0.992 * 0.6
=0.595
u*2（ 3） = 3
68
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 1 s1 取值集合为,3
= 0.541= maxf1（ 3） = max
（ 1 - 0.1） * f2（ 3）
（ 1 - 0.12） * f2（ 1）
0.9 * 0.595
0.99 * 0.546
u*1（ 3） = 1
10,顺序确定 最优策略。
s1= 3 s2= 1 s3= 0
u*1= 1 u*2= 1 u*3= 0
69
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用设备更新问题在工业和交通运输企业中，经常会遇到因设备陈旧或部分损坏需要更新的问题。那么，从经济上分析，一台（一批）设备应该使用多少年后进行更新最为恰当，或合理的更新年限是多少？从而使在某一时间内的总收入达到最大（或总成本达到最小）。这是设备更新问题所要研究的。
70
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用设备更新问题的一般性描述：
已知一台设备的效益函数 r（ t），维修费用函数 u（ t），更新费用函数 c（ t），在 n 年内，每年年初都须作出决策，是继续使用
（ Keep）旧设备还是更换（ Replacement）一台新的设备，使在 n
年内总净效益最大。
设,r k（ t） —— 在第 k 年初设备已使用了 t 年（或称役龄为 t年）的设备在第 k 年再使用的效益。
u k（ t） —— 在第 k 年初设备已使用了 t 年时继续使用的第 k 年中的维修费用。
c k（ t） —— 在第 k 年初设备已使用了 t 年时的更新费用。
—— 为折扣因子（ 0 ≤? ≤1），表示一年以后的单位收入的价值视为现年的? 单位。
71
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用建立动态规划模型：
1,阶段 k,表计划使用设备的年数,k=1,2,…,n
2,状态变量 sk,第 k 年初，设备已使用过的年数（役龄 ） 。
3,决策变量 xk,第 k 年初更新设备，或保留使用旧设备。
Dk（ sk） = { xk | xk =R,K}
4,状态转移方程,sk+1 = 1 （当 xk =R ）
sk+1 = sk + 1 （当 xk = K ）
5,阶段指标值（函数）
vk（ sk,xk） =
r k（ sk ） - u k（ sk ） 当 xk = K
r k（ 0） - u k（ 0） - c k（ sk ） 当 xk = R
72
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
6,定义 fk（ sk）：第 k 年初，设备已使用了 sk 年时，第 k 年至第
n 年末的 最大效益 。
7,动态规划结构图：
sk
1
sk + 1
第 k 年第 k+1年第 k+1年f
k（ sk）
fk+1（ 1 ）
fk+1（ sk+ 1）
Max
（ ∑）
73
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
8,动态方程：（逆序递推方程）
fk(sk) = Max
fn+1(sn+1) = 0 k = n-1,…,2,1
9,逆序递推求解动态规划方程。
74
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用例 某台新设备的年效益及年均维修费、更新净费用如表所示。试确定今后 5 年内的更新策略，使总收益最大。（? = 1）
单位：万元役龄项目 0 1 2 3 4 5
效益 r k（ t） 5 4.5 4 3.75 3 2.5
维修费 u k（ t） 0.5 1 1.5 2 2.5 3
更新费 c k（ t） 0.5 1.5 2.2 2.5 3 3.5
75
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 5 s5 取值集合为,1,2,3,4
f5( 1 ) = Max
= Max = 3.5 x*5（ 1） = K
f5( 2 ) = Max = 2.5 x*5（ 2） = K
f5( 3 ) = 2 x*5（ 3） = K
f5( 4 ) = 1.5 x*5（ 4） = R
76
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 4 s4 取值集合为,1,2,3
f4( 1 ) = Max
= Max = 6.5 x*4（ 1） = R
f4( 2 ) = 5.8 x*4（ 2） = R
f4( 3 ) = 5.5 x*4（ 3） = R
77
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 3 s3 取值集合为,1,2
f3( 1 ) = Max
= Max = 9.5 x*3（ 1） = R
f3( 2 ) = Max
= Max = 8.8 x*3（ 2） = R
78
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 2 s2 取值集合为,1
f2( 1 ) = Max
= Max = 12.5 x*2（ 1） = R
79
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 1 s1 = 0
f1( 0 ) = Max
= Max = 17 x*1（ 0） = K
10,顺序确定 最优策略。
年份 1 2 3 4 5
sk 役龄 0 1 1 1 1
xk决策 K R R R K
80
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介随机动态规划不同于确定型动态规划之处在于其下一阶段的状态不是由当前阶段的状态以及决策完全确定。确切地说。下一阶段的状态是什么，服从一个概率分布。不过，这个概率分布仍由当前阶段的状态以及决策完全确定。由此，我们得到随机动态规划的基本结构。下图给出了这种结构的形象描绘：
81
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介随机动态规划的基本结构图
sk uk
s1k+1
sNk+1
s2k+1
opt
k+1阶段
p1
fk（ sk）
k阶段 p
2
pN
…
v1
v2
vN
…
…
fk+1（ s1k+1 ）
fk+1（ s2k+1 ）
fk+1（ sNk+1 ）
决策
uk? Dk（ sk）
82
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介随机动态规划的基本方程：
fk（ sk） = opt {? pi（ vi+ fk+1（ sik+1 ） ） }
uk? Dk（ sk） i =1
N
fn（ sn） = opt {? pivi }
un? Dn（ sn） i =1
N
k = n-1,…,2，
1
下面我们通过一个例子来具体阐述如何求解动态规划问题请看案例 ——
83
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介某公司相信对一个开发项目进行投资会取得成功。若投资会成功的话，公司就可以获得与投资数额相同的利润，若投资失败的话，
公司非但得不到利润，就连投资也完全不能收回。公司对有关资料详细分析后认为，每次投资 成功的概率为 2/3,失败的概率为 1/3。
目前公司对此项目进行投资的总资金有 3 百万元，为了有效控制投资风险，公司计划分 三次 投入资金（如果有资金的话）。公司需要作出的决策是每次应投入多少资金（以百万元为单位），才能使三次投资结束后公司最终获得 2 百万元利润（即最终拥有 5 百万元总资金）的 概率最大 。
84
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介
1,阶段 k,第 k 次投资,k = 1,2,3
2,状态变量 sk,第 k 次投资时拥有可用于投资的资金数量。
3,决策变量 uk,第 k 次投资的资金数量。
决策集合 Dk（ sk） = { uk | uk = 0,1,2,…,sk }
4,状态转移方程：
sk+1 = sk + uk 第 k 次投资确实成功。s
k - uk 第 k 次投资确实失败。
5,定义阶段指标值（函数）：
成功的概率为 2/3，失败的概率为 1/3。
85
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介
6,定义 fk（ sk ）：第 k 次投资时拥有可用于投资的资金数量 sk,
并一直投资到第 3 次投资结束后公司获得 2 百万元利润的最大概率。
我们应该注意到这样一个事实 —— 即使前两次投资失败了，公司仍然有机会最终赢得 2 百万元的利润。
7,随机动态规划的基本结构图：
sk uk
sk- uk
sk+ uk
k+1阶段
fk（ sk）
k阶段
fk+1（ sk + uk ）决策
uk =0,1,…,sk （? ）
max
fk+1（ sk - uk ）
86
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介
8,随机动态方程：
fk（ sk） = max {（ 2/3） fk+1（ sk + uk ） +（ 1/3） fk+1（ sk - uk ） }
uk =0,1,…,sk
k = 3,2,1
f4（ s4） =△ 0 s4? 5
1 s4 ≥ 5
87
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介
9,逆序递推求解随机动态方程。
k = 3 s3 = 0,1,2,3,4,5,…,12
s3 0 1 2 3 4 ≥5
f3（ s3） 0 0 0 2/3 2/3 1
u*3 … … … 2,3 1,2,3,4 0,≤ s3 - 5
88
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介
k = 2 s2 = 0,1,2,3,4,5,6
u2
s2
（ 2/3） f3（ s2 + u2 ） +（ 1/3） f3（ s2 - u2 ） f
2（ s2） u*20 1 2 3 4
0 0 0 …
1 0 0 0 …
2 0 4/9 4/9 4/9 1,2
3 2/3 4/9 2/3 2/3 2/3 0,2,3
4 2/3 8/9 2/3 2/3 2/3 8/9 1
≥ 5 1 1 0,≤ s3 - 5
89
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介
k = 1 s1 = 3
u2
s2
（ 2/3） f2（ s1 + u1 ） +（ 1/3） f2（ s1 – u1 ） f
1（ s1） u*10 1 2 3
3 2/3 20/27 2/3 2/3 20/27 1
于是，我们有最优策略：
s1=3,u*1=1
成功 s2=4,u*2=1
失败 s2=2,u*2=1
u*2=2
成功 s3=5,u*3=0
失败 s3=3,u*3=2 or 3
成功 s3=3 or 4,u*3=2,3 or 1,…,4
失败 s3=1 or 0，投资失败。
90
动态规划 Dynamic Programming（ DP）
第七章结束谢谢！
91
动态规划 Dynamic Programming（ DP）
P225 例 10 限期采购问题某部门欲采购一批原料，原料价格在五周内可能有所变动，
已预测得该种原料今后五周内取不同单价的概率如下表所示。
试确定该部门在五周内购进这批原料的最优策略，使采购价格的期望值最小。
原料价格（元） 概率
500
600
700
0.3
0.3
0.4
92
动态规划 Dynamic Programming（ DP）
1、阶段 k = 1,2,3,4,5
2、状态变量 sk,第 k 周的原料实际价格。
3、决策变量 uk,第 k 周的采购决策，若采购则 uk = 1，若不采购则 uk = 0。
4、阶段
动态规划 Dynamic Programming（ DP）
第七章动态规划
2
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
引言动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。 1951年，美国数学家贝尔曼（ R,
Bellman ）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。贝尔曼等人在研究和解决了大量实际问题之后，提出了解决这类问题的 —— 所谓“最优性原理”，通常称为“贝尔曼最优化原理”，从而创建了解决最优化问题的一种新的方法 —— 动态规划 —— （ Dynamic Programming ）。 贝尔曼的名著,动态规划,
于 1957年出版，这成了动态规划的第一本著作。
3
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
引言动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，他是现代企业管理中的一种重要的决策方法。
许多实际问题采用动态规划方法去处理，常比线性规划或非线性规划更加有效。特别对于离散性的问题，由于解析数学无法施展其术，而动态规划的方法就成为一种非常有效的工具。
4
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
引言应特别指出的是，动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。正如贝尔曼本人所说：“由于动态规划的最优化原理仅仅是一种基本原理，正是它的某种不确定性为你提供了发挥你创造性思维的巨大空间 !
本部分我们主要研究离散决策过程，介绍动态规划的基本概念、
理论和方法，在通过一些典型的应用问题来说明它的应用。
5
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
多阶段决策过程的最优化多阶段决策过程：
整个决策过程可按时间或空间顺序分解成若干 相互联系 的阶段，
每一阶段都需作出决策，全部过程的决策是一个决策序列。
多阶段决策过程最优化的目标：
达到整个活动过程的总体效果最优，而非各单个阶段最优的简单总和。
Page 199 例 1,2,3
请看如下典例 —— 最短路线问题
6
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理请看如下典例 —— 最短路线问题
7
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理
B1
A
C3
F2
F1
E3
E2
E1
D3
D2
D1
C4
C2
C1
B2
G
第一阶段 第二阶段 第三阶段 第四阶段 第五阶段 第六阶段
5
3
1
3
6
8
7
6
6
8
3
5
3
4
2
1
3
8
2
2
3
3
3
5
5
2
6 6
4
3
4
3
7
5
9
7
6
8
13
10
9
12
13
16
18
该点到 G点的最短距离
8
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理
1,阶段（ stage）
对整个决策过程的自然划分，通常根据 时间顺序或空间特征 来划分阶段，以便按阶段的次序逐段解决整个过程的优化问题。阶段变量通常用 k表示（ k = 1,2,3,…,n）。
2,状态（ state）
每个阶段开始时过程所处的自然状况或客观条件。它应能描述过程的特征并具有,无后效性,，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。
状态变量 —— sk（ state variable）
状态集合 —— Sk（ set of admissible states）
9
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理
3,决策（ decision）
当一个阶段的状态确定后，可以作出不同的 决定或选择,
从而演变到下一阶段的某个状态，这种决定或选择称为决策。
决策变量 —— uk（ sk） （ decision variable）简记为 uk
决策集合 —— Dk（ sk）（ set of admissible decision）
4,策略（ policy）
一组有序的 决策序列 构成一个策略，从第 k阶段至第 n阶段的一个策略称为后部子策略记为 pk,n → （ uk,uk+1,…,un）。
10
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理
5,状态转移方程（ equation of state transition）
在确定型 多阶段决策过程中，一旦某阶段的状态和决策为已知，
下一阶段的 状态便完全确定，用 状态转移方程反映这种状态间的 演变规律,写作：
sk+1 = Tk（ sk,uk） k =1,2,…,n
6,阶段指标值（ objective value in a stage）
衡量在一个阶段某个状态下各决策所对应的某种 数量指标或效果,通常表示为 vk（ sk,uk）。
11
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理
7,指标函数（ objective function）
衡量在选定某策略时，其优劣的数量指标。定义在整个过程（ 1
到 n阶段）上的指标函数记为,V1,n（ s1,u1,s2,…,sn,un），
定义在 后部子 过程 （ k到 n阶段）上的指标函数记为,Vk,n（ sk，
uk,…,sn,un），或简记为,Vk,n（ sk,pk,n ）。
常见指标函数的形式：
Vk,n（ sk,pk,n ） = ∑ vi（ si,ui）
Vk,n（ sk,pk,n ） = ∏ vi（ si,ui）
12
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本概念和基本原理
8,最优指标函数（ optimal value function）
从第 k阶段 状态 sk 出发，采用 最优策略 p*k,n 到终止时的后部子 过程指标函数值。
fk（ sk ） = Opt [ Vk,n（ sk,pk,n ） ]
pk,n? Pk,n（ sk ）
13
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本思想基本思想总结：例 —— 最短路线问题
1、划分阶段。
2、求解从边界条件开始，逆向逐段递推。
3、每段的最优是从全局考虑的，并非仅考虑本阶段。
Bellman 最优化原理：
“一个过程的最优策略具有这样的性质，即无论开始的状态及初始的决策如何，对先前决策所形成的状态而言，其以后所有的决策必构成最优决策 —— 后部子过程最优。”
14
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
动态规划的基本思想动态规划发展的早期，从简单逻辑分析出发给出了所谓“最优性原理”，然后在最优策略存在的前提下导出了基本动态方程，再由此方程求解最优策略。后来，在其应用过程中发现，最优性原理并非对任何多阶段决策过程普遍成立，它与基本动态方程并不是无条件等价的，二者之间也不存在任何确定的蕴含关系,基本方程 在动态规划中起着更为本质的作用。
fk（ sk） = opt [ vk（ sk,uk） + fk+1（ sk+1） ],k=n,n-1,…,2,1
uk? Dk（ sk）
fn+1（ sn+1） =?（ sn+1） ——边界条件 （?为已知函数）
15
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解建立动态规划的模型，就是分析问题并建立问题的动态规划基本方程，成功地应用动态规划方法的关键，在于识别问题本身的多阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题，
或者说正确地建立具体问题的基本方程，这不仅需要 经验和技巧,
也需要对实际问题 敏锐的动察力 。而正确建立基本递推关系方程的关键又在于正确选择状态变量 sk+1 = Tk（ sk,uk），这是建立动态规划的模型的两个要点。
16
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解建立动态规划的模型的十步曲：
1,正确、明确地划分阶段 k,k =1,2,3,…,n。依据决策过程的时间和空间的顺序关系。
2,正确选择并确定状态变量 sk 及状态集合 Sk 。状态变量的确定有时并非显而易见，要确定它，通常可对问题作如下分析而帮助确定状态变量
a,什么关系将各个阶段联系在一起？
b,为了决定今后的最优（子）策略，需要事件现状的哪些信息？
17
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
3,确定决策变量 uk 及 决策集合 Dk（ sk）。
4,写出 状态转移方程 sk+1 = Tk（ sk,uk）。
5,定义阶段指标值（函数） vk（ sk,uk）。
6,定义第 k至 n 阶段（后部子过程）的最优指标（目标）函数
fk（ sk）。
7,作出动态规划结构图：
sk sk+1 = Tk（ sk,uk）
k阶段
fk（ sk）
k+1阶段
fk+1（ sk+1）
opt
（?,?）
vk（ sk,uk）
uk? Dk（ sk）
18
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
8,建立动态规划基本方程：（逆序递推方程）
fk（ sk） = opt [ vk（ sk,uk） + fk+1（ sk+1） ],k= n-1,…,2,1
uk? Dk（ sk）
fn（ sn） = opt [ vn（ sn,un） ]
或 fn+1（ sn+1） =?（ sn+1） —— 边界条件 （?为已知函数）
un? Dn（ sn）
或 k=n,n-1,…,1
19
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
9,逆序递推求解动态规划基本方程。
求出最优决策序列 u*n,u*n-1,…,u*2,u*1
10,顺序确定 最优策略。 p*1n = { u*1,u*2,…,u*n }
s1
u*1 u*2 u*n
sns2 = T2（ s2,u2） …
…
20
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解例 分配投资问题某公司有资金 10 万元，若投资于项目 k （ k = 1,2,3）的投资额为 xk 时，其收益分别为 g1（ x1） = 4x1,g2（ x2） = 9x2,
g3（ x3） = 2x32,问应该如何分配投资数额才能使总收益最大？
该问题表面上看与时间无明显关系，其静态模型：
Max z = 4x1 + 9x2 + 2x32
x1 + x2 + x3 = 10
xi ≥ 0 （ i = 1,2,3）
21
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解如何应用动态规划方法求解此类静态规划问题？一般我们可以人为地给它赋予,时段,的概念，将投资项目按任意顺序进行排序，
如首先考虑项目 1 的投资，然后考虑项目 2 的投资 ……,即将问题人为划分为若干个阶段，每个阶段只决定对一个项目应投资的金额。
这样，可以将上述问题转化为一个 n 阶段决策过程。
分配投资问题的分析求解如下：
22
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
1,阶段 k = 1,2,3，分别表示项目 1,2,3
2,状态变量 sk,第 k 段初拥有的资金总量（分配给第 k 至第 3
个项目的资金数量）
3,决策变量 uk,第 k 段的投资量（分配给第 k 个项目的资金数量）,决策集合 Dk（ sk） =? uk? 0 ≤ uk ≤ sk?
4,状态转移方程 sk+1 = sk - uk
5,阶段指标值（函数） vk（ sk,uk） = gk（ xk）
6,定义 fk（ sk）：第 k 段初拥有的资金总量为 sk 时，第 k 至第 3
段按最优投资策略所获得的第 k 至第 3 段的总收益。
23
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
7,动态规划结构图
sk sk+1 = sk - uk
k阶段
fk（ sk）
k+1阶段
fk+1（ sk+1）
max
（? ）
gk（ xk）
0 ≤ uk ≤ sk
8,建立动态规划基本方程：（逆序递推方程）
fk（ sk） = max [ gk（ xk） + fk+1（ sk+1） ],k = 3,2,1
0 ≤ uk ≤ sk
f4（ s4） = 0
24
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
9,逆序递推求解动态规划基本方程
k = 3
f3（ s3） = Max [ 2x32 + f4（ s4） ] = Max [ 2x32 + 0 ]
0 ≤ u3 ≤ s3 0 ≤ u3 ≤ s3
f3 *（ s3） = 2s32,uk* = s3
25
动态规划 Dynamic Programming（ DP）
动态规划 ——Dynamic Programming
建立 DP 模型与求解
k = 2
f2（ s2） = Max [ 9x2 + f3（ s3） ] = Max [ 9x2 + 2s32 ]
0 ≤ u2 ≤ s2
= Max [ 9x2 + 2（ s2 – x2 ） 2 ]
可以证明极大值只可能在端点取得，即：
f2（ 0） = 2s22 f2（ s2） = 9s2
s2 ＞ 9/2 时,f2（ 0） ＞ f2（ s2），此时 x2* = 0
s2 ＜ 9/2 时,f2（ 0） ＜ f2（ s2），此时 x2* = s3
26
动态规划 Dynamic Programming（ DP）
动态规划求解
k = 1
当 f2（ s2 ） = 9s2,f1（ 10） = Max [ 4x1 + f2（ s2） ]
0 ≤ x1 ≤ 10
= Max [ 9s1 – 5x1 ] = 9s1,x1* = 0
但此时 s2 = s1 – x1 =10 - 0 ＞ 9/2 与 s2 ＜ 9/2 矛盾，故舍去。
27
动态规划 Dynamic Programming（ DP）
动态规划求解
k = 1
当 f2（ s2 ） = 2s22,f1（ 10） = Max [ 4x1 + f2（ s2） ]
0 ≤ x1 ≤ 10
= Max [ 4s1 + 2（ s1 – x1 ） 2 ]
同样可以证明极大值只可能在端点取得，比较两个端点：
x1 = 0 时,f1（ 10） = 200,x1 = 10 时,f1（ 10） = 40
所以 x1* = 0
28
动态规划 Dynamic Programming（ DP）
动态规划求解
10,顺序确定 最优策略。
s1= 10
x1* = 0
s2 = s1 – x1* = 10 ＞ 9/2
x2* = 0
s3 = s2 – x2* = 10
x3* = 10
最优投资方案为全部资金投资于第 3 个项目，可获最大收益 200 万元。
29
动态规划 Dynamic Programming（ DP）
动态规划求解方法逆序递推法 （ Backward Induction Method）
将寻优过程看做连续递推的过程，从最终阶段开始,逆着 实际决策过程的进展方向逐段求解，在每一段求解中都要利用刚刚求解完那段的结果，直到初始阶段求出结果回到始点为止。
顺序递推法 （ Forward Induction Method）
从初始阶段向前递推，直到最终阶段为止。
顺序递推法本质上并无新的建树，只是对某些实际问题的求解，
应用起来较为简便而已。
30
动态规划 Dynamic Programming（ DP）
动态规划求解方法连续变量的离散化当 sk 与 uk 都是连续变量，各阶段的指标 没有特殊性质而较为复杂时，要求出 会比较困难，因而求全过程的最优策略也就相当不容易，这时常常采用把连续变量 离散化 的办法求其数值解。具体做法如下：
1) 令 sk = 0,?,2?,…,m? = a,把区间? 0,a? 进行分割，
的大小可依据问题所要求的精度以及计算机的容量确定。
2) 规定状态变量 sk 以及决策变量 uk 只在 离散点 0,?,2?,…,
m? 上取值，相应的函数就被定义在这些 离散点 上。
3) 逐步递推求解。
31
动态规划 Dynamic Programming（ DP）
动态规划求解方法高维问题的降维法以多维资源分配问题为例，若资源种类增加（即问题的维数增加）或所分配的产品增加（即阶段数增加）都会使得计算量成指数倍增长。这就是动态规划的,维数灾难,。为计算可行，可利用计算机速度快的特点，采用以时间换空间的办法，对问题进行降维或简化以求其解或近似解。常用方法有：
1、拉格朗日乘子法
2、逐步逼近法
3、疏密格子点法
32
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用资源分配问题（背包问题）
资源分配问题是动态规划的典型问题之一，它的一般提法是：
有某种资源，总量为 a,用于 n 个项目，若分配数量 ui 用于第 i
个项目，则第 i 个项目所产生的效果（收益）为 gi（ ui）。问题是如何分配资源总量 a 才能获得 n 个项目所产生的 总效果 （收益）最优（ max ）？
静态规划问题
max Z = g1（ u1） + g2（ u2） + … + g n（ un）
u1 + u2 + … + u n ≤（ =） a
ui ≥ 0
33
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用例 1 某公司新引进了 6 台高效率生产设备，该设备可用于生产 4
种不同的产品，当生产每种产品所投入的设备数量不同时所带来的利润也不相同。其详细资料如下,利润表 单位：万元设备数量 4 种 产 品产 品 1 产 品 2 产 品 3 产 品 4
0
1
2
3
4
5
6
0
20
42
60
75
85
90
0
25
45
57
65
70
73
0
18
39
61
78
90
95
0
28
47
65
74
80
85
34
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用该公司这 6 台设备在 4 种产品的生产中能够发挥最大的效益，
应该如何分配这 6 台设备，才能获得最大的总利润？
分析、建模此决策问题如按 4 种产品的一种顺序（可以任意排列，不妨按产品的自然顺序），将产品 1 分配的设备数量作为 第一阶段 需作出的决策，将产品 2 分配的设备数量作为 第二阶段 需作出的决策，将产品 3 分配的设备数量作为 第三阶段 需作出的决策，将产品 4 分配的设备数量作为 第四阶段 需作出的决策，这显然就是一个多阶段决策问题。因此有：
35
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
1,阶段 k,第 k 种产品,k=1,2,3,4
2,状态变量 sk,当按顺序应第 k 种产品分配设备时所余有的总量。
3,决策变量 uk,分配给第 k 种产品的设备数量。
Dk（ sk） = { uk | uk =0,1,2,…,sk }
4,状态转移方程,sk+1 = sk - uk
5,定义阶段指标值（函数） vk（ sk,uk） = vk（ uk ）：即分配给第 k 种产品的设备数量为 uk 时，第 k 种产品所创造的利润
（如利润表）。
36
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
6,定义 fk（ sk）：第 k 种产品分配设备时所余有的设备数量为 sk,
第 k 种产品至第四种产品按 最优分配策略 分配所余有的设备，
第 k 种产品至第四种产品所创造的 利润总和 。（第 k 种产品至第四种产品按某种设备分配策略所创造的 最大总利润 。
7,作出动态规划结构图：
sk sk+1 = sk - uk
k阶段
fk（ sk）
k+1阶段
fk+1（ sk+1）
max
（? ）
vk（ uk）
uk =0,1,2,…,sk
37
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
8,建立动态规划基本方程：（逆序递推方程）
fk（ sk） = max [ vk（ uk） + fk+1（ sk+1） ],k= 3,2,1u
k = 0,1,2,…,sk
f4（ s4） = max [ v4（ u4） ]
u4 = 0,1,2,…,s4
9,逆序递推求解动态规划基本方程。
38
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k= 4 时，状态集合 —— S4={ 0,1,2,3,4,5,6 }
f4（ s4） = max [ v4（ u4） ]
u4
s4
v4（ u4） f
4（ s4） u*40 1 2 3 4 5 6
0 0 0 0
1 0 28 28 1
2 0 28 47 47 2
3 0 28 47 65 65 3
4 0 28 47 65 74 74 4
5 0 28 47 65 74 80 80 5
6 0 28 47 65 74 80 85 85 6
39
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k= 3 时，状态集合 —— S3={ 0,1,2,3,4,5,6 }
f3（ s3） = max [ v3（ u3） + f4（ s4） ]
u3
s3
v3（ u3） + f4（ s4） f
3（ s3） u*30 1 2 3 4 5 6
0 0+0 0 0
1 0+28 18+0 28 0
2 0+47 18+28 39+0 47 0
3 0+65 18+47 39+28 61+0 67 2
4 0+74 18+65 39+47 61+28 78+0 89 3
5 0+80 18+74 39+65 61+47 78+28 90+0 108 3
6 0+85 18+80 39+74 61+65 78+47 90+28 95+0 126 3
s4 0 1 2 3 4 5 6
f4（ s4） 0 28 47 65 74 80 85
40
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k= 2 时，状态集合 —— S2={ 0,1,2,3,4,5,6 }
f2（ s2） = max [ v2（ u2） + f3（ s3） ]
u2
s2
v2（ u2） + f3（ s3） f
2（ s2） u*20 1 2 3 4 5 6
0 0+0 0 0
1 0+28 25+0 28 0
2 0+47 25+28 45+0 53 1
3 0+67 25+47 45+28 57+0 73 2
4 0+89 25+67 45+47 57+28 65+0 92 1,2
5 0+108 25+89 45+67 57+47 65+28 70+0 114 1
6 0+126 25+108 45+89 57+67 65+47 70+28 73+0 134 2
s3 0 1 2 3 4 5 6
f3（ s3） 0 28 47 67 89 108 126
41
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k= 1 时，状态集合 —— S1={ 6 }
f1（ s1） = max [ v1（ u1） + f2（ s2） ]
u1
s1
v1（ u1） + f2（ s2） f
1（ s1） u*10 1 2 3 4 5 6
0 0+134 20+114 42+92 60+73 75+53 85+28 90+0 134 0,1,2
10,顺序确定 最优策略之一。
s2= 6s1= 6
u1= 0 u4= 1u2= 2 u3= 3
s4= 1s3= 4
s2 0 1 2 3 4 5 6
f2（ s2） 0 28 53 73 92 114 134
42
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用该公司设备分配的所有最优方案：
最大总利润
（万元）产品 1 产品 2 产品 3 产品 4
方案 1 0台 2台 3台 1台 134
方案 2 1台 1台 3台 1台 134
方案 3 2台 1台 1台 2台 134
方案 4 2台 2台 0台 2台 134
43
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用例 2 机器负荷分配问题某种机器可在两种负荷下进行生产。在高负荷下生产的产量函数为 g = 8 u1 （ u1 为投入的机器数量），年完好率为 a = 0.7 ；
在低高负荷下生产的产量函数为 h = 5y （ y 为投入的机器数量），
年完好率为 b = 0.9 。开始生产时完好机器数量 s1 = 1000台，问每年如何分配机器在两种负荷下进行生产，使五年内生产的产品总产量最高。
44
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用建立动态规划模型：
1,阶段 k,生产年度,k = 1,2,3,4,5
2,状态变量 sk,第 k 年度初安排时拥有的完好机器数量，（此也为第 k-1 年度末时的完好机器数量）。
3,决策变量 uk,第 k年度初安排在 高 负荷下进行生产的机器数量，
于是 sk-uk 为该年度中安排在 低 负荷下进行生产的机器数量。
决策集合 Dk（ sk） = { uk | 0 ≤ uk ≤ sk }
4,状态转移方程,sk+1 = 0.7 uk + 0.9（ sk - uk ）
5,定义阶段指标值（函数） vk（ sk,uk） = 8 uk + 5 （ sk - uk ）
45
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
6,定义 fk（ sk）：第 k 年度初拥有的完好机器数量为 sk 时，将其安排（分配）于第 k 至第 5 年中两种负荷下进行生产时所生产的 最大 产量。
7,作出动态规划结构图：
sk sk+1 = 0.7 uk + 0.9（ sk - uk ）
k阶段
fk（ sk）
k+1阶段
fk+1（ sk+1）
max
（? ）
8 uk + 5 （ sk - uk ）
0 ≤ uk ≤ sk
46
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
8,建立动态规划基本方程：（逆序递推方程）
fk（ sk） = max { 8 uk + 5（ sk - uk ） + fk+1（ sk+1） },k= 4,3,2,1
f5（ s5） = max { 8 u5 + 5 （ s5 - u5 ） }
9,逆序递推求解动态规划基本方程。
0≤ uk≤ sk
0≤ u5≤ s5
k = 5
f5（ s5） = max { 8 u5 + 5 （ s5 - u5 ） } = max { 3u5 + 5s5 } = 8s5
0≤ u5≤ s5
u*5（ s5） = s5
47
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 4
f4（ s4） = max { 8 u4 + 5（ s4 - u4 ） + f5（ s5） }
0≤ u4≤ s4
= max { 8 u4 + 5（ s4 - u4 ） + 8s5 }
= max { 8 u4 + 5（ s4 - u4 ） + 8（ 0.7 u4 + 0.9（ s4 - u4 ） }
= max { 1.4 u4 + 12.2 s4 } = 13.6s4 u*4（ s4） = s4
k = 3
f3（ s3） = max { 8 u3 + 5（ s3 - u3 ） + f4（ s4） }
0≤ u3≤ s3
= max { 8 u3 + 5（ s3 - u3 ） + 13.6s4 }
= max { 8 u3 + 5（ s3 - u3 ） + 13.6（ 0.7 u3 + 0.9（ s3 - u3 ） }
= max { 0.28 u3 + 17.24 s3 }≈ 17.5s3 u*3（ s3） = s3
48
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 2
f2（ s2） = max { 8 u2 + 5（ s2 - u2 ） + f3（ s3） }
0≤ u2≤ s2
= max { 8 u2 + 5（ s2 - u2 ） + 17.5s3 }
= max { 8 u2 + 5（ s2 - u2 ） + 17.5（ 0.7 u2 + 0.9（ s2 - u2 ） }
= max {- 2.5 u2 + 20.75 s2 }≈ 20.8s2 u*2（ s2） = 0
k = 1
f1（ s1） = max { 8 u1 + 5（ s1 - u1 ） + f2（ s2） }
0≤ u1≤ s1
= max { 8 u1 + 5（ s1 - u1 ） + 20.8s2 }
= max { 8 u1 + 5（ s1 - u1 ） + 20.8（ 0.7 u1 + 0.9（ s1 - u1 ） }
= max {-1.16 u1 + 23.72 s1 }≈ 23.7s1 u*1（ s1） = 0
49
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
10,顺序确定 最优策略。 p*15 = { u*1,u*2,…,u*5 }
s1=1000 s2=900 s5≈ 397s3=810 s4=567
u*1= 0 u*2= 0 u*3= 810 u*4= 567 u*5= 397
最大产量 f1（ s1=1000） = 23700,五年生产期结束时
（即第六年初还剩余）有完好机器 s6 = 0.7? 397 = 278（台）
50
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用例 3 生产与存储问题某厂经过调查知在未来四个月中每月市场对该厂产品的需求量如表，该厂每批产品的生产准备费（固定成本）为 3 千元，若不生产则为零。每件产品的生产成本（可变成本）为 1千元。该厂最大生产能力为每批不超过 6 件，每件产品每月的库存费用为 0.5 千元，
第一月初该厂没有此产品的库存，并要求第四月末也无库存剩余。
该厂每月初应如何计划产品的生产量及库存量，才能既满足市场对该厂产品的需求又使其总费用最低。 产品需求表
k（月） 1 月 2月 3 月 4 月
dk（需求量）件 2 3 2 4
51
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用建立动态规划模型：
1,阶段 k,第 k月,k = 1,2,3,4
2,状态变量 sk,第 k月初（ k-1月末）的库存量，已知 s1 = s5 = 0。
3,决策变量 uk,第 k月的生产量。
根据条件有,0 ≤ uk ≤ 6,min（ sk+1） ≤ sk+1 ≤ max（ sk+1 ）
4,状态转移方程,sk+1 = sk + uk - dk
因此，决策集合 Dk（ sk） = { uk | 0 ≤ uk ≤ 6,min（ sk+1） ≤ sk+1≤
max（ sk+1 ） } = { uk | max [ 0,dk - sk + min（ sk+1） ] ≤ uk ≤ min
[ 6,dk - sk + max（ sk+1） ] }
52
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
5,阶段指标值（函数）：
vk（ sk,uk） = uk + 3?( uk ) + 0.5sk,其中?( uk ) = 0 当 uk = 0
1 当 uk > 0
6,定义 fk（ sk）：第 k月初库存量为 sk 时，第 k月至第 四月末的最低 总费用。
7,作出动态规划结构图：
sk sk+1 = sk + uk - dk
k 阶段
fk（ sk）
k+1阶段
fk+1（ sk+1）
min
（? ）
uk + 3?( uk ) + 0.5sk
uk? Dk（ sk）
53
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
8,动态方程：（逆序递推方程）
fk（ sk） = min { uk + 3?( uk ) + 0.5sk + fk+1（ sk+1） },k= 4,3,2,1
f5（ s5） = f5（ 0 ） = 0 因为第 5月计划期已结束，没有费用产生了。
uk? Dk（ sk）
9,逆序递推求解动态规划方程。
k = 4,s4 取值集合为 0,1,2,3,4。 因 min s5 = max s5 = 0
D4（ s4） = { u4 | max [ 0,d4 - s4 ] ≤ u4 ≤ min [ 6,d4 - s4 ] }
= {u4 | u4 = d4 - s4 = 4 - s4 }
f4（ s4） = min { u4 + 3?( u4 ) + 0.5s4 + 0 }
54
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
f4（ s4） = min { u4 + 3?( u4 ) + 0.5s4 + 0 }
s4 0 1 2 3 4
u4 4 3 2 1 0
f4（ s4） 7 6.5 6 5.5 2
u*4 4 3 2 1 0
55
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 3,s3 取值集合为 0,1,2,3,4,5,6。
min s4 = 0,max s4 = 4
D3（ s3） = { u3 | max [ 0,d3 - s3 + min（ s4） ] ≤ u3 ≤ min [ 6,d3 –
s3 + max （ s4 ） ] }
= { u3 | max [ 0,2 - s3 ] ≤ u3 ≤ min [ 6,6 - s3 ] }
f3（ s3） = min { u3 + 3?( u3 ) + 0.5s3 + f4（ s4 = s3 + u3 - d3 ） }
56
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
f3（ s3） = min { u3 + 3?( u3 ) + 0.5s3 + f4（ s4 = s3 + u3 - d3 ） }
u3
s3
[ u3 + 3?( u3 ) + 0.5s3 ] + f4（ s4 ） f
3（ s3） u*30 1 2 3 4 5 6
0 5+7 6+6.5 7+6 8+5.5 9+2 11 6
1 4.5+7 5.5+6.5 6.5+6 7.5+5.5 8.5+2 10.5 5
2 1+7 5+6.5 6+6 7+5.5 8+2 8 0
3 1.5+6.5 5.5+6 6.5+5.5 7.5+2 8 0
4 2+6 6+5.5 7+2 8 0
5 2.5+5.5 6.5+2 8 0
6 3+2 5 0
s4 0 1 2 3 4
f4（ s4） 7 6.5 6 5.5 2
57
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 2,s2 取值集合为 0,1,2,3,4。 因 s1=0,u1 ≤ 6,d1=2
min s3 = 0,max s3 = 6
D2（ s2） = { u2 | max [ 0,d2 – s2 + min（ s3） ] ≤ u2 ≤ min [ 6,d2 –
s2 + max （ s3） ] }
= { u2 | max [ 0,3 – s2 ] ≤ u2 ≤ min [ 6,9 – s2 ] }
f2（ s2） = min { u2 + 3?( u2 ) + 0.5s2 + f3（ s3 = s2 + u2 – d2 ） }
58
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
f2（ s2） = min { u2 + 3?( u2 ) + 0.5s2 + f3（ s3 = s2 + u2 – d2 ） }
u2
s2
[ u2 + 3?( u2 ) + 0.5s2 ] + f3（ s3 ） f
2（ s2） u*20 1 2 3 4 5 6
0 6+11 7+10.5 8+8 9+8 16 5
1 5.5+11 6.5+10.5 7.5+8 8.5+8 9.5+8 15.5 4
2 5+11 6+10.5 7+8 8+8 9+8 10+8 15 3
3 1.5+11 5.5+10.5 6.5+8 7.5+8 8.5+8 9.5+8 10.5+5 12.5 0
4 2+10.5 6+8 7+8 8+8 9+8 10+5 12.5 0
S3 0 1 2 3 4 5 6
f3（ s3） 11 10.5 8 8 8 8 5
59
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 1,s1 取值集合为 0 。
min s2 = 0,max s2 = 4
D1（ s1） = { u1 | max [ 0,d1 – s1 + min（ s2） ] ≤ u1 ≤ min [ 6,d1 –
s1 + max （ s2 ） ] }
= { u1 | max [ 0,2 – s1 ] ≤ u1 ≤ min [ 6,6 – s1 ] }
= { u1 | 2 ≤ u1 ≤ 6 }
f1（ s1） = min { u1 + 3?( u1 ) + 0.5s1 + f2（ s2 = s1 + u1 – d1 ） }
60
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
f1（ s1） = min { u1 + 3?( u1 ) + 0.5s1 + f2（ s2 = s1 + u1 – d1 ） }
s1 0 1 2 3 4
f2（ s2） 16 15.5 15 12.5 12.5
u1
s1
[ u1 + 3?( u1 ) + 0.5s1 ] + f2（ s2 ） f
2（ s2） u*22 3 4 5
0 5+16 6+15.5 7+15 8+12.5 20.5 5
61
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
10,顺序确定 最优策略。 p*14 = { u*1,u*2,u*3,u*4 }
s1= 0 s2= 3 s3= 0 s4= 4
u*1= 5 u*2= 0 u*3= 6 u*4= 0
该厂按以上生产与库存方案计划其总费用将是最低的，为
20.5 千元。
62
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用复合系统可靠性问题
p1 p2 pn…
pk表示系统中第 k 个部件的可靠度，即在给定标准下正常工作的概率。根据系统可靠性理论知，提高整个系统可靠性的一种十分有效的方法是采用 冗余 （储备 ——并联）技术。当系统中第 k个部件的冗余数量为 uk时，则系统中第 k个部件的可靠度提高为：
pk（ uk） = 1 -（ 1 - pk） 1+ uk
63
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用复合系统可靠性问题当 系统中第 k 个部件（ 1,2,…,n） 的冗余数量为 uk时，
从而整个系统的可靠度为：
P =? pk（ uk）
下面研究一个简单例子
64
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用复合系统可靠性问题例 一台机器的三个重要部件对整台机器的正常运行起着至关重要的作用，他们的可靠度及成本分别为：
p1 = 0.9,p2 = 0.7,p3 = 0.6；
c1 = 2,c2 = 1,c3 = 3； （ 单位：万元）
如果采用冗余技术来提高整台机器的可靠度，而提供的冗余经费仅有 3 万元，这三个重要部件应该怎样冗余才能使整台机器的可靠度最高。
这实际上是一个 3 万元如何分配使用在这三个重要部件冗余的资源分配问题，其动态规划结构图如下：
65
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
7,动态规划结构图：
sk sk+1 = sk + ckuk
k阶段
fk（ sk）
k+1阶段
fk+1（ sk+1）
max
（? ）
pk（ uk）
0≤ uk ≤ sk /ck
且为整数
8,动态方程：（逆序递推方程）
fk（ sk） = max { [ 1 -（ 1 - pk） 1+ uk ] * fk+1（ sk+1） },k= 3,2,1
f4（ s4） = 1
uk? Dk（ sk）
66
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
9,逆序递推求解动态规划方程。
k = 3 s2 取值集合为,0≤ sk ≤ 3
f3（ s3） = max { [ 1 -（ 1 - p3） 1+ u3 ] * f4（ s4） }
f3（ 0≤ s3 < 3） = max { [ 1 -（ 1 - 0.6） 1 ] * 1 } = 0.6
u*3（ s3 < 3 ） = 0
f3（ s3 = 3 ） = max { [ 1 -（ 1 - 0.6） 1+1 ] * 1 } = 0.84
u*3（ s3 = 3 ） = 1
67
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 2 s2 取值集合为,1,3
f2（ 1） = max （ 1 - 0.3） * f3（ 1）
（ 1 - 0.32） * f3（ 0）
= max 0.7 * 0.6
0.91 * 0.6
=0.546
u*2（ 1） = 1
f2（ 3） = max
（ 1 - 0.3） * f3（ 3）
（ 1 - 0.32） * f3（ 2）
（ 1 - 0.33） * f3（ 1）
（ 1 - 0.34） * f3（ 0）
= max
0.7 * 0.84
0.91 * 0.6
0.973 * 0.6
0.992 * 0.6
=0.595
u*2（ 3） = 3
68
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 1 s1 取值集合为,3
= 0.541= maxf1（ 3） = max
（ 1 - 0.1） * f2（ 3）
（ 1 - 0.12） * f2（ 1）
0.9 * 0.595
0.99 * 0.546
u*1（ 3） = 1
10,顺序确定 最优策略。
s1= 3 s2= 1 s3= 0
u*1= 1 u*2= 1 u*3= 0
69
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用设备更新问题在工业和交通运输企业中，经常会遇到因设备陈旧或部分损坏需要更新的问题。那么，从经济上分析，一台（一批）设备应该使用多少年后进行更新最为恰当，或合理的更新年限是多少？从而使在某一时间内的总收入达到最大（或总成本达到最小）。这是设备更新问题所要研究的。
70
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用设备更新问题的一般性描述：
已知一台设备的效益函数 r（ t），维修费用函数 u（ t），更新费用函数 c（ t），在 n 年内，每年年初都须作出决策，是继续使用
（ Keep）旧设备还是更换（ Replacement）一台新的设备，使在 n
年内总净效益最大。
设,r k（ t） —— 在第 k 年初设备已使用了 t 年（或称役龄为 t年）的设备在第 k 年再使用的效益。
u k（ t） —— 在第 k 年初设备已使用了 t 年时继续使用的第 k 年中的维修费用。
c k（ t） —— 在第 k 年初设备已使用了 t 年时的更新费用。
—— 为折扣因子（ 0 ≤? ≤1），表示一年以后的单位收入的价值视为现年的? 单位。
71
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用建立动态规划模型：
1,阶段 k,表计划使用设备的年数,k=1,2,…,n
2,状态变量 sk,第 k 年初，设备已使用过的年数（役龄 ） 。
3,决策变量 xk,第 k 年初更新设备，或保留使用旧设备。
Dk（ sk） = { xk | xk =R,K}
4,状态转移方程,sk+1 = 1 （当 xk =R ）
sk+1 = sk + 1 （当 xk = K ）
5,阶段指标值（函数）
vk（ sk,xk） =
r k（ sk ） - u k（ sk ） 当 xk = K
r k（ 0） - u k（ 0） - c k（ sk ） 当 xk = R
72
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
6,定义 fk（ sk）：第 k 年初，设备已使用了 sk 年时，第 k 年至第
n 年末的 最大效益 。
7,动态规划结构图：
sk
1
sk + 1
第 k 年第 k+1年第 k+1年f
k（ sk）
fk+1（ 1 ）
fk+1（ sk+ 1）
Max
（ ∑）
73
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
8,动态方程：（逆序递推方程）
fk(sk) = Max
fn+1(sn+1) = 0 k = n-1,…,2,1
9,逆序递推求解动态规划方程。
74
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用例 某台新设备的年效益及年均维修费、更新净费用如表所示。试确定今后 5 年内的更新策略，使总收益最大。（? = 1）
单位：万元役龄项目 0 1 2 3 4 5
效益 r k（ t） 5 4.5 4 3.75 3 2.5
维修费 u k（ t） 0.5 1 1.5 2 2.5 3
更新费 c k（ t） 0.5 1.5 2.2 2.5 3 3.5
75
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 5 s5 取值集合为,1,2,3,4
f5( 1 ) = Max
= Max = 3.5 x*5（ 1） = K
f5( 2 ) = Max = 2.5 x*5（ 2） = K
f5( 3 ) = 2 x*5（ 3） = K
f5( 4 ) = 1.5 x*5（ 4） = R
76
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 4 s4 取值集合为,1,2,3
f4( 1 ) = Max
= Max = 6.5 x*4（ 1） = R
f4( 2 ) = 5.8 x*4（ 2） = R
f4( 3 ) = 5.5 x*4（ 3） = R
77
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 3 s3 取值集合为,1,2
f3( 1 ) = Max
= Max = 9.5 x*3（ 1） = R
f3( 2 ) = Max
= Max = 8.8 x*3（ 2） = R
78
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 2 s2 取值集合为,1
f2( 1 ) = Max
= Max = 12.5 x*2（ 1） = R
79
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用
k = 1 s1 = 0
f1( 0 ) = Max
= Max = 17 x*1（ 0） = K
10,顺序确定 最优策略。
年份 1 2 3 4 5
sk 役龄 0 1 1 1 1
xk决策 K R R R K
80
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介随机动态规划不同于确定型动态规划之处在于其下一阶段的状态不是由当前阶段的状态以及决策完全确定。确切地说。下一阶段的状态是什么，服从一个概率分布。不过，这个概率分布仍由当前阶段的状态以及决策完全确定。由此，我们得到随机动态规划的基本结构。下图给出了这种结构的形象描绘：
81
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介随机动态规划的基本结构图
sk uk
s1k+1
sNk+1
s2k+1
opt
k+1阶段
p1
fk（ sk）
k阶段 p
2
pN
…
v1
v2
vN
…
…
fk+1（ s1k+1 ）
fk+1（ s2k+1 ）
fk+1（ sNk+1 ）
决策
uk? Dk（ sk）
82
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介随机动态规划的基本方程：
fk（ sk） = opt {? pi（ vi+ fk+1（ sik+1 ） ） }
uk? Dk（ sk） i =1
N
fn（ sn） = opt {? pivi }
un? Dn（ sn） i =1
N
k = n-1,…,2，
1
下面我们通过一个例子来具体阐述如何求解动态规划问题请看案例 ——
83
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介某公司相信对一个开发项目进行投资会取得成功。若投资会成功的话，公司就可以获得与投资数额相同的利润，若投资失败的话，
公司非但得不到利润，就连投资也完全不能收回。公司对有关资料详细分析后认为，每次投资 成功的概率为 2/3,失败的概率为 1/3。
目前公司对此项目进行投资的总资金有 3 百万元，为了有效控制投资风险，公司计划分 三次 投入资金（如果有资金的话）。公司需要作出的决策是每次应投入多少资金（以百万元为单位），才能使三次投资结束后公司最终获得 2 百万元利润（即最终拥有 5 百万元总资金）的 概率最大 。
84
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介
1,阶段 k,第 k 次投资,k = 1,2,3
2,状态变量 sk,第 k 次投资时拥有可用于投资的资金数量。
3,决策变量 uk,第 k 次投资的资金数量。
决策集合 Dk（ sk） = { uk | uk = 0,1,2,…,sk }
4,状态转移方程：
sk+1 = sk + uk 第 k 次投资确实成功。s
k - uk 第 k 次投资确实失败。
5,定义阶段指标值（函数）：
成功的概率为 2/3，失败的概率为 1/3。
85
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介
6,定义 fk（ sk ）：第 k 次投资时拥有可用于投资的资金数量 sk,
并一直投资到第 3 次投资结束后公司获得 2 百万元利润的最大概率。
我们应该注意到这样一个事实 —— 即使前两次投资失败了，公司仍然有机会最终赢得 2 百万元的利润。
7,随机动态规划的基本结构图：
sk uk
sk- uk
sk+ uk
k+1阶段
fk（ sk）
k阶段
fk+1（ sk + uk ）决策
uk =0,1,…,sk （? ）
max
fk+1（ sk - uk ）
86
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介
8,随机动态方程：
fk（ sk） = max {（ 2/3） fk+1（ sk + uk ） +（ 1/3） fk+1（ sk - uk ） }
uk =0,1,…,sk
k = 3,2,1
f4（ s4） =△ 0 s4? 5
1 s4 ≥ 5
87
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介
9,逆序递推求解随机动态方程。
k = 3 s3 = 0,1,2,3,4,5,…,12
s3 0 1 2 3 4 ≥5
f3（ s3） 0 0 0 2/3 2/3 1
u*3 … … … 2,3 1,2,3,4 0,≤ s3 - 5
88
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介
k = 2 s2 = 0,1,2,3,4,5,6
u2
s2
（ 2/3） f3（ s2 + u2 ） +（ 1/3） f3（ s2 - u2 ） f
2（ s2） u*20 1 2 3 4
0 0 0 …
1 0 0 0 …
2 0 4/9 4/9 4/9 1,2
3 2/3 4/9 2/3 2/3 2/3 0,2,3
4 2/3 8/9 2/3 2/3 2/3 8/9 1
≥ 5 1 1 0,≤ s3 - 5
89
动态规划 Dynamic Programming（ DP）
动态规划在经济管理中的应用随机动态规划简介
k = 1 s1 = 3
u2
s2
（ 2/3） f2（ s1 + u1 ） +（ 1/3） f2（ s1 – u1 ） f
1（ s1） u*10 1 2 3
3 2/3 20/27 2/3 2/3 20/27 1
于是，我们有最优策略：
s1=3,u*1=1
成功 s2=4,u*2=1
失败 s2=2,u*2=1
u*2=2
成功 s3=5,u*3=0
失败 s3=3,u*3=2 or 3
成功 s3=3 or 4,u*3=2,3 or 1,…,4
失败 s3=1 or 0，投资失败。
90
动态规划 Dynamic Programming（ DP）
第七章结束谢谢！
91
动态规划 Dynamic Programming（ DP）
P225 例 10 限期采购问题某部门欲采购一批原料，原料价格在五周内可能有所变动，
已预测得该种原料今后五周内取不同单价的概率如下表所示。
试确定该部门在五周内购进这批原料的最优策略，使采购价格的期望值最小。
原料价格（元） 概率
500
600
700
0.3
0.3
0.4
92
动态规划 Dynamic Programming（ DP）
1、阶段 k = 1,2,3,4,5
2、状态变量 sk,第 k 周的原料实际价格。
3、决策变量 uk,第 k 周的采购决策，若采购则 uk = 1，若不采购则 uk = 0。
4、阶段
