1
动态规划
2
基本概念多阶段决策问题,
此问题系统的动态过程可以按照时间的进程分为若干个相互联系的 阶段,而在每一个阶段中，具有一个或多个 状态,在每一个阶段中都要针对每一个状态作出 决策 。这样，
在各阶段的决策确定以后，就顺序构成一个决策序列，称为一个 策略 。
3
阶段和阶段变量,阶段是按照总决策进行的时间或空间的先后顺序来划分，用 K表示,K为阶段变量。
状态和状态变量,状态描述系统所处的状态或位置。
阶段状态应具有“无后效性”，即过程的历史只能通过当前的状态去影响它的未来，每一阶段（ k ）
状态分为初始状态（ sk）和终止状态（ sk+1），前一阶段的终止状态是后一阶段的初始状态。
状态可能集 Sk,sk?Sk
4
决策变量和策略,xk表示第 k阶段的决策。
决策变量序列称为策略全过程策略 （ x1,...,xn）
子策略 （ xm,xm+1,...,xn）
5
状态转移方程,把过程由一个状态变到另一个状态的变化叫做状态转移。
sk，选择决策 xk（ sk）的产生的结果，便转移到 sk+1，记为 sk+1=Tk（ sk,xk）
若 Tk（ sk,xk） =0，则称 sk为终止状态。
6
阶段效益函数,sk，执行决策 xk时，不仅带来系统状态的转移，也必然要影响决策目标，
对应这个决策的效果值，叫做效益函数，记为 rk（ sk,xk ）
7
效益函数,多阶段决策过程关于目标的总效益，在
“无后效性”的条件下，由各阶段效益累计而成。
Rk= rk（ sk,xk ） ⊙ rk+1（ sk+1,xk+1 ） ⊙?
⊙ rn（ sn,xn ） k=1,…,n
即 k子系统的效益。
⊙ 表示某种运算（ +,-,*等）
8
当 k=1时,R*表示总目标效益函数的最优值。
R*=r1（ s1,x1*） ⊙ r2（ s2,x2*） ⊙?
⊙ rn（ sn,xn*）
（ x1*,x2*,…,xn*） 称为最优策略
fk（ sk） =opt{rk（ sk,xk*） ⊙ rk+1（ sk+1,xk+1*）
⊙?⊙ rn（ sn,xn*） }
fk（ sk）,由第 k阶段的状态 sk到终点的最优效益值。
当 k=1，且 s1唯一时,R*=f1（ s1）
9
当 ⊙ 为,+” 时，
fk（ sk） =opt{rk（ sk,xk*） + rk+1（ sk+1,xk+1*）
+?+ rn（ sn,xn*） }
-----贝尔曼函数
10
最优化原理,若（ x1*,…,xn*）是初始状态
s1? S1的最优策略，则其一部分
（ xk*,xk+1*,…,xn*） 1≤k≤n对于它的初始状态 sk? Sk而言也构成一个最优策略，或称：
最优策略的任何一部分子策略也是相应初始状态的最优策略。
证明（反证法）
11
最短路线问题
EX:
1
2
3 6
4 7
8
9
10
5
2
4
5
7
46
3
24
4 1
5
1
4
6
3
3
3
3
4
A B
k=1 k=2 k=3 k=4
12
K— 阶段变量
sk— 状态变量 S2={②,③,④ }
xk— 决策变量，即当状态为 sk时，可选择的下一状态,xk=sk+1
rk（ sk,xk） — 从 sk到 sk+1的距离
fk（ sk） — 由 sk到终点的最短距离采用逆推的方法求解
13
k=4
f4（ 8） =r4（ 8,10） =3
f4（ 9） =r4（ 9,10） =4
k=3
f3（ s3） =min{r3（ s3,x3） +f4（ s4） }
f3（ 5） =min r3（ 5,8） +f4（ 8）
r3（ 5,9） +f4（ 9）
f3（ 6） =7
f3（ 7） =6
1
2
3 6
4 7
8
9
10
5
2 4
5
7
46
324
4 1
5
1
4
63
3
3
3
4
A B
k=1 k=2 k=3 k=4解
14
k=2
f2（ s2） =min{r2（ s2,x2） +f3（ s3） }
f2（ 2） =min{r2（ 2,5） +f3（ 5），
r2（ 2,6） +f3（ 6），
r2（ 2,7） +f3（ 7） }
=min{7+4,4+7,6+6}=11
f2（ 3） =7
f2（ 4） =8
1
2
3 6
4 7
8
9
10
5
2 4
5
7
46
324
4 1
5
1
4
63
3
3
3
4
A B
k=1 k=2 k=3 k=4
15
k=1
f1（ s1） =min{r1（ s1,x1） +f2（ s2） }
f1（ 1） =min{r1（ 1,2） +f2（ 2），
r1（ 1,3） +f2（ 3），
r1（ 1,4） +f2（ 4） }
=min{2+11,4+7,3+8}=11
f1（ 1） =r1（ 1,3） +f2（ 3）
f2（ 3） =r2（ 3,5） +f3（ 5）
f3（ 5） =r3（ 5,8） +f4（ 8）
f4（ 8） =r4（ 8,10）
1 3 5 8 10
4 6 9
1
2
3 6
4 7
8
9
10
5
2 4
5
7
46
324
4 1
5
1
4
63
3
3
3
4
A B
k=1 k=2 k=3 k=4
16
动态规划模型一、动态规划模型
fk（ sk） =opt{ ri（ si,xi） }
=opt{rk（ sk,xk） +opt ri（ si,xi）
= opt{rk（ sk,xk） +fk+1（ sk+1） }
n
∑
i=k
n
∑
i=k+1
}
17
fn+1（ sn+1） =0
fk（ sk） =opt{rk（ sk,xk） +fk+1（ sk+1） }
sk+1=Tk（ sk,xk）
递归方程
18
二、步骤
1、划分阶段 k
2、确定 xk,sk,Rk,R1
3、建立 Tk
4、建立递归方程
5、由递归方程求出 R1*和最优决策
19
练习
A
B1
D
C2
C1
B3
B2
30
20
10
40
30
30
20
50 50
50
60
A B2 C1 D
C2
D
20
投资分配问题
c：投资者拥有资金量
n,n个投资机会
xk：预知投放到第 k个投资机会的资金
gk（ xk）：可获取利润
21
确定一方案能从全部的投资中得到最大收益。
一般模型,maxR= gk（ xk）
xk≤c,xk≥0,k=1,?,
n
n
∑
k=1n
∑
k=1
22
该类问题的动态规划模型：
sk：第 k阶段资金拥有量,0≤sk≤c
xk：第 k个投资机会的资金投放量，
0≤xk≤sk
fn+1（ sn+1） =0
fk（ sk） =max{gk（ xk） +fk+1（ sk+1） }
sk+1=sk-xk k=n,n-1,…,1
23
EX：某公司拟将 500万元资金用于 3个项目的投资，
预计收益如下，问该公司应如何选择投资方案，使总投资期望收益最大？
-12116403
1211.51110502
-1297301
543210投资收益项目
24
解模型,
f4（ s4） =0
fk（ sk） =max{gk（ xk） +fk+1（ sk+1） }
sk+1=sk-xk
0≤x1≤4
0≤x2≤5
0≤x3≤4
25
k=3
f3（ s3） =max{g3（ x3） }
S3={0,1,2,3,4,5}
4
12
4
43210X3*（ s3）
1211640F3（ s3）
53210S3
26
k=2
f2（ s2） =max{g2（ x2） + f3（ s2-x2） }
S2={0,1,2,3,4,5}
f2（ 0） =0,x2*（ 0） =0
.
.
.
27
1,2
16
4
22210x2*（ s2）
21141050f2（ s2）
53210S2
28
k=1
f1（ s1） =max{g1（ x1） +f2（ s1-x1） }
（ x1*,x2*,x3*） =（ 0,2,3）或（ 2,2,1）
R*=21
0,2x1*（ s1）
21f1（ s1）
5s1
29
生产 -库存问题生产成本和库存费构成产品成本的主体产量 生产成本,库存费产量 生产成本,库存费如何调节产量
30
生产阶段,n （月份，季度）
期初库存,s1
第 k阶段市场需求量,qk （ k=1,2,…,n）
阶段生产固定费用,F （不生产时 F=0）
单位产品变动费用,c
单位产品阶段库存费用,P
仓库容量,M
阶段生产能力,Bk
第 k阶段期初库存量,sk 0≤sk≤min{M,qi}
第 k阶段产量,xk qk-sk≤xk≤min{Bk,qi -sk}
n
∑
i=k
n
∑
i=k
31
问：如何安排生产，才能既满足市场需求，又能使计划期内总费用最小？
状态转移方程,sk+1=sk+xk-qk
rk（ sk,xk） = Psk xk=0
F+cxk+Psk xk>0
R= rk（ sk,xk）
fk（ sk）,k阶段期初库存量为 sk时，执行最优生产 -库存计划的最小费用。
n
∑
k=1
32
列出模型：
fn+1（ sn+1） =0
fk（ sk） =max{rk（ xk） +fk+1（ sk+1） }
sk+1=sk+xk- qk k=n,n-1,…,1
33
EX
某厂在年初预计，今年四个季度中市场对该厂某种产品的需求量如下：
季度 n 需求量 qk
1 2
2 3
3 4
4 2
34
该厂各季度的生产能力如下：
季度 n 生产能力 Bk
1 6
2 4
3 5
4 4
35
每季固定费用 3（万元），变动成本 1（万元），库存费 0.5（万元） /台，仓库容量 3台，
计划期初及第四季末的库存量为零。试建立这四个季度的最优生产计划。
36
解,xk,第 k季产量
sk,第 k季期初库存
qk,第 k季需求量
（ k=1,2,3,4）
sk+1= sk + xk - qk
rk（ sk,xk ） = 3+ xk +0.5 sk xk >0
0.5 sk xk =0
37
模型
f5（ s5） =0
fk（ sk） =min{rk（ sk,xk） +fk+1（ sk+1） }
sk+1=sk+xk-qk
s.t,qk-sk≤xk≤min{Bk,qk+qk+1+…+q n-sk}
0≤sk≤min{3,qk+…+q n}
38
k=4
f4(s4)=min{r4(s4,x4)}
S4={0,1,2} (q4=2,B4=4)
f4(0)=5 x4 *(0)=2
f4(1)=4.5 x4 *(1)=1
f4(2)=1 x4 *(2)=0
季度 n 需求量 qk
1 2
2 3
3 4
4 2
季度 n 生产能力 Bk
1 6
2 4
3 5
4 4
39
k=3
f3(s3)=min{r3(s3,x3)+f4(s4)}
S3={0,1,2,3} (q3=4,B3=5)
f3(0)=12 x3*(0)=4
f3(1)=9.5 x3*(1)=5
f3(2)=9 x3*(2)=4
f3(3)=8.5 x3*(3)=3
季度 n 需求量 qk
1 2
2 3
3 4
4 2
季度 n 生产能力 Bk
1 6
2 4
3 5
4 4
40
k=2
f2(s2)=min{r2(s2,x2)+f3(s3)}
S2={0,1,2,3} (q2=3,B2=4)
f2(0)=16.5 x2*(0)=4
f2(1)=16 x2*(1)=3
f2(2)=15.5 x2*(2)=2
f2(3)=13.5 x2*(3)=0
季度 n 需求量 qk
1 2
2 3
3 4
4 2
季度 n 生产能力 Bk
1 6
2 4
3 5
4 4
41
k=1
f1(s1)=min{r1(s1,x1)+f2(s2)}
S1={0} (q1=2,B1=6) x1≥2
r1(0,2)+f2(0)
f1(0)=min r1(0,3)+f2(1) = 21.5
r1(0,4)+f2(2)
r1(0,5)+f2(3)
x1*(0)=2,5
季度 n 需求量 qk
1 2
2 3
3 4
4 2
季度 n 生产能力 Bk
1 6
2 4
3 5
4 4
42
(x1*,x2*,x3*,x4*)=(2,4,5,0)
或 (x1*,x2*,x3*,x4*)=(5,0,4,2)
R*=f1(0)=21.5
43
练习某公司拟将 4百万元资金用于 A,B,C三项目的追加投资，各项目效益值如下表，问怎样分配资金才能使总收益最大？
38 41 48 60 66
40 42 50 60 65
38 64 68 70 70
A
B
C
0 1 2 3 4投资额项目
Key,3 0 1 164
44
练习答案建立该问题的动态规划模型如下：
f4(s4)=0
fk(sk)=max{gk(xk)+fk+1(sk+1)}
sk+1=sk-xk k=3,2,1。
45
k=3,S3={0,1,2,3,4}
s3 0 1 2 3 4
f3（ s3） 38 64 68 70 70
x3*(s3) 0 1 2 3 4
38 41 48 60 66
40 42 50 60 65
38 64 68 70 70
A
B
C
0 1 2 3 4投资额项目
46
k=2,S2={0,1,2,3,4}
f2(0)=max{g2(0)+f3(0)}=78,x2*(0)=0
f2(1)=max g2(0)+f3(1)
g2(1)+f3(0) =104,x2*(1)=0
f2(2)=max g2(0)+f3(2)
g2(1)+f3(1) =108,x2*(2)=0
g2(2)+f3(0)
38 41 48 60 66
40 42 50 60 65
38 64 68 70 70
A
B
C
0 1 2 3 4投资额项目
47
f2(3)=max g2(0)+f3(3)
g2(1)+f3(2)
g2(2)+f3(1) =114 x2*(3)=2
g2(3)+f3(0)
f2(4)=max g2(0)+f3(4)
g2(1)+f3(3)
g2(2)+f3(2) =124 x2*(4)=3
g2(3)+f3(1)
g2(4)+f3(0)
s2 0 1 2 3 4
f2（ s2） 78 104 108 114 124
x2*(s2) 0 0 0 2 3
48
k=1,S1={4}
f1(4)=max g1(0)+f2(4)
g1(1)+f2(3)
g1(2)+f2(2) =164,x1*(4)=3
g1(3)+f2(1)
g1(4)+f2(0)
(x1*,x2*,x3*)=(3,0,1) 164
49
载货问题设有一艘装载 N种货物的船，其最大载重量为
W，已知第 i种货物的单位重量为 wi，价值为 ri
（ i=1,…,N），求装载货物价值最大的动态规划模型。
xk：第 k种货物的数量 0≤xk≤[W/wk]
sk：载第 k种货前的剩余载重量 s1=W
sk+1=sk-wkxk 0≤sk≤sk-1
50
模型：
sk+1=sk-wkxk
fk(sk)=max{rk(sk,xk)+fk+1(sk+1)}
fn+1(sn+1)=0 k=1,2,…,n
51
解如下形式的数学规划问题
EX:动态规划求解非线性规划
maxZ=x12+x22+x32+x42
x1+x2+x3+x4=10
xj≥0 且为整数 (j=1,2,3,4)
52
随机型动态规划确定型：某阶段作出决策后，由这个决策所产生的状态是唯一确定的。
随机型,s
k xk
1
2
n
p1 p
2
pn
…
Sk+1取,,…,1 2 n
53
分布函数：
F(sk,1,xk)=p1,…,F(s k,n,xk)=pn
0≤pi≤1 pi=1
目标函数 期望益损
fn+1(sn+1)=0
fk(sk)=opt{ [rk(sk,i,xk)+fk+1(i)]pi(xk)}
n
∑
i=1
n
∑
i=1
54
随机进货计划
EX：某商店经销一种时令商品，预计该季度前两月的销售量 Q1和 Q2是概率已知的随机变量，
P（ Q1 =10） =0.4,P（ Q1=20） =0.6,P
（ Q2 =10） =0.6,P（ Q2 =20） =0.4,每月初进货，仓库容量为 30，两个月的进货价分别为 1.1和 1，售价分别为 1.8和 1.6，前两个月未售完的存货将在第三个月以单价 0.8削价处理，且全部售完。问商店如何制订进货计划，
使三个月的期望毛利最大。
55
解,k=3，每一阶段确定每一月的进货量
xk：第 k月的进货量 x3=0
sk：第 k月初库存量
sk+1=sk+xk-Qk （ Qk为随机变量） s4=0
r1（ s1,i,x1） =1.8Q1-1.1x1
r2（ s2,i,x2） =1.6Q2-x2
56
方程：
f4(s4)=0
fk(sk)=max{ [ rk(sk,i,xk)+fk+1(i)]pi(xk)}
k=3
s3={0,10,20} x3*=0
f3(s3)=0.8s3
f3(0)=0
f3(10)=8
f3(20)=16
2
∑
i=1
57
k=2
s2={0,10,20} x2 ∈ {0,10,20}
f2(s2)=max{ [ r2(s2,i,x2)+f3(i)]pi(x2)}
=max{ [1.6Q2-x2+0.8s3]pi(x2)}
0
f2(0)=max 1.6*10-10
[1.6*10-20+f3(10)]*0.6+[(1.6*20-20+f3 (0))]*0.4
0
=max 6 =7.2
7.2
x2*(0)=20
2∑
i=1
2∑
i=1
58
1.6*10-0+0
f2(10)=max [(1.6*10-10+f3(10)]*0.6+[(1.6*20-10+f3(0)]*0.4
[(1.6*10-20+f3(20)]*0.6+[(1.6*20-20+f3(10)]*0.4
16
=max 17.2 =17.2
15.2
x2*(10)=10
f2(20)=max [(1.6*10+f3(10)]*0.6+[(1.6*20-0+0)]*0.4
[(1.6*10-10+f3(20)]*0.6+[(1.6*20-10+f3(10)]*0.4
=27.2
x2*(20)=0
59
k=1
s1={0} x1={0,10,20,30}
f1(0)=max{[1.8Q1-1.1x1+f2(s2)]pi(x1)}
f2(0)
f1(0)=max 1.8*10-1.1*10+f2(0)
[1.8*10-1.1*20+f2(10)]*0.4+[1.8*20-1.1*20+f2(0)*0.6
[1.8*10-1.1*30+f2(20)]*0.4+[1.8*20-1.1*30+f2(10)*0.6
7.2
=max 14.2 =18
18.0
17
x1*(0)=20
60
x1*=20
若第 1月份销量为 10，则 s2=10,x2*=10
若第 1月份销量为 20，则 s2=0,x2*=20
61
不确定采购问题
EX：某厂生产上需要在近五周内采购一批原料，估计在未来五周内价格有波动，其浮动价格和概率如表，试求在哪一周以什么价格购入，使其采购价格的数学期望最小，并求期望值。
单价 概率
500
600
700
0.3
0.3
0.4
62
xk= 1 采购
0 不采购
sk：第 k周实际价格
skE：第 k周决定等待，在以后采取最优决策时采购价格的期望值
fk（ sk）：第 k周实际价格为 sk时，从第 k周到第 5周采取最优决策所得的最小期望值
fk（ sk)=min{sk,skE} sk属于 Sk
f5(s5)=s5
skE=Efk+1(sk+1)=0.3fk+1(500)+0.3fk+1(600)+0.4fk+1(700)
63
k=5
f5(s5)=s5 第 5周无论市价如何，必须采购
f5(500)=500
f5(600)=600
f5(700)=700
k=4
s4E=0.3f5(500)+0.3f5(600)+0.4f5(700)=610
f4(s4)=min{s4,s4E}=min{s4,610}
500 s4=500
= 600 s4=600
610 s4=700
x4= 1 s4=500,600
0 s4=700
64
k=3
f3(s3)=min{s3,574}= 500 s3=500
574 s3=600,700
x3= 1 s3=500
0 s3=600,700
k=2
f2(s2)=min{s2,551.8}= 500 s2=500
551.8 s2=600,700
x2= 1 s2=500
0 s2=600,700
65
k=1
f1(s1)=min{s1,536.26}= 500 s1=500
536.26 s1=600,700
x1= 1 s1=500
0 s1=600,700
66
最优采购决策：
1,2,3周时，价格为 500采购，否则等待
4周时，价格为 500或 600采购，否则等待
5周时，必须购
500*0.3(1+0.7+0.72+0.73+0.73*0.4)
+600*0.3(0.73+0.4*0.73)
+700*0.42*0.73
=525.382
67
本章结束！
动态规划
2
基本概念多阶段决策问题,
此问题系统的动态过程可以按照时间的进程分为若干个相互联系的 阶段,而在每一个阶段中，具有一个或多个 状态,在每一个阶段中都要针对每一个状态作出 决策 。这样，
在各阶段的决策确定以后，就顺序构成一个决策序列，称为一个 策略 。
3
阶段和阶段变量,阶段是按照总决策进行的时间或空间的先后顺序来划分，用 K表示,K为阶段变量。
状态和状态变量,状态描述系统所处的状态或位置。
阶段状态应具有“无后效性”，即过程的历史只能通过当前的状态去影响它的未来，每一阶段（ k ）
状态分为初始状态（ sk）和终止状态（ sk+1），前一阶段的终止状态是后一阶段的初始状态。
状态可能集 Sk,sk?Sk
4
决策变量和策略,xk表示第 k阶段的决策。
决策变量序列称为策略全过程策略 （ x1,...,xn）
子策略 （ xm,xm+1,...,xn）
5
状态转移方程,把过程由一个状态变到另一个状态的变化叫做状态转移。
sk，选择决策 xk（ sk）的产生的结果，便转移到 sk+1，记为 sk+1=Tk（ sk,xk）
若 Tk（ sk,xk） =0，则称 sk为终止状态。
6
阶段效益函数,sk，执行决策 xk时，不仅带来系统状态的转移，也必然要影响决策目标，
对应这个决策的效果值，叫做效益函数，记为 rk（ sk,xk ）
7
效益函数,多阶段决策过程关于目标的总效益，在
“无后效性”的条件下，由各阶段效益累计而成。
Rk= rk（ sk,xk ） ⊙ rk+1（ sk+1,xk+1 ） ⊙?
⊙ rn（ sn,xn ） k=1,…,n
即 k子系统的效益。
⊙ 表示某种运算（ +,-,*等）
8
当 k=1时,R*表示总目标效益函数的最优值。
R*=r1（ s1,x1*） ⊙ r2（ s2,x2*） ⊙?
⊙ rn（ sn,xn*）
（ x1*,x2*,…,xn*） 称为最优策略
fk（ sk） =opt{rk（ sk,xk*） ⊙ rk+1（ sk+1,xk+1*）
⊙?⊙ rn（ sn,xn*） }
fk（ sk）,由第 k阶段的状态 sk到终点的最优效益值。
当 k=1，且 s1唯一时,R*=f1（ s1）
9
当 ⊙ 为,+” 时，
fk（ sk） =opt{rk（ sk,xk*） + rk+1（ sk+1,xk+1*）
+?+ rn（ sn,xn*） }
-----贝尔曼函数
10
最优化原理,若（ x1*,…,xn*）是初始状态
s1? S1的最优策略，则其一部分
（ xk*,xk+1*,…,xn*） 1≤k≤n对于它的初始状态 sk? Sk而言也构成一个最优策略，或称：
最优策略的任何一部分子策略也是相应初始状态的最优策略。
证明（反证法）
11
最短路线问题
EX:
1
2
3 6
4 7
8
9
10
5
2
4
5
7
46
3
24
4 1
5
1
4
6
3
3
3
3
4
A B
k=1 k=2 k=3 k=4
12
K— 阶段变量
sk— 状态变量 S2={②,③,④ }
xk— 决策变量，即当状态为 sk时，可选择的下一状态,xk=sk+1
rk（ sk,xk） — 从 sk到 sk+1的距离
fk（ sk） — 由 sk到终点的最短距离采用逆推的方法求解
13
k=4
f4（ 8） =r4（ 8,10） =3
f4（ 9） =r4（ 9,10） =4
k=3
f3（ s3） =min{r3（ s3,x3） +f4（ s4） }
f3（ 5） =min r3（ 5,8） +f4（ 8）
r3（ 5,9） +f4（ 9）
f3（ 6） =7
f3（ 7） =6
1
2
3 6
4 7
8
9
10
5
2 4
5
7
46
324
4 1
5
1
4
63
3
3
3
4
A B
k=1 k=2 k=3 k=4解
14
k=2
f2（ s2） =min{r2（ s2,x2） +f3（ s3） }
f2（ 2） =min{r2（ 2,5） +f3（ 5），
r2（ 2,6） +f3（ 6），
r2（ 2,7） +f3（ 7） }
=min{7+4,4+7,6+6}=11
f2（ 3） =7
f2（ 4） =8
1
2
3 6
4 7
8
9
10
5
2 4
5
7
46
324
4 1
5
1
4
63
3
3
3
4
A B
k=1 k=2 k=3 k=4
15
k=1
f1（ s1） =min{r1（ s1,x1） +f2（ s2） }
f1（ 1） =min{r1（ 1,2） +f2（ 2），
r1（ 1,3） +f2（ 3），
r1（ 1,4） +f2（ 4） }
=min{2+11,4+7,3+8}=11
f1（ 1） =r1（ 1,3） +f2（ 3）
f2（ 3） =r2（ 3,5） +f3（ 5）
f3（ 5） =r3（ 5,8） +f4（ 8）
f4（ 8） =r4（ 8,10）
1 3 5 8 10
4 6 9
1
2
3 6
4 7
8
9
10
5
2 4
5
7
46
324
4 1
5
1
4
63
3
3
3
4
A B
k=1 k=2 k=3 k=4
16
动态规划模型一、动态规划模型
fk（ sk） =opt{ ri（ si,xi） }
=opt{rk（ sk,xk） +opt ri（ si,xi）
= opt{rk（ sk,xk） +fk+1（ sk+1） }
n
∑
i=k
n
∑
i=k+1
}
17
fn+1（ sn+1） =0
fk（ sk） =opt{rk（ sk,xk） +fk+1（ sk+1） }
sk+1=Tk（ sk,xk）
递归方程
18
二、步骤
1、划分阶段 k
2、确定 xk,sk,Rk,R1
3、建立 Tk
4、建立递归方程
5、由递归方程求出 R1*和最优决策
19
练习
A
B1
D
C2
C1
B3
B2
30
20
10
40
30
30
20
50 50
50
60
A B2 C1 D
C2
D
20
投资分配问题
c：投资者拥有资金量
n,n个投资机会
xk：预知投放到第 k个投资机会的资金
gk（ xk）：可获取利润
21
确定一方案能从全部的投资中得到最大收益。
一般模型,maxR= gk（ xk）
xk≤c,xk≥0,k=1,?,
n
n
∑
k=1n
∑
k=1
22
该类问题的动态规划模型：
sk：第 k阶段资金拥有量,0≤sk≤c
xk：第 k个投资机会的资金投放量，
0≤xk≤sk
fn+1（ sn+1） =0
fk（ sk） =max{gk（ xk） +fk+1（ sk+1） }
sk+1=sk-xk k=n,n-1,…,1
23
EX：某公司拟将 500万元资金用于 3个项目的投资，
预计收益如下，问该公司应如何选择投资方案，使总投资期望收益最大？
-12116403
1211.51110502
-1297301
543210投资收益项目
24
解模型,
f4（ s4） =0
fk（ sk） =max{gk（ xk） +fk+1（ sk+1） }
sk+1=sk-xk
0≤x1≤4
0≤x2≤5
0≤x3≤4
25
k=3
f3（ s3） =max{g3（ x3） }
S3={0,1,2,3,4,5}
4
12
4
43210X3*（ s3）
1211640F3（ s3）
53210S3
26
k=2
f2（ s2） =max{g2（ x2） + f3（ s2-x2） }
S2={0,1,2,3,4,5}
f2（ 0） =0,x2*（ 0） =0
.
.
.
27
1,2
16
4
22210x2*（ s2）
21141050f2（ s2）
53210S2
28
k=1
f1（ s1） =max{g1（ x1） +f2（ s1-x1） }
（ x1*,x2*,x3*） =（ 0,2,3）或（ 2,2,1）
R*=21
0,2x1*（ s1）
21f1（ s1）
5s1
29
生产 -库存问题生产成本和库存费构成产品成本的主体产量 生产成本,库存费产量 生产成本,库存费如何调节产量
30
生产阶段,n （月份，季度）
期初库存,s1
第 k阶段市场需求量,qk （ k=1,2,…,n）
阶段生产固定费用,F （不生产时 F=0）
单位产品变动费用,c
单位产品阶段库存费用,P
仓库容量,M
阶段生产能力,Bk
第 k阶段期初库存量,sk 0≤sk≤min{M,qi}
第 k阶段产量,xk qk-sk≤xk≤min{Bk,qi -sk}
n
∑
i=k
n
∑
i=k
31
问：如何安排生产，才能既满足市场需求，又能使计划期内总费用最小？
状态转移方程,sk+1=sk+xk-qk
rk（ sk,xk） = Psk xk=0
F+cxk+Psk xk>0
R= rk（ sk,xk）
fk（ sk）,k阶段期初库存量为 sk时，执行最优生产 -库存计划的最小费用。
n
∑
k=1
32
列出模型：
fn+1（ sn+1） =0
fk（ sk） =max{rk（ xk） +fk+1（ sk+1） }
sk+1=sk+xk- qk k=n,n-1,…,1
33
EX
某厂在年初预计，今年四个季度中市场对该厂某种产品的需求量如下：
季度 n 需求量 qk
1 2
2 3
3 4
4 2
34
该厂各季度的生产能力如下：
季度 n 生产能力 Bk
1 6
2 4
3 5
4 4
35
每季固定费用 3（万元），变动成本 1（万元），库存费 0.5（万元） /台，仓库容量 3台，
计划期初及第四季末的库存量为零。试建立这四个季度的最优生产计划。
36
解,xk,第 k季产量
sk,第 k季期初库存
qk,第 k季需求量
（ k=1,2,3,4）
sk+1= sk + xk - qk
rk（ sk,xk ） = 3+ xk +0.5 sk xk >0
0.5 sk xk =0
37
模型
f5（ s5） =0
fk（ sk） =min{rk（ sk,xk） +fk+1（ sk+1） }
sk+1=sk+xk-qk
s.t,qk-sk≤xk≤min{Bk,qk+qk+1+…+q n-sk}
0≤sk≤min{3,qk+…+q n}
38
k=4
f4(s4)=min{r4(s4,x4)}
S4={0,1,2} (q4=2,B4=4)
f4(0)=5 x4 *(0)=2
f4(1)=4.5 x4 *(1)=1
f4(2)=1 x4 *(2)=0
季度 n 需求量 qk
1 2
2 3
3 4
4 2
季度 n 生产能力 Bk
1 6
2 4
3 5
4 4
39
k=3
f3(s3)=min{r3(s3,x3)+f4(s4)}
S3={0,1,2,3} (q3=4,B3=5)
f3(0)=12 x3*(0)=4
f3(1)=9.5 x3*(1)=5
f3(2)=9 x3*(2)=4
f3(3)=8.5 x3*(3)=3
季度 n 需求量 qk
1 2
2 3
3 4
4 2
季度 n 生产能力 Bk
1 6
2 4
3 5
4 4
40
k=2
f2(s2)=min{r2(s2,x2)+f3(s3)}
S2={0,1,2,3} (q2=3,B2=4)
f2(0)=16.5 x2*(0)=4
f2(1)=16 x2*(1)=3
f2(2)=15.5 x2*(2)=2
f2(3)=13.5 x2*(3)=0
季度 n 需求量 qk
1 2
2 3
3 4
4 2
季度 n 生产能力 Bk
1 6
2 4
3 5
4 4
41
k=1
f1(s1)=min{r1(s1,x1)+f2(s2)}
S1={0} (q1=2,B1=6) x1≥2
r1(0,2)+f2(0)
f1(0)=min r1(0,3)+f2(1) = 21.5
r1(0,4)+f2(2)
r1(0,5)+f2(3)
x1*(0)=2,5
季度 n 需求量 qk
1 2
2 3
3 4
4 2
季度 n 生产能力 Bk
1 6
2 4
3 5
4 4
42
(x1*,x2*,x3*,x4*)=(2,4,5,0)
或 (x1*,x2*,x3*,x4*)=(5,0,4,2)
R*=f1(0)=21.5
43
练习某公司拟将 4百万元资金用于 A,B,C三项目的追加投资，各项目效益值如下表，问怎样分配资金才能使总收益最大？
38 41 48 60 66
40 42 50 60 65
38 64 68 70 70
A
B
C
0 1 2 3 4投资额项目
Key,3 0 1 164
44
练习答案建立该问题的动态规划模型如下：
f4(s4)=0
fk(sk)=max{gk(xk)+fk+1(sk+1)}
sk+1=sk-xk k=3,2,1。
45
k=3,S3={0,1,2,3,4}
s3 0 1 2 3 4
f3（ s3） 38 64 68 70 70
x3*(s3) 0 1 2 3 4
38 41 48 60 66
40 42 50 60 65
38 64 68 70 70
A
B
C
0 1 2 3 4投资额项目
46
k=2,S2={0,1,2,3,4}
f2(0)=max{g2(0)+f3(0)}=78,x2*(0)=0
f2(1)=max g2(0)+f3(1)
g2(1)+f3(0) =104,x2*(1)=0
f2(2)=max g2(0)+f3(2)
g2(1)+f3(1) =108,x2*(2)=0
g2(2)+f3(0)
38 41 48 60 66
40 42 50 60 65
38 64 68 70 70
A
B
C
0 1 2 3 4投资额项目
47
f2(3)=max g2(0)+f3(3)
g2(1)+f3(2)
g2(2)+f3(1) =114 x2*(3)=2
g2(3)+f3(0)
f2(4)=max g2(0)+f3(4)
g2(1)+f3(3)
g2(2)+f3(2) =124 x2*(4)=3
g2(3)+f3(1)
g2(4)+f3(0)
s2 0 1 2 3 4
f2（ s2） 78 104 108 114 124
x2*(s2) 0 0 0 2 3
48
k=1,S1={4}
f1(4)=max g1(0)+f2(4)
g1(1)+f2(3)
g1(2)+f2(2) =164,x1*(4)=3
g1(3)+f2(1)
g1(4)+f2(0)
(x1*,x2*,x3*)=(3,0,1) 164
49
载货问题设有一艘装载 N种货物的船，其最大载重量为
W，已知第 i种货物的单位重量为 wi，价值为 ri
（ i=1,…,N），求装载货物价值最大的动态规划模型。
xk：第 k种货物的数量 0≤xk≤[W/wk]
sk：载第 k种货前的剩余载重量 s1=W
sk+1=sk-wkxk 0≤sk≤sk-1
50
模型：
sk+1=sk-wkxk
fk(sk)=max{rk(sk,xk)+fk+1(sk+1)}
fn+1(sn+1)=0 k=1,2,…,n
51
解如下形式的数学规划问题
EX:动态规划求解非线性规划
maxZ=x12+x22+x32+x42
x1+x2+x3+x4=10
xj≥0 且为整数 (j=1,2,3,4)
52
随机型动态规划确定型：某阶段作出决策后，由这个决策所产生的状态是唯一确定的。
随机型,s
k xk
1
2
n
p1 p
2
pn
…
Sk+1取,,…,1 2 n
53
分布函数：
F(sk,1,xk)=p1,…,F(s k,n,xk)=pn
0≤pi≤1 pi=1
目标函数 期望益损
fn+1(sn+1)=0
fk(sk)=opt{ [rk(sk,i,xk)+fk+1(i)]pi(xk)}
n
∑
i=1
n
∑
i=1
54
随机进货计划
EX：某商店经销一种时令商品，预计该季度前两月的销售量 Q1和 Q2是概率已知的随机变量，
P（ Q1 =10） =0.4,P（ Q1=20） =0.6,P
（ Q2 =10） =0.6,P（ Q2 =20） =0.4,每月初进货，仓库容量为 30，两个月的进货价分别为 1.1和 1，售价分别为 1.8和 1.6，前两个月未售完的存货将在第三个月以单价 0.8削价处理，且全部售完。问商店如何制订进货计划，
使三个月的期望毛利最大。
55
解,k=3，每一阶段确定每一月的进货量
xk：第 k月的进货量 x3=0
sk：第 k月初库存量
sk+1=sk+xk-Qk （ Qk为随机变量） s4=0
r1（ s1,i,x1） =1.8Q1-1.1x1
r2（ s2,i,x2） =1.6Q2-x2
56
方程：
f4(s4)=0
fk(sk)=max{ [ rk(sk,i,xk)+fk+1(i)]pi(xk)}
k=3
s3={0,10,20} x3*=0
f3(s3)=0.8s3
f3(0)=0
f3(10)=8
f3(20)=16
2
∑
i=1
57
k=2
s2={0,10,20} x2 ∈ {0,10,20}
f2(s2)=max{ [ r2(s2,i,x2)+f3(i)]pi(x2)}
=max{ [1.6Q2-x2+0.8s3]pi(x2)}
0
f2(0)=max 1.6*10-10
[1.6*10-20+f3(10)]*0.6+[(1.6*20-20+f3 (0))]*0.4
0
=max 6 =7.2
7.2
x2*(0)=20
2∑
i=1
2∑
i=1
58
1.6*10-0+0
f2(10)=max [(1.6*10-10+f3(10)]*0.6+[(1.6*20-10+f3(0)]*0.4
[(1.6*10-20+f3(20)]*0.6+[(1.6*20-20+f3(10)]*0.4
16
=max 17.2 =17.2
15.2
x2*(10)=10
f2(20)=max [(1.6*10+f3(10)]*0.6+[(1.6*20-0+0)]*0.4
[(1.6*10-10+f3(20)]*0.6+[(1.6*20-10+f3(10)]*0.4
=27.2
x2*(20)=0
59
k=1
s1={0} x1={0,10,20,30}
f1(0)=max{[1.8Q1-1.1x1+f2(s2)]pi(x1)}
f2(0)
f1(0)=max 1.8*10-1.1*10+f2(0)
[1.8*10-1.1*20+f2(10)]*0.4+[1.8*20-1.1*20+f2(0)*0.6
[1.8*10-1.1*30+f2(20)]*0.4+[1.8*20-1.1*30+f2(10)*0.6
7.2
=max 14.2 =18
18.0
17
x1*(0)=20
60
x1*=20
若第 1月份销量为 10，则 s2=10,x2*=10
若第 1月份销量为 20，则 s2=0,x2*=20
61
不确定采购问题
EX：某厂生产上需要在近五周内采购一批原料，估计在未来五周内价格有波动，其浮动价格和概率如表，试求在哪一周以什么价格购入，使其采购价格的数学期望最小，并求期望值。
单价 概率
500
600
700
0.3
0.3
0.4
62
xk= 1 采购
0 不采购
sk：第 k周实际价格
skE：第 k周决定等待，在以后采取最优决策时采购价格的期望值
fk（ sk）：第 k周实际价格为 sk时，从第 k周到第 5周采取最优决策所得的最小期望值
fk（ sk)=min{sk,skE} sk属于 Sk
f5(s5)=s5
skE=Efk+1(sk+1)=0.3fk+1(500)+0.3fk+1(600)+0.4fk+1(700)
63
k=5
f5(s5)=s5 第 5周无论市价如何，必须采购
f5(500)=500
f5(600)=600
f5(700)=700
k=4
s4E=0.3f5(500)+0.3f5(600)+0.4f5(700)=610
f4(s4)=min{s4,s4E}=min{s4,610}
500 s4=500
= 600 s4=600
610 s4=700
x4= 1 s4=500,600
0 s4=700
64
k=3
f3(s3)=min{s3,574}= 500 s3=500
574 s3=600,700
x3= 1 s3=500
0 s3=600,700
k=2
f2(s2)=min{s2,551.8}= 500 s2=500
551.8 s2=600,700
x2= 1 s2=500
0 s2=600,700
65
k=1
f1(s1)=min{s1,536.26}= 500 s1=500
536.26 s1=600,700
x1= 1 s1=500
0 s1=600,700
66
最优采购决策：
1,2,3周时，价格为 500采购，否则等待
4周时，价格为 500或 600采购，否则等待
5周时，必须购
500*0.3(1+0.7+0.72+0.73+0.73*0.4)
+600*0.3(0.73+0.4*0.73)
+700*0.42*0.73
=525.382
67
本章结束！
