第二节 动态规划应用举例本节将通过动态规划的三种应用类型 —— 资源分配问题、复合系统可靠性问题、设备更新问题，进一步介绍动态规划的特点和处理方法。
一、资源分配问题
1,问题的一般提法设有某种资源，总数量为 a，用于生产 n种产品；
若分配数量 xi用于生产第 i种产品，其收益为 gi(xi)。
问应如何分配，可使总收益最大？
2,数学规划模型
xi 种产品的资源数量为设分配给第决策变量,
xgM a xz )( 目标函数：
nix
ax
,,1,0
约束条件：
模型的特点
—— 变量分离。
3.用动态规划方法求解阶段 k
状态 sk
决策 xk
=1,…,n表示把资源分配给第 k种产品的过程；
表示在给第 k种产品分配之前还剩有的资源量；
表示分配给第 k种产品的资源量；
状态转移 sk+1 = sk- xk ；
阶段指标 vk
指标函数 vkn ；；
n
ki ii
kk
xg
xg
)(
)(
,1,0,1
1
nkf
fvM a xf基本方程
1 2S1=a
x1 x2
g1(x1) g2(x2)
n
xn
sn
gn(xn)
s2 s3,..
例 3 某公司拟将某种高效设备 5台分配给所属甲、
乙、丙 3厂。各厂获此设备后可产生的效益如下表。问应如何分配，可使所产生的总效益最大？
效益 厂设备台数 甲 乙 丙
0 0 0 0
1 3 5 4
2 7 10 6
3 9 11 11
4 12 11 12
5 13 11 12
解,阶段 k
状态 sk
决策 xk
=1,2,3依次表示把设备分配给甲、乙、丙厂的过程；
表示在第 k阶段初还剩有的可分台数；
表示第 k阶段分配的设备台数；
状态转移 sk+1= sk- xk ；
阶段指标 vk
指标函数 vk3 ；；阶段分配后产生的效益表示第
3
k
)( xv
k
,1,0,
1
23kf
fvM a xf基本方程问题：本问题是属于离散型还是属于连续型？怎样解？
—— 离散型，用表格的方式求解。
效益 厂设备台数 甲 乙 丙
0 0 0 0
1 3 5 4
2 7 10 6
3 9 11 11
4 12 11 12
5 13 11 12
k Sk xk vk vk+fk+1 fk?P
3
0
1
2
3
4
5
0
1
2
3
4
5
0
4
6
11
12
12
0+0
4+0
6+0
11+0
12+0
12+0
0
4
6
11
12
12
0
1
2
3
4
5
k Sk xk vk vk+fk+1 fk?P
0
1
2
3
4
5
2
0 0 0+0 0 0-0
0 0 0+4
1 5 5+0 5 1-0
0 0 0+6
1 5 5+4
2 10 10+0
10 2-0
0 0 0+11
1 5 5+6
2 10 10+4
3 11 11+0
14 2-1
0 0 0+12
1 5 5+11
2 10 10+6
3 11 11+4
4 11 11+0
16 1-3
2-2
0 0 0+12
1 5 5+12
2 10 10+11
3 11 11+6
4 11 11+4
5 11 11+0
21 2-3
k Sk xk vk vk+fk+1 fk?P
1 5
0
1
2
3
4
5
0
3
7
9
12
13
0+21
3+16
7+14
9+10
12+5
13+0
21 0-2-3
2-2-1
最优策略,P*13 为 0-2-3或 2-2-1，
即分给甲厂 0台、分给乙厂 2台、分给丙厂 3台，
或分给甲厂 2台、分给乙厂 2台、分给丙厂 1台。
最优值,f1=21。
可见，最优解可以是不唯一的，但最优值是唯一的。
资源分配问题的应用很广泛，例如：
1.某学生正在备考 4门功课，还剩 7天时间，
每门功课至少复习 1天。若他已估计出各门功课的复习天数与能提高的分数之间的关系，
问他应怎样安排复习时间可使总的分数提高最多？
2.背包问题：旅行者携带的背包中能装的物品重量为 a，现他要从 n种物品中挑选若干数量装入背包，问他应如何挑选可使所带的物品总价值最大？
二、复合系统工作可靠性问题
1,问题的一般提法设某工作系统由 n个部件串接而成，为提高系统的可靠性，在每个部件上装有备用件。
已知部件 i上装有 xi个备用件时，其正常工作的概率为 pi(xi)；每个部件 i的备用件重量为 wi，系统要求总重量不超过 W。问应如何安排备用件可使系统可靠性最高？
串接,1 2
2,数学规划模型个备用件个部件安排设给第决策变量,xi
)( 1 iini xpM a x z目标函数：
为非负整数约束条件：
x
Wxw
1
模型的特点
—— 变量分离。
3.用动态规划方法求解
1 2S1=W
x1 x2
p1(x1) p2(x2)
n
xn
sn
pn(xn)
s2 s3,..
阶段 k
状态 sk
决策 xk
=1,…,n表示安排第 k个部件备用件的过程；
表示在给第 k个部件安排之前还剩有的容许重量；
表示第 k个部件上安排的备用件数量；
状态转移 sk+1 = sk- wkxk ；
阶段指标 vk
指标函数 vkn ；
的可靠性；部件安排备用件后产生表示第
)(
n
xp
k
,1,,1n
1
nkf
fvM a xf
1基本方程可靠性问题的应用很广泛，例如：
1.某重要的科研攻关项目正在由 3个课题组以 3种不同的方式进行，各组已估计出失败的概率。为减少失败的概率，选派了 2名高级专家去充实科研力量。若可估计出各组增加专家后的失败概率，问应如何分派专家可使总的失败概率最小？
2.已知 x1+x2+…+ xn=c，求 z=x1x2… xn的最大值。
三、设备更新问题例 4 某运输公司购进一批卡车投入运营，公司每年初需对卡车作出更新或继续使用的决定。假设第 k年中,rk(tk)
表示车龄为 tk的车使用一年的收入,uk(tk)表示车龄为 tk的车使用一年的维修费用,ck(tk)表示车龄为 tk的车更新成新车的费用。现公司需制定一个 10年计划，以决定如何安排使 10年的总收入最大。
1 2S1=？
x1 x2
10
x10
s10
v1 v2 v10
s2 …
问题：状态和决策怎样设置？
—— 决策是更新与否，可用 0-1变量表示；状态可设为车龄。
阶段 k
状态 sk
决策 xk
= 1,…,10 表示第 k年的决策过程；
= tk表示第 k年的车龄；
年不更新，第年更新第
k
k
0
1,
状态转移 tk+1 = tk +1(1-xk)
阶段指标 vk
指标函数 vkn
= rk[tk ] - uk[tk ] - ck(tk)(1-xk) (1-xk) xk；?
10 v
,11 0,0,11
1
kf
fvM a xf基本方程四、其他 —— 随机型问题举例例 5 某瓷厂接受订制一个瓷瓶的任务。瓷瓶用电炉烧制。
据技术分析估计，每个瓷瓶出炉后的合格率为 0.5，各瓶合格与否相互独立（即一炉如装有 n个瓷瓶，那么出炉后都不合的概率为 0.5n）。 制造一个瓷瓶的原料费为 100元，烧一炉的费用为 300元。现因厂中条件限制最多只能烧 3炉，每炉最多装 4个瓷瓶。若 3炉的瓷瓶无 1个合格，则因不能履行合同而被罚款 1600元。试用动态规划方法确定一种生产方案（即每炉该装几个瓷瓶），使总的期望成本为最小。
一、资源分配问题
1,问题的一般提法设有某种资源，总数量为 a，用于生产 n种产品；
若分配数量 xi用于生产第 i种产品，其收益为 gi(xi)。
问应如何分配，可使总收益最大？
2,数学规划模型
xi 种产品的资源数量为设分配给第决策变量,
xgM a xz )( 目标函数：
nix
ax
,,1,0
约束条件：
模型的特点
—— 变量分离。
3.用动态规划方法求解阶段 k
状态 sk
决策 xk
=1,…,n表示把资源分配给第 k种产品的过程；
表示在给第 k种产品分配之前还剩有的资源量；
表示分配给第 k种产品的资源量；
状态转移 sk+1 = sk- xk ；
阶段指标 vk
指标函数 vkn ；；
n
ki ii
kk
xg
xg
)(
)(
,1,0,1
1
nkf
fvM a xf基本方程
1 2S1=a
x1 x2
g1(x1) g2(x2)
n
xn
sn
gn(xn)
s2 s3,..
例 3 某公司拟将某种高效设备 5台分配给所属甲、
乙、丙 3厂。各厂获此设备后可产生的效益如下表。问应如何分配，可使所产生的总效益最大？
效益 厂设备台数 甲 乙 丙
0 0 0 0
1 3 5 4
2 7 10 6
3 9 11 11
4 12 11 12
5 13 11 12
解,阶段 k
状态 sk
决策 xk
=1,2,3依次表示把设备分配给甲、乙、丙厂的过程；
表示在第 k阶段初还剩有的可分台数；
表示第 k阶段分配的设备台数；
状态转移 sk+1= sk- xk ；
阶段指标 vk
指标函数 vk3 ；；阶段分配后产生的效益表示第
3
k
)( xv
k
,1,0,
1
23kf
fvM a xf基本方程问题：本问题是属于离散型还是属于连续型？怎样解？
—— 离散型，用表格的方式求解。
效益 厂设备台数 甲 乙 丙
0 0 0 0
1 3 5 4
2 7 10 6
3 9 11 11
4 12 11 12
5 13 11 12
k Sk xk vk vk+fk+1 fk?P
3
0
1
2
3
4
5
0
1
2
3
4
5
0
4
6
11
12
12
0+0
4+0
6+0
11+0
12+0
12+0
0
4
6
11
12
12
0
1
2
3
4
5
k Sk xk vk vk+fk+1 fk?P
0
1
2
3
4
5
2
0 0 0+0 0 0-0
0 0 0+4
1 5 5+0 5 1-0
0 0 0+6
1 5 5+4
2 10 10+0
10 2-0
0 0 0+11
1 5 5+6
2 10 10+4
3 11 11+0
14 2-1
0 0 0+12
1 5 5+11
2 10 10+6
3 11 11+4
4 11 11+0
16 1-3
2-2
0 0 0+12
1 5 5+12
2 10 10+11
3 11 11+6
4 11 11+4
5 11 11+0
21 2-3
k Sk xk vk vk+fk+1 fk?P
1 5
0
1
2
3
4
5
0
3
7
9
12
13
0+21
3+16
7+14
9+10
12+5
13+0
21 0-2-3
2-2-1
最优策略,P*13 为 0-2-3或 2-2-1，
即分给甲厂 0台、分给乙厂 2台、分给丙厂 3台，
或分给甲厂 2台、分给乙厂 2台、分给丙厂 1台。
最优值,f1=21。
可见，最优解可以是不唯一的，但最优值是唯一的。
资源分配问题的应用很广泛，例如：
1.某学生正在备考 4门功课，还剩 7天时间，
每门功课至少复习 1天。若他已估计出各门功课的复习天数与能提高的分数之间的关系，
问他应怎样安排复习时间可使总的分数提高最多？
2.背包问题：旅行者携带的背包中能装的物品重量为 a，现他要从 n种物品中挑选若干数量装入背包，问他应如何挑选可使所带的物品总价值最大？
二、复合系统工作可靠性问题
1,问题的一般提法设某工作系统由 n个部件串接而成，为提高系统的可靠性，在每个部件上装有备用件。
已知部件 i上装有 xi个备用件时，其正常工作的概率为 pi(xi)；每个部件 i的备用件重量为 wi，系统要求总重量不超过 W。问应如何安排备用件可使系统可靠性最高？
串接,1 2
2,数学规划模型个备用件个部件安排设给第决策变量,xi
)( 1 iini xpM a x z目标函数：
为非负整数约束条件：
x
Wxw
1
模型的特点
—— 变量分离。
3.用动态规划方法求解
1 2S1=W
x1 x2
p1(x1) p2(x2)
n
xn
sn
pn(xn)
s2 s3,..
阶段 k
状态 sk
决策 xk
=1,…,n表示安排第 k个部件备用件的过程；
表示在给第 k个部件安排之前还剩有的容许重量；
表示第 k个部件上安排的备用件数量；
状态转移 sk+1 = sk- wkxk ；
阶段指标 vk
指标函数 vkn ；
的可靠性；部件安排备用件后产生表示第
)(
n
xp
k
,1,,1n
1
nkf
fvM a xf
1基本方程可靠性问题的应用很广泛，例如：
1.某重要的科研攻关项目正在由 3个课题组以 3种不同的方式进行，各组已估计出失败的概率。为减少失败的概率，选派了 2名高级专家去充实科研力量。若可估计出各组增加专家后的失败概率，问应如何分派专家可使总的失败概率最小？
2.已知 x1+x2+…+ xn=c，求 z=x1x2… xn的最大值。
三、设备更新问题例 4 某运输公司购进一批卡车投入运营，公司每年初需对卡车作出更新或继续使用的决定。假设第 k年中,rk(tk)
表示车龄为 tk的车使用一年的收入,uk(tk)表示车龄为 tk的车使用一年的维修费用,ck(tk)表示车龄为 tk的车更新成新车的费用。现公司需制定一个 10年计划，以决定如何安排使 10年的总收入最大。
1 2S1=？
x1 x2
10
x10
s10
v1 v2 v10
s2 …
问题：状态和决策怎样设置？
—— 决策是更新与否，可用 0-1变量表示；状态可设为车龄。
阶段 k
状态 sk
决策 xk
= 1,…,10 表示第 k年的决策过程；
= tk表示第 k年的车龄；
年不更新，第年更新第
k
k
0
1,
状态转移 tk+1 = tk +1(1-xk)
阶段指标 vk
指标函数 vkn
= rk[tk ] - uk[tk ] - ck(tk)(1-xk) (1-xk) xk；?
10 v
,11 0,0,11
1
kf
fvM a xf基本方程四、其他 —— 随机型问题举例例 5 某瓷厂接受订制一个瓷瓶的任务。瓷瓶用电炉烧制。
据技术分析估计，每个瓷瓶出炉后的合格率为 0.5，各瓶合格与否相互独立（即一炉如装有 n个瓷瓶，那么出炉后都不合的概率为 0.5n）。 制造一个瓷瓶的原料费为 100元，烧一炉的费用为 300元。现因厂中条件限制最多只能烧 3炉，每炉最多装 4个瓷瓶。若 3炉的瓷瓶无 1个合格，则因不能履行合同而被罚款 1600元。试用动态规划方法确定一种生产方案（即每炉该装几个瓷瓶），使总的期望成本为最小。
