k=4，f4(x4)=0 k=3，0≤d3≤x3，x4=x3-d3
k=2，0≤d2≤x2，x3=x2-d2
k=1，0≤d1≤x1，x2=x1-d1
最优解为 x1=4, d1*=1, x2=x1-d1=3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0， 即项目A投资1万元，项目B投资0万元，项目C投资3 万元，最大效益为60万吨。
x1
x2
x3
x4
x5
s1
第 1
s2
第 2
s3
第 3
s4
第 4
s5
第 5
s6
年
年
年
年
年
指标值 (产量) V1(s1,x1)
指标值 (产量) V2(s2,x2)
指标值 (产量) V3(s3,x3)
指标值 (产量) V4(s4,x4)
指标值 (产量) V5(s5,x5)
动态规划模型构造
阶段k： 运行年份（k=1,2,3,4,5）； 状 态 变 量 sk ： 第 k 年 初 完 好 的 机 器 数 （k=1,2,3,4,5）； 决策变量xk： 第k年投入高负荷运行的机器数； 状态转移方程：sk+1=0.7xk+0.9(sk-xk) 决策允许集合：Dk(sk)={xk|0xksk}
运筹学
第十章 动态规划应用举例
第九章 动态规划应用举例
本章内容
➢资源分配问题 ➢生产与存储问题 ➢背包问题 ➢复合系统工作可靠性问题 ➢排序问题 ➢设备更新问题 ➢货郎担问题
第一节 资源分配问题
（一）投资分配问题
设总投资额为a万元，拟投资于n个项目上，已知 对第i个项目投资xi万元，收益函数为gi(xi)，问应如 何分配资金才可以使总收益最大？这是一个与时间 无明显关系的静态最优化问题，可先列出其静态模 型为：
0
80+0=80
…
…
…
…
…
…
0
7
0+60=60
7
1
5
40+60=100
120
3
2
3
80+0=80
3
1
120+0=120
…
…
…
…
…
…
0
10
0+120=120
10
1
8
40+60=100
200
5
2
6
80+60=140
设xi 为第i 种物品的装件数（非负整数）则问题的数学
模型如下：
n
max Z ci (x i ) i 1 n
wi xi w
i 1 xi 0且为整数(i 1.2.L n)
例1 有一辆最大货运量为10 t 的卡车，用以装载3种 货物，每种货物的单位重量及相应单位价值如表所示。
物品 重量（公斤）
max 0x4 s4
max 0x4 s4
8x4 5(s4 x4 ) 8[0.7x4 1.4x4 12.2s4 13.6s4
0.9(s4
x4 )]
x4
x4* s4
s4
第 4
s5 …
年
指标值 (产量) V4(s4,x4)
+f5(s5)
f3(s3)=max{8x3+5(s3-x3)+f4(s4)}
有一个徒步旅行者，其可携带物品重量的限度为w 公 斤，有n 种物品可供他选择装入包中。已知每种物品的 重量及使用价值（作用），问此人应如何选择携带的 物品（各几件），使所起作用（使用价值）最大？
物品
12
重量（公斤/件） w1 w2
使用价值
c1 c2
…i…n
… wi … wn
…
ci … cn
这就是背包问题。类似的还有运输中的货物装载问 题、人造卫星内的物品装载问题等。
第二节 生产与存储问题
在生产和经营管理中，经常会遇到要合理 地安排生产(或购买)与库存的问题，达到既要 满足社会的需要，又要尽量降低成本费用。因 此，正确制定生产（采购）策略，确定不同时 期的生产量（或采购量）和库存量，以使总的 生产成本费用和库存费用之和最小，这就是生 产和存储问题的目标。
第三节 背包问题
0x3s3
=max{8x3+5(s3-x3)+13.6s4}
0x3s3
=max{8d3+5(s3-d3)+13.6[0.7d3+0.9(s3-d3)]} x3
0x3s3
=max{0.28x3+17.24s3}=17.52s3
0x3s3
s3
第 3
s4 …
年
x3*=s3
指标值
(产量)
V3(s3,x3) +f4(s4)
f3(s3)
X*3
解：终端条件：f4(s4)=0 k=3时，递推方程为
f3 (s3 )
max
0 x s3 w3
c3 x3 f4 (s4 )
max 0 x s3 5
60 x3
s3 D3(s3) s4 60x3+f4(s4)
f3(s3)
X*3
0
0
0
0+0=0
0
0
1
0
1
0+0=0
0
0
…
…
…
…
…
…
5
0
5
0+0=0
1
0 60+0=60
60
1
…
…
…
…
…
…
0
10
0+0=0
10
1
5 60+0=60
120
2
2
0 120+0=120
k=2时，递推方程为
f2
(s2
)
max
0 x s2 w2
c2 x2 f3 (s3 )
max 0 x s2 2
40x2 f3 (s3 )
s2 D2(s2) s3 40x2+f3(s3)
这时决策变量x5的决策允许集合为：
D5 (S5 ) X5 | 0.7 X5 0.9(S5 X5 ) 300, X5 0
即 下面数需重新算
0 X5 4.5S5 1500
从上题计算结果可以看出：前两年低负荷运行， 后三年高负荷运行。是否有这样的规律，n年的生 产计划，总是前1~t-1年底负荷运行，t~n年高负荷 运行。
建立模型：
max Z 4x1 9x2 2x3
x1
x2 xi
0
x3
10 (i 1, 2,3)
例2 有资金4万元，投资A、B、C三个项目，每 个项目的投资效益与投入该项目的资金有关。三 个项目A、B、C的投资效益（万吨）和投入资金 （万元）关系见下表：
求对三个项目的最优投资分配，使总投资效 益最大。
x1*=0 x2*=0 x3*=s3 x4*=s4 x5*=s5
用s1=1000代入，得到五年最大产量为 f1(s1)=f1(1000)=23690
每年投入高负荷运行的机器数以及每年初完好的机 器数为：
s1=1000 x1*=0, x2*=0, x3*=s3=810, x4*=s4=567, x5*=s5=397,
nt1
ai
gh
nt
ai
i0
g(b a) i0
习题1：
某公司有1000辆运输卡车，在超负荷运输（即每 天满载行驶500km以上）情况下，年利润为25万元/ 辆，这时卡车的年损坏率为0.3；在低负荷下运输 （即每天行驶300km以下）情况下，年利润为16万 元/辆。年损坏率为0.1。现要制定一个5年计划，问 每年年初应如何分配完好车辆在两种不同的负荷下 运输的卡车数量，使在第5年年末剩余的完好卡车 数量为500台，并且使在5年内的总利润最大？
一般地，设一个周期为n年， 条件：g(x)、h(x)为线性函数，且g(0)=h(0)=0。
则最优设备分配策略是：从1至t-1年，年初将全 部完好设备投入低负荷运行，从t至n年，年初将 全部完好设备投入高负荷运行，总产量达到最大。
计算t：
高负荷生产时设备的完好率为a，单台产量为g； 低负荷生产时设备的完好率为b，单台产量为h;
s2=0.7x1+0.9(s1-x1)=900 s3=0.7x2+0.9(s2-x2)=810 s4=0.7x3+0.9(s3-x3)=567 s5=0.7x4+0.9(s4-x4)=397 s6=0.7x5+0.9(s5-x5)=278
该例题对S6没有限制，有时会对最后一年年末 完好设备数施以约束，例如S6〉=300。
阶段指标： 终端条件：
vk(sk,xk)=8xk+5(sk-xk) f6(s6)=0
递推方程：
fk(sk)=max{vk(sk,xk)+fk+1(sk+1)} 0xksk
=max{8xk+5(sk-xk)+fk+1[0.7xk+0.9(sk-xk)]} 0xksk
f5
v3(s3,u3)=60x3
阶段k： 物品（k=3,2,1）；
状态变量sk：从第k种物品到第3种物品可载重量； 决策变量xk：装第k种物品数量;
决策允许集合：Dk(sk)={xk|0xk[sk/wk]} 状态转移方程：sk+1=sk-wk*xk
阶段指标：vk(sk,xk)=ck*xk
0x1s1
x1
=max{-0.05x1+23.69s1}=23.69s1
0x1s1
s1
第 1
s2 …
年