最优指标函数（动态规划方程）：
?fk ( sk ) ? min[ d k ( sk , xk ) ? fk ?1 ( sk ?1 )
k ? n , n ? 1,? ,2,1)
边界条件： fn?1(sn?1) ? 0或1
3、动态规划的求解目标 最优解 最优策略 最有轨线
4、动态规划的求解方法：逆序法和顺序法两种 5、动态规划7个基本案例
4
? Vk ,4 ?
gi (si ,ui )
i? k
（7）动态规划基本方程
fk (sk ) ?
min {3 y
uk? U k ( sk )
?
uk
?
0.5( sk )
?
fk ? 1 ( sk ? 1 )}
（8）边界条件： f5(s5) ? 0
（7）设备更新问题
胜利家具厂购进了一台先进新设备，该设备的年效益及 年均维修费用、更新净费用如下表，试确定今后五年内的 更新策略，使总效益最大。（每年初进行决策是更新还是 保留）
5 F1 4
E2
5 2
G
6 E3 6
F2
3
4
5
6
解：最短路问题的动态规划模型为：
（1）划分阶段：按中转站空间位置将整体路线划分为6个阶段
（2）设状态变量sk： 表示每一阶段上的中转站个数sk∈Sk 。
（3）设决策变量uk：表示从某一阶段上、某一中转站出发到下
一阶段各个中转站的决定。 xk ∈Xk
（4）状态转移方程：Sk+1=xk(sk) 表示从第k阶段某一中转站sk出
? ?
s
k
?1
?1
xk ? K xk ? R
（5）阶段指标函数（效益）
vk (sk
8、边界条件： f4 ( s4 ) ? 0
k ? 3,2,1
（4）背包问题（决策变量要求为整数）
有一个人带一个背包上山，其可以携带物品的重量限度为10 公斤。设有3种物品可供选择，物品编号为1，2，3 。已知各 种物品每件重量为3、2、5公斤，且在上山过程中的作用（价 值）是携带数量分别是60、40、60。问此人应如何选择携带 物品（各几件），使所起作用（总价值）最大？（特点：决 策变量要求取整数）
（4） 状态转移方程为： s k ? 1 ? s k ? u k ? d k （5） 阶段指标函数：为阶段生产费用和库存费用之和，即
g k (sk , u k ) ? 3 y ? u k ? 0.5(sk )
y
?
?1
? ?
0
uk ? 0 uk ? 0
阶段k的生产费用
k阶段结束时库存费用
（6）过程指标函数：
用动态规划方法求解背包问题（整数规划）
MaxZ ? 60 x 1 ? 40 x 2 ? 60 x 3
? ? ?
3 x
x
i
1
?
? 0
2 x2 ? 5 x 且为整数，
3
?
10 i
?
1 , 2 ，3
（特点：决策变量要求取整数）
建立动态规划模型：
设：wk是第k种物品单位重量，ck为第k种物品单位价值 （1）划分阶段k：按可以装入物品的种类划分为3个阶段。
（1）最短路问题 （2）资源分配问题（投资问题、设备分配问题、背包问题） （3）连续生产控制问题（机器负荷分配） （4）生产与存储问题 （5）设备更新问题
（1）最短路问题
1
5 B1 3
A
6
3
B2
8 7
6
1
2
C1 6 8
C2 3 5
C3 3 3 8
C4 4
3
D1 2 2
D2 1 2 3
D3 3
E1 3
在第k 年继续再使用一年的效益。 u k（t）——在第k 年初已使用了t 年（或称役龄为t年）的设备
在第k 年继续再使用一年的维修费用。 c k（t）——在第k 年初已使用了t 年（或称役龄为t年）的设备
更换一台新设备的更新费用。 ? ——为折扣因子（0 ≤ ? ≤1），表示一年以后的单位收入
的价值是现年的 ? 单位。
?解：建立动态规划模型 （1）分阶段：按生产周期划分为4个阶段，k=4 （2）状态变量sk：第k月初（ k-1月末）的库存量，已知s1=s5=0
状态变量集合Sk：阶段k的库存量即不能超过库存容量4， 也不能超过阶段k至阶段4的需求总量(因为第5阶段的库 存量为0），故：
0 ? sk ? min{ 4, d k ? dk?1 ? ? ? d4}, k ? 1,2,3,4
g 3 ( x3 ) ? 2 x32
? 问如何分配投资数额才能使总效益最大（特点：收益函数是 连续的）。
? 解：可列出静态规划问题的模型如下
max
Z
?
4 x1 ? 9 x 2 ?
2
x
2 3
s .t .
? ? ?
x1 xi
? ?
x2 0,
? x3 (i ?
? 10 1,2 ,3 )
动态规划模型为：
1、分阶段：按投资项目的 个数分为三个阶段，k=1，2，3
4、状态转移方程： sk?1 ? sk ? xk
5、阶段指标函数：gi(si，xi)表示对第i的项目投入x台机器所获 得的收入值。
6、过程指标函数： V k , 3 ?
3
?
g i( si, xi)
i? k
7、动态规划递推模型：fk (sk ) ?
max {g
0? xk ? sk
k
(Leabharlann sk,xk)
?
fk ?1 ( sk ?1 )}
（5）阶段指标函数： gk (sk, uk ) ? 8uk ? 5(sk ? uk )
（6）过程指标函数： R 1 , 5
?
5
?
g k ( sk , uk )
k ?1
（7）动态规划递推模型fk(sk)为：
??? fk (sk ) ? 0m?uka?xsk{8uk ? 5(sk ? uk ) ? fk?1(0.7uk ? 0.9(sk ? uk ))} k ? 5,? ,2,1
（6）过程指标函数：V k , n
?
n
?
g i ( si, xi )
（7）动态规划递推方程：fk
i
(
?
s
k
k
)
?
max ?vk ( sk , xk ) ? ? fk ?1 ( sk?1 )
0 ? xk ?
sk wk
（8）边界条件：f4 ( s4 ) ? 0
（5）连续生产控制问题—机器负荷分配
胜利家具厂购进了一批先进的家具制造机器，该机器床 可在高低两种不同负荷下进行生产。
当机器在高负荷情况下的产量函数为 g=8u1，其中u1是 投入高负荷生产的机器数量，年完好率为 a=0.7；
当机器在低负荷情况下的产量函数为 h=5u2，其中u2是 投入低负荷生产的机器数量，年完好率为b=0.9；
假定开始生产时完好机器的数量为 1000台，试问每年 如何安排机器在高、低两种负荷下生产，可使 5年内生产的 产品总产量最高。
设备更新问题的一般性描述：
已知一台设备的效益函数为r（t），维修费用函数为u（t），更 新费用函数为c（t），在n 年内，每年年初都须作出决策，是继 续使用（Keep）旧设备还是更换（Replaceme）n一t 台新的设备， 使在n年内总净效益最大。 r k（t）——在第k 年初已使用了t 年（或称役龄为t年）的设备
发，选择决策xk，达到第k+1阶段中转站sk+1
（5）阶段指标函数： Rk(sk，xk)表示在第k阶段的中转站sk处，
选择决策xk 的距离值。
（6）子过程指标函数：R k，n示表示在第k阶段sk处到终点的距离
n
? Vk,n ? dk (sk , xk ) i?k
（7）基本方程： ?fk (sk ) ? min[ d k ( sk , xk ) ? fk?1(sk?1 )
解： 建立动态规划模型
（1）分阶段：按年度划分为5个阶段，k=5
（2）状态变量sk：表示第k年初拥有的完好机器台数。
（3）决策变量uk：表示为第k年度中分配给高负荷下生产的机
器台数；因此低负荷下生产的机器台数是sk-uk
决策允许集合：0? uk? sk
（4）状态转移方程：sk?1 ? auk ? b(sk ? uk) ? 0.7uk ? 0.9(sk ? uk), k ? 1,2,? ,5
车间
甲
乙
丙
设备 盈利
0
0
0
0
1
3
5
4
2
7
10
6
3
9
11
11
4
12
11
12
5
13
11
12
解：建立动态规划模型
1、分阶段：每个车间作为一个阶段，分为三个阶段，用k表示
2、决策变量xk: 表示分配给第k个车间的设备台数， 决策变量集合为： 0?xk?sk
3、状态变量sk: 表示分配给第k个车间至第3车间的设备台数； 状态变量集合为： ： 0?sk?5
?（3）决策变量uk：第k月的生产量。 ? 决策变量集合Uk：阶段产量必须不超过生产能力和第k阶 ? 段到第4阶段的总需求减去第k阶段初的库存量，同时要 ? 大于该阶段的市场需求 量与该阶段初库存量之差：
d k ? s k ? u k ? m in{ 6 , d k ? d k ? 1 ? ? ? d n ? s k }
（2）状态变量sk：第k次装载时，背包剩余的装载重量。
状态变量集合为：0 ? sk ? 10
（3）决策变量xk：第k次装载第k种物品的件数