4-3 动 态 规 划 应用 (一 )
建 模 练 习
一,工程路线问题
（也称最短路或最长路问题）
工程路线问题的一般提法：
从某地出发，途径若干个中间点
最后到达目的地，试求距离最短或
费用最省的路线。
具体有两种情况：
1,从出发点到目的地的每条路线均由 n条
边（弧）组成，因此问题可以化为 n个
阶段的多阶段决策过程。由于可以明确
地划分出固定的阶段数，所以称为 定步
数问题,亦称 定期的多阶段决策过程。
2,阶段数不固定则称为 不定步数问题,或
不定期的多阶段决策过程 。
建模过程如表 4-1。
表 4-1 工程路线的建模过程
基 本 方 程
? ?
1,2,,1,
0)!(
)(m i n)(
1
1
???
?
?
?
?
?
??
??
?
?
nnk
nf
jfCif
n
kij
j
k
最 短 路 问 题 最 长 路 问 题
阶段,nk,,2,1 ??
√
状态变量：各阶段初始位置
)(
kkkk
XiXx ?? 或
√
决策变量：各阶段终止位置
)(
kkkk
UjUu ?? 或
√
状态转移方程：
)()(
11 kkkkkk
ijixux ??
??
或
√
阶段效益
)(),(
1
的费用
?
???
kkkijkkk
xuxCuxr
√
目标函数：
kk
kk
n
k
ij
n
k
k
ji
uxCrR
??
??
??
??
),(
11
√
基本方程：
? ?
?
?
?
?
?
???
??
??
?
1210)(
)().(m i n)(
11
1
，，,?nnkjf
jfjiCif
nn
kkkkk
j
kk
k
? ?
?
?
?
?
?
???
??
??
?
1210)(
)().(m a x)(
11
1
，，,?nnkjf
jfjiCif
nn
kkkkk
j
kk
k
? ?
?
?
?
?
?
???
??
??
?
1210)(
)().(m a x)(
11
1
，，,?nnkjf
jfjiCif
nn
kkkkk
j
kk
k
或简化为
? ?
?
?
?
?
?
???
??
??
?
1,,1,0)(
)(m i n)(
11
1
?nnkif
jfCif
nn
kij
j
k
或
? ?
?
?
?
?
?
???
??
??
?
1,,1,0)(
)(m a x)(
11
1
?nnkif
jfCif
nn
kij
j
k
若是不定步数问题，则基本方
程呈函数方程的形式：
? ?)(m i n)( jfcif ijj ??
二、资源分配问题,
1,资源的多元分配,
某种资源总量为 M，用于进行 n种
生产活动，已知用于活动 k的资源量
为 uk时收益为 gk(uk)，（ gk(uk)为 uk
的非递减函数），问如何分配资源，
才能使 n种生产活动的总收益最大？
例 4-2,某公司拟将 5万元资金投放下属 A,B、
C三个企业，各企业在获得资金后的收益如
下表所示，用动态规划方法求总收益最大的
投资分配方案（投资数取整数）。
表 4-2 例 4-2已知信息表
投放资金 （ 万元 ） 0 1 2 3 4 5
收 益
(万元 )
A 0 2 2 3 3 3
B 0 0 1 2 4 7
C 0 1 2 3 4 5
?
?
?
3
1
)(
k
kk ugR
该问题可以作为三阶段决策过程 。
对 A,B,C三个企业资金分配过程分
别形成 1,2,3三个阶段 。
xk表示给企业分配资金数时拥有的资金数 。
uk为给企业实际分配的资金数 。
状态转移方程是 xk+1=xk-uk。
阶段效应 rk(xk,uk)如表 4-2所示,记为 gk(uk)。
目标函数是：
一 般 问 题 例 4 - 2
大
前
提
阶 段
变量 k
把每一种活动作为一个阶段,n 种生产活
动构成 n 个阶段。由于每个阶段都要确定
对该项活动的资源投放量，从而构成多阶
段决策问题
把资金分配给一个企业的过程看作
一种生产活动，向三个企业的投资过
程看作三个阶段
条
件 1
状态与状态
变量
k 阶段初拥有的资源量，即对第 k 阶段到
第 n 阶段这 n - k 种活动中可进行分配的资
源量 0 ≤ x k ≤ M, x 1 =M
给企业 K 投资时所拥有的资金数（即
初始的资源拥有量） x
k
,0 ≤ x k ≤ 5,
x 1 =5
条
件 2
决策与决策
变量
对第 k 种生产活动的资源投放量
0 ≤ u k ≤ x k
给企业 k 的投资数（阶段投放量）
0 ≤ u k ≤ x k
条
件 3
状态转移方
程
x
k + 1
=x
k
- u
k
x
k + 1
=x
k
- u
k
阶段效应 对活动投放资源 u
k
时的收益
r
k
（ x
k
,u
k
） =g
k
（ u
k
）
g
k
（ u
k
）, k = 1, 2, 3 条
件 4
目标函数
R=
??
??
?
n
k
kk
n
k
kkk
uguxr
11
)(),(
?
?
?
3
1
),(
k
kkk
uxgR
一
个
方
程
基本方程
? ?
?
?
?
?
?
???
??
??
??
1210)(
)()(m a x)(
11
11
，，,?nnkxf
xfugxf
nn
kkkk
u
kk
k
? ?
?
?
?
?
?
??
??
??
12,30)(
)()(m a x)(
44
11
，kxf
xfugxf
kkkk
u
kk
k
资金分配完毕，不再分配，收益为 0
表
4-
3
资
源
的
多
元
分
配
问
题
建
模
过
程
2,资源的多段分配 —— 有消耗的资源
多阶段地在两种不同的生产活动中投放的问题
问题的提法,假定拥有某种资源，总量为
M，计划在 A,B两种生产过程（部门）中连
续使用 n个阶段，已知在两个部门中分别投入
资源 ua,ub后可分别获得阶段效益 g(ua),
h(ub)，同时知道每生产一个阶段后资源的完
好率分别为 a和 b，（ 0<a<1,0<b<1）,求 n个
阶段间总收益最大的资源分配计划。
例 4-3 今有 1000台机床，要投放到
A,B两个生产部门，计划连续使用 5年。
已知对 A部门投入 ua台机器时的年收益
是 g(ua)=ua2元，机器完好率 a=0.8；相应
地,B部门为 h(ub)=2ub2,b=0.4。
试建立 5年间总收益最大的年度机
器分配方案。
问题的建模过程如表 4-4所示。
表 4-4 资源的多段分配问题建模过程
一般问题 例 4 - 3
前提,
n 阶段决策，每个阶段均要决定 A, B 两个部门的资源投放
量。 K = 1,2,…,n
5 阶段决策问题,( 机器连续使用五年 )
一个年度作为一个阶段；
k
=1, 2, 3, 4, 5 。
状态与状
态变量
k
阶段初拥有的资源量
k
x
MxMx
k
???
1
,0
k
年初拥 有的完好机器数
k
x
100 0,100 00
1
??? xx
k
决策与决
策变量
k
阶段对 A 部门的资源投放量
Ak
uu ?
则有：
AkkkB
uxuxu ????
kk
xu ??0
k
年度投入 A 部门的机器台数
Ak
uu ?
（
kkB
uxu ??
）
kk
xu ??0
状态转移
方程
)(
1 kkkk
uxbaux ???
?
阶段末 A 部门剩余资源 阶段末 B 部门剩余资源
)(4.08.0
1 kkkk
uxux ???
?
阶段效益
与目标函
数
)()(),(
kkkkkk
uxhuguxr ???
? ?
??
??
????
n
k
kkk
n
k
k
uxhugrR
11
)()(
22
)(2)()(
kkkkkkk
uxuuxhugr ??????
? ?
??
??
????
n
k
kkk
n
k
k
uxurR
1
22
1
)(2
基本方程
? ?
?
?
?
?
?
???
????
??
??
1,,1,0)(
)()()(m a x)(
11
11
?nnkxf
xfuxhugxf
nn
kkkkk
u
kk
k
? ?
?
?
?
?
?
??
?????
??
??
1,2,3,4,50)(
)()(2m a x)(
66
11
2
0
kxf
xfuxuxf
kkkkk
xu
kk
kk
三、生产 — 库存问题：
生产（或销售）部门 已知 生产成
本、库存费用、各阶段的市场需求，
需要决定 各阶段产量（或采购量），
使计划期内的 费用总和最小 。
问题的一般提法,设有一生产部门，生产计划
周期分为 n个阶段（即 k=1~n）已知最初库存量
为 x1，阶段产量需求为 dk，生产的固定成本
为,单位产品的消耗费用为 L，单位产品的
阶段库存费用为 h，库存容量为 M，阶段生产能
力为 B，问应 如何安排各阶段的产量，使计划
期内的费用总和最小。
k~
k~ 例 4-4 求解生产 -库存问题：已知 n=3,=8，
L=2,h=2,x1=1,M=4,x4=0（计划期末库存
为 0）,B=6,d1=3,d2=4,d3=3。
表 4-5 生产 -库存问题的建模过程
问题一般形式 例 4 - 4
阶段
（ k ）
计划期所划分的阶段即为 D P 模型的阶段
nk,,2,1 ??
3,2,1,3 ?? kn
状态与状
态变量
第
k
阶段初的库存量
k
x
，
1
x 已知。若 1?n
x
已知，
则为始、终端固定的问题，若
1?n
x
=0 即计划期末
无库存。这样,
? ?
nkkk
dddMx ?????
?
?
1
,m i n0
1
1
?x （初始库存）
0
4
?x （计划期末库存为 0 ）
? ?
3
,m i n0 ddMx
kk
???? ?
决策与决
策变量
k
阶段的产量
k
u
? ?
knkkkk
xddBuxd ????? ?,m i n
? ?
kkkkk
xdduxd ?????
3
,6m i n ?
状态转移
方程
kkkk
duxx ???
? 1
k = 1, …, n
kkkk
duxx ???
? 1
, k = 1, 2, 3
阶段效益
与目标函
数
生产费用 + 库存费用
)(
?
1
^
kkkk
kkk
duxhLuk
hxLukr
?????
???
?
?
?
?
h
k
k
rR
1
)(228
228
1
kkkk
kkk
duxu
xur
?????
???
?
? ?
?
?
?????
3
1
)(228
k
kkkk
duxuR
基本方程
? ?
?
?
?
?
?
?
?
???
??????
??
??
1,,1,0)(
)()(
?
m i n
)(
11
11
?nnkxf
xfduxhLuk
xf
nn
kkkkkk
u
kk
k
? ?
?
?
?
?
?
?
?
??
?????
??
1,2,30)(
)()(228m i n
)(
44
11
kxf
xfduxu
xf
kkkkkk
u
kk
k
四、设备更新问题
问题的一般提法,已知 n为计算设备回
收额的总期数,t为某个阶段的设备役龄，
r(t)为从役龄为 t的设备得到的阶段效益，
u(t)为役龄为 t的设备的阶段使用费,s(t)是
役龄为 t的设备处理价格,p为新设备的购
置价格。假定关于现值的折扣率为 1,求 n
期内使回收额最大的设备更新策略。
例 4-5 假定设备的使用年限为 10年，设备的
处理价格与役龄无关为 4万元，其它有关信息
如表 4-6所示，寻求设备更新的最优策略 。
表 4 - 6 例 4 - 5 有关信息表 ( 单位：万元 )
t 期数 0 1 2 3 4 5 6 7 8 9 10
r （ t ） 27 26 26 25 24 23 23 22 21 21 20
u(t) 15 15 16 16 16 17 18 18 19 20 20
表 4-6 设备更新问题建模过程
问题的一般提法 例 4 - 5
阶 段 设备使用年限 n = 10
状态变量 设备的役龄 t √
决策变量 K —— 保留
P —— 更新
k 或 p
状态转移
方程
?
?
?
? )(1
)(
决策
决策
kt
pt
√
阶段效应
与目标函
数
从役龄 t 为的设备得到的收益
回收额
k
g
=
?
?
?
? u ( 0 )-r ( 0 )p-s ( t )p
u ( t )-r ( t )k
时：决策为
时：决策为
总回收额 ?
?
?
n
k
k
gR
1
?
?
?
????????
?
决策
决策
purpts
ktutr
31527134)0()0()(
)()(
√
基本方程
?
?
?
?
?
?
?
?
?
?????
???
?
?
?
?
0)(
)1()0()0()(:
)1()()(:
m a x)(
1
1
1
tf
tfurptsp
tftutrk
tf
n
k
k
k
?
?
?
?
?
?
?
?
?
?
???
?
?
?
0)(
)1(3:
)1()()(:
m a x)(
11
1
1
tf
fp
tftutrk
tf
k
k
k
五、其它典型问题
1、串联系统可靠性问题：
在成本、重量、体积等一定的限制
下，如何选择各部件的备用元件数，
使整个系统的可靠性最大。
特点,目标函数是阶段效应的 乘积 形
式。
2、背包问题：
在旅行袋容积或载重量的限制条件下，
如何选择装载物品，使总价值最大。
特点：
?只有一个限制条件构成 一维背包 问题，
有两个限制条件则构成 二维背包 问题；
?二维背包 问题有两个状态变量；
第七次作业
P175~P177：
根据 4-2,4-3,4-4三个题目的
背景，分别建立动态规划模型
建 模 练 习
一,工程路线问题
（也称最短路或最长路问题）
工程路线问题的一般提法：
从某地出发，途径若干个中间点
最后到达目的地，试求距离最短或
费用最省的路线。
具体有两种情况：
1,从出发点到目的地的每条路线均由 n条
边（弧）组成，因此问题可以化为 n个
阶段的多阶段决策过程。由于可以明确
地划分出固定的阶段数，所以称为 定步
数问题,亦称 定期的多阶段决策过程。
2,阶段数不固定则称为 不定步数问题,或
不定期的多阶段决策过程 。
建模过程如表 4-1。
表 4-1 工程路线的建模过程
基 本 方 程
? ?
1,2,,1,
0)!(
)(m i n)(
1
1
???
?
?
?
?
?
??
??
?
?
nnk
nf
jfCif
n
kij
j
k
最 短 路 问 题 最 长 路 问 题
阶段,nk,,2,1 ??
√
状态变量：各阶段初始位置
)(
kkkk
XiXx ?? 或
√
决策变量：各阶段终止位置
)(
kkkk
UjUu ?? 或
√
状态转移方程：
)()(
11 kkkkkk
ijixux ??
??
或
√
阶段效益
)(),(
1
的费用
?
???
kkkijkkk
xuxCuxr
√
目标函数：
kk
kk
n
k
ij
n
k
k
ji
uxCrR
??
??
??
??
),(
11
√
基本方程：
? ?
?
?
?
?
?
???
??
??
?
1210)(
)().(m i n)(
11
1
，，,?nnkjf
jfjiCif
nn
kkkkk
j
kk
k
? ?
?
?
?
?
?
???
??
??
?
1210)(
)().(m a x)(
11
1
，，,?nnkjf
jfjiCif
nn
kkkkk
j
kk
k
? ?
?
?
?
?
?
???
??
??
?
1210)(
)().(m a x)(
11
1
，，,?nnkjf
jfjiCif
nn
kkkkk
j
kk
k
或简化为
? ?
?
?
?
?
?
???
??
??
?
1,,1,0)(
)(m i n)(
11
1
?nnkif
jfCif
nn
kij
j
k
或
? ?
?
?
?
?
?
???
??
??
?
1,,1,0)(
)(m a x)(
11
1
?nnkif
jfCif
nn
kij
j
k
若是不定步数问题，则基本方
程呈函数方程的形式：
? ?)(m i n)( jfcif ijj ??
二、资源分配问题,
1,资源的多元分配,
某种资源总量为 M，用于进行 n种
生产活动，已知用于活动 k的资源量
为 uk时收益为 gk(uk)，（ gk(uk)为 uk
的非递减函数），问如何分配资源，
才能使 n种生产活动的总收益最大？
例 4-2,某公司拟将 5万元资金投放下属 A,B、
C三个企业，各企业在获得资金后的收益如
下表所示，用动态规划方法求总收益最大的
投资分配方案（投资数取整数）。
表 4-2 例 4-2已知信息表
投放资金 （ 万元 ） 0 1 2 3 4 5
收 益
(万元 )
A 0 2 2 3 3 3
B 0 0 1 2 4 7
C 0 1 2 3 4 5
?
?
?
3
1
)(
k
kk ugR
该问题可以作为三阶段决策过程 。
对 A,B,C三个企业资金分配过程分
别形成 1,2,3三个阶段 。
xk表示给企业分配资金数时拥有的资金数 。
uk为给企业实际分配的资金数 。
状态转移方程是 xk+1=xk-uk。
阶段效应 rk(xk,uk)如表 4-2所示,记为 gk(uk)。
目标函数是：
一 般 问 题 例 4 - 2
大
前
提
阶 段
变量 k
把每一种活动作为一个阶段,n 种生产活
动构成 n 个阶段。由于每个阶段都要确定
对该项活动的资源投放量，从而构成多阶
段决策问题
把资金分配给一个企业的过程看作
一种生产活动，向三个企业的投资过
程看作三个阶段
条
件 1
状态与状态
变量
k 阶段初拥有的资源量，即对第 k 阶段到
第 n 阶段这 n - k 种活动中可进行分配的资
源量 0 ≤ x k ≤ M, x 1 =M
给企业 K 投资时所拥有的资金数（即
初始的资源拥有量） x
k
,0 ≤ x k ≤ 5,
x 1 =5
条
件 2
决策与决策
变量
对第 k 种生产活动的资源投放量
0 ≤ u k ≤ x k
给企业 k 的投资数（阶段投放量）
0 ≤ u k ≤ x k
条
件 3
状态转移方
程
x
k + 1
=x
k
- u
k
x
k + 1
=x
k
- u
k
阶段效应 对活动投放资源 u
k
时的收益
r
k
（ x
k
,u
k
） =g
k
（ u
k
）
g
k
（ u
k
）, k = 1, 2, 3 条
件 4
目标函数
R=
??
??
?
n
k
kk
n
k
kkk
uguxr
11
)(),(
?
?
?
3
1
),(
k
kkk
uxgR
一
个
方
程
基本方程
? ?
?
?
?
?
?
???
??
??
??
1210)(
)()(m a x)(
11
11
，，,?nnkxf
xfugxf
nn
kkkk
u
kk
k
? ?
?
?
?
?
?
??
??
??
12,30)(
)()(m a x)(
44
11
，kxf
xfugxf
kkkk
u
kk
k
资金分配完毕，不再分配，收益为 0
表
4-
3
资
源
的
多
元
分
配
问
题
建
模
过
程
2,资源的多段分配 —— 有消耗的资源
多阶段地在两种不同的生产活动中投放的问题
问题的提法,假定拥有某种资源，总量为
M，计划在 A,B两种生产过程（部门）中连
续使用 n个阶段，已知在两个部门中分别投入
资源 ua,ub后可分别获得阶段效益 g(ua),
h(ub)，同时知道每生产一个阶段后资源的完
好率分别为 a和 b，（ 0<a<1,0<b<1）,求 n个
阶段间总收益最大的资源分配计划。
例 4-3 今有 1000台机床，要投放到
A,B两个生产部门，计划连续使用 5年。
已知对 A部门投入 ua台机器时的年收益
是 g(ua)=ua2元，机器完好率 a=0.8；相应
地,B部门为 h(ub)=2ub2,b=0.4。
试建立 5年间总收益最大的年度机
器分配方案。
问题的建模过程如表 4-4所示。
表 4-4 资源的多段分配问题建模过程
一般问题 例 4 - 3
前提,
n 阶段决策，每个阶段均要决定 A, B 两个部门的资源投放
量。 K = 1,2,…,n
5 阶段决策问题,( 机器连续使用五年 )
一个年度作为一个阶段；
k
=1, 2, 3, 4, 5 。
状态与状
态变量
k
阶段初拥有的资源量
k
x
MxMx
k
???
1
,0
k
年初拥 有的完好机器数
k
x
100 0,100 00
1
??? xx
k
决策与决
策变量
k
阶段对 A 部门的资源投放量
Ak
uu ?
则有：
AkkkB
uxuxu ????
kk
xu ??0
k
年度投入 A 部门的机器台数
Ak
uu ?
（
kkB
uxu ??
）
kk
xu ??0
状态转移
方程
)(
1 kkkk
uxbaux ???
?
阶段末 A 部门剩余资源 阶段末 B 部门剩余资源
)(4.08.0
1 kkkk
uxux ???
?
阶段效益
与目标函
数
)()(),(
kkkkkk
uxhuguxr ???
? ?
??
??
????
n
k
kkk
n
k
k
uxhugrR
11
)()(
22
)(2)()(
kkkkkkk
uxuuxhugr ??????
? ?
??
??
????
n
k
kkk
n
k
k
uxurR
1
22
1
)(2
基本方程
? ?
?
?
?
?
?
???
????
??
??
1,,1,0)(
)()()(m a x)(
11
11
?nnkxf
xfuxhugxf
nn
kkkkk
u
kk
k
? ?
?
?
?
?
?
??
?????
??
??
1,2,3,4,50)(
)()(2m a x)(
66
11
2
0
kxf
xfuxuxf
kkkkk
xu
kk
kk
三、生产 — 库存问题：
生产（或销售）部门 已知 生产成
本、库存费用、各阶段的市场需求，
需要决定 各阶段产量（或采购量），
使计划期内的 费用总和最小 。
问题的一般提法,设有一生产部门，生产计划
周期分为 n个阶段（即 k=1~n）已知最初库存量
为 x1，阶段产量需求为 dk，生产的固定成本
为,单位产品的消耗费用为 L，单位产品的
阶段库存费用为 h，库存容量为 M，阶段生产能
力为 B，问应 如何安排各阶段的产量，使计划
期内的费用总和最小。
k~
k~ 例 4-4 求解生产 -库存问题：已知 n=3,=8，
L=2,h=2,x1=1,M=4,x4=0（计划期末库存
为 0）,B=6,d1=3,d2=4,d3=3。
表 4-5 生产 -库存问题的建模过程
问题一般形式 例 4 - 4
阶段
（ k ）
计划期所划分的阶段即为 D P 模型的阶段
nk,,2,1 ??
3,2,1,3 ?? kn
状态与状
态变量
第
k
阶段初的库存量
k
x
，
1
x 已知。若 1?n
x
已知，
则为始、终端固定的问题，若
1?n
x
=0 即计划期末
无库存。这样,
? ?
nkkk
dddMx ?????
?
?
1
,m i n0
1
1
?x （初始库存）
0
4
?x （计划期末库存为 0 ）
? ?
3
,m i n0 ddMx
kk
???? ?
决策与决
策变量
k
阶段的产量
k
u
? ?
knkkkk
xddBuxd ????? ?,m i n
? ?
kkkkk
xdduxd ?????
3
,6m i n ?
状态转移
方程
kkkk
duxx ???
? 1
k = 1, …, n
kkkk
duxx ???
? 1
, k = 1, 2, 3
阶段效益
与目标函
数
生产费用 + 库存费用
)(
?
1
^
kkkk
kkk
duxhLuk
hxLukr
?????
???
?
?
?
?
h
k
k
rR
1
)(228
228
1
kkkk
kkk
duxu
xur
?????
???
?
? ?
?
?
?????
3
1
)(228
k
kkkk
duxuR
基本方程
? ?
?
?
?
?
?
?
?
???
??????
??
??
1,,1,0)(
)()(
?
m i n
)(
11
11
?nnkxf
xfduxhLuk
xf
nn
kkkkkk
u
kk
k
? ?
?
?
?
?
?
?
?
??
?????
??
1,2,30)(
)()(228m i n
)(
44
11
kxf
xfduxu
xf
kkkkkk
u
kk
k
四、设备更新问题
问题的一般提法,已知 n为计算设备回
收额的总期数,t为某个阶段的设备役龄，
r(t)为从役龄为 t的设备得到的阶段效益，
u(t)为役龄为 t的设备的阶段使用费,s(t)是
役龄为 t的设备处理价格,p为新设备的购
置价格。假定关于现值的折扣率为 1,求 n
期内使回收额最大的设备更新策略。
例 4-5 假定设备的使用年限为 10年，设备的
处理价格与役龄无关为 4万元，其它有关信息
如表 4-6所示，寻求设备更新的最优策略 。
表 4 - 6 例 4 - 5 有关信息表 ( 单位：万元 )
t 期数 0 1 2 3 4 5 6 7 8 9 10
r （ t ） 27 26 26 25 24 23 23 22 21 21 20
u(t) 15 15 16 16 16 17 18 18 19 20 20
表 4-6 设备更新问题建模过程
问题的一般提法 例 4 - 5
阶 段 设备使用年限 n = 10
状态变量 设备的役龄 t √
决策变量 K —— 保留
P —— 更新
k 或 p
状态转移
方程
?
?
?
? )(1
)(
决策
决策
kt
pt
√
阶段效应
与目标函
数
从役龄 t 为的设备得到的收益
回收额
k
g
=
?
?
?
? u ( 0 )-r ( 0 )p-s ( t )p
u ( t )-r ( t )k
时：决策为
时：决策为
总回收额 ?
?
?
n
k
k
gR
1
?
?
?
????????
?
决策
决策
purpts
ktutr
31527134)0()0()(
)()(
√
基本方程
?
?
?
?
?
?
?
?
?
?????
???
?
?
?
?
0)(
)1()0()0()(:
)1()()(:
m a x)(
1
1
1
tf
tfurptsp
tftutrk
tf
n
k
k
k
?
?
?
?
?
?
?
?
?
?
???
?
?
?
0)(
)1(3:
)1()()(:
m a x)(
11
1
1
tf
fp
tftutrk
tf
k
k
k
五、其它典型问题
1、串联系统可靠性问题：
在成本、重量、体积等一定的限制
下，如何选择各部件的备用元件数，
使整个系统的可靠性最大。
特点,目标函数是阶段效应的 乘积 形
式。
2、背包问题：
在旅行袋容积或载重量的限制条件下，
如何选择装载物品，使总价值最大。
特点：
?只有一个限制条件构成 一维背包 问题，
有两个限制条件则构成 二维背包 问题；
?二维背包 问题有两个状态变量；
第七次作业
P175~P177：
根据 4-2,4-3,4-4三个题目的
背景，分别建立动态规划模型
