对最短路问题：
最短路问题的特点：
找最短路线的方法：
，必是最短的能选择的不同路线来说出发到达终点的所有可从达终点的这段路线对于点出发到点，则由阶段通过如果最短路线在第
s
ssk
短路线求得由起点到终点的最终点的最短路线，最后各点到由后向前的方法，求出从最后一阶段开始，用来源于动态规划的最优化原理最短路问题的 基本方程,
11,m in kkkk
u
sfusd
k
kk sf k=4,3,2,1
055?sf?

由后向前迭代递推公式最优化原理,
一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略对最短路问题：
的最优策略（最短路）到是若 FCFEDC 1121
来说，必有：对状态 1C
A○
○ B1
○ F ○ B2○
B3
○ C1
○ C2
○ C3○ D2
○ D1
○ E2
○ E1
则不论前面 A如何到达 B,B又如何到达 C1
的最优策略到是 FDFED 212
的最优策略到是 FEFE 11?
上堂课的主要内容：
一、动态规划的基本概念
1,阶段,指对整个过程的自然划分,用 k表示
2、状态变量 sk
Sk ={sk} 第 k阶段的状态集合
：第 k阶段开始时所处的自然状况
3、决策变量,
当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策
kk su 时的决策变量阶段处于状态第 ksk
kk sU 允许取值的范围决策变量 )( kk su
4、状态转移方程
sk 第 k阶段的状态变量
kk su 时的决策变量阶段处于状态表示第 ksk
),(1 kkkk usTs状态转移方程：
5、策略,由各阶段的决策组成的序列称为策略

阶段全过程的策略始到第开从第一阶段初始状态原过程的策略
n
ssp n 11,1
nnn susususp?,,22111,1?即
策略?P —— 允许策略集合

阶段的策略始到第开阶段状态从第后部子过程的策略
n
sksp kknk,
nnkkkkknk susususp?,,11,即
6、指标函数用于衡量所选定的策略优劣的数量指标称为指标函数

的指标函数所对应时采用原过程策略在初始状态为 nnn pspsV,11,11,1,

所对应的指标函数策略时采用后部子过程阶段状态为在第
nk
knkknk
p
skpsV
,
,,,
最优策略达到最优的策略使指标函数
nkknk psV,,,：nkp,*
kk sf最优值函数

所对应的指标函数值时全过程采用最优策略初始状态为 npssf,1111 *
时的指标函数值止采用最优策略开始到过程终阶段状态从第
nk
kp sk
,*

kk sf
nkknkPp psVo p t
nknk
,,,
,,?
nkknk psV,,*,?
二、最优化原理,
一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略对最短路问题：
的最优策略（最短路）到是若 FCFEDC 1121
来说，必有：对状态 1C
A○
○ B1
○ F ○ B2○
B3
○ C1
○ C2
○ C3○ D2
○ D1
○ E2
○ E1
则不论前面 A如何到达 B,B又如何到达 C1
的最优策略到是 FDFED 212
的最优策略到是 FEFE 11?
找最短路线的方法：
短路线求得由起点到终点的最终点的最短路线，最后各点到由后向前的方法，求出从最后一阶段开始，用
kk sf 点的最短距离到阶段状态为从第 Esk k?
对最短路问题：
Af1,求
○ C1
○ A
○ B1
○ E ○ B2
○ B3
○ C2
○ C3○ D2
○ D18
4
5
89
6
16
10
9 67
7 3
8
4
2
3
最短路问题的 基本方程,
11,m in kkkku sfusd
k
kk sf k=4,3,2,1
055?sf
例 3（生产与存储问题）某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产 j个单位产品的费用为每月库存 i个单位产品的费用 E(i)=0.5i(千元），该厂最大库存容量为 3个单位，每月最大生产能力为 6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。
6,2,13 00?jj jjc
阶段 k=1,2,3,4
状态变量 sk=第 k个月月初的库存量
i月 1 2 3 4
g(i)需求 2 3 2 4
时产品的产量月月初库存量为第决策变量 kkk sksu?
状态转移方程,)(
1 kgsus kkk
计划结束的最小总费用时，从本月到月月初库存为：第最优值函数 kkk sksf )(
)0(1f求当 k=4时,)(
44 sf求
u4(s4)对应的总费用 =生产费 +库存费
3,2,1,04?s
)( 44 sEuc
)(m in 4444
4
sEucsf u




6,2,13
00
jj
jjc
生产费用
i月 1 2 3 4
g(i)需求 2 3 2 4
库存费 E(i)=0.5i，
最大库存容量为 3个单位，最大生产能力为 6个单位，
计划开始和计划期末库存量为零的最小总费用时，从本月到计划结束月月初库存为：第 kkk sksf )(
4s
0 1 2 3
4u 4
)( 44 sf 7
4*u
4
3
6.5
3
2
6
2
1
5.5
1
当 k=3时,)( 33 sf求的最小总费用时，从本月到计划结束月月初库存为第 333 3)( ssf?
3,2,1,03?s




6,2,13
00
jj
jjc
生产费用
i月 1 2 3 4
g(i)需求 2 3 2 4
库存费 E(i)=0.5i，
最大库存容量为 3个单位，最大生产能力为 6个单位，
计划开始和计划期末库存量为零
3s
)3(3 Euc
时，当 33?s 3333 usu 2,1,0：分析 )3(3f
0
1
2
3
0
4s
1
2
3
0
03?u
23?u
13?u
)1(4f
)2(4f
)3(4f
)3(3f3)3()2(,2)3()1(,1)3()0(m i n 444 fECfECfEC
433 )3()3(m in3 fEuCu
4s
44333 )()(m i n 33 sfsEsuCsu
u3(3)对应的总费用 =生产费 +库存费




6,2,13
00
jj
jjc
生产费用
i月 1 2 3 4
g(i)需求 2 3 2 4
库存费 E(i)=0.5i，
最大库存容量为 3个单位，最大生产能力为 6个单位，
计划开始和计划期末库存量为零 3s
4433333 )()(m i n
33
sfsEsuCsf su
3s
0
3u
2 3 4 5
4fEC 12 12,5 13 13.5
33 sf 12
3*3 su 2
1
1 2 3 4
11.5 12 12.5 13
11.5
1
2
0 1 2 3
8 11.5 12 12.5
8
0
3
0 1 2
8
8
0
11.5 12
4s
0 1 2 3
4u 4
)( 44 sf 7
4*u
4
3
6.5
3
2
6
2
1
5.5
1
当 k=2时,)(
22 sf求 3,2,1,02?s
的最小总费用时，从本月到计划结束月月初库存为第 222 2)( ssf?
)( 22 sEuc
)( 22 sf3322 )()( sfsEuC
22minsu
i月 1 2 3 4
g(i)需求 2 3 2 4
u2(s2)对应的总费用 =生产费 +库存费
3s
0
3u
2 3 4 5
4fEC 12 12,5 13 13.5
33 sf 12
3*3 su 2
1
1 2 3 4
11.5 12 12.5 13
11.5
1
2
0 1 2 3
8 11.5 12 12.5
8
0
3
0 1 2
8 11.5 12
8
0
k=3
当 k=2时,?)( 22 sf3322 )()( sfsEuC
22minsu
2s 0 1 2 3
2u
3 4 5 6
22 sf
18 18.5 16 173fEC
16
2*2 su 5
2 3 4 5
17.5 18 15.5 16.5
1 2 3 4
17
0 1 2 3
13.5 17 14.5 15.5
15.5
4
15
3
13.5
0
17.5 15 16
当 k=1时,)(
11 sf求 01?s
结束的最低总费用时，从第一个月到计划月初库存为第 01)0(1?f
22101 )(m in0
1
sfuCf u
1uc?
i月 1 2 3 4
g(i)需求 2 3 2 4
u1(0)对应的总费用 =生产费
k=2
2s
0 1 2 3
2u
3 4 5 6
22 sf
18 18.5 16 173fEC
16
2*2 su 5
2 3 4 5
17.5 18 15.5 16.5
1 2 3 4
17 17.5 15 16
0 1 2 3
13.5 17 14.5 15.5
15.5
4
15
3
13.5
0
22101 )(m in0
1
sfuCf u当 k=1时，
1s
0
1u
2 3 4 5
01f
2fC?
0*1u
22 21.5
21
2
21 21.5
最优生产方案：
2101?f结论, 20*1?u 50*2?u
02*3?u 40*4?u
个，个月生产第 21
个，个月生产第 52
个，个月生产第 03
个，个月生产第 44
21?总费用
)(m in 4444
4
sEucsf u时，4?k
时，3?k443333 )()(m i n
33
sfsEuCsf su
时，2?k?)( 22 sf3322 )()( sfsEuC
22
minsu
时，1?k
22101 )(m in0 1 sfuCf u
01?s?
0111 fsf2211 )()(m in
11
sfsEuCsu
055?sf
)()(m i n 5544
4
sfsEucu
11)()(m i n kkkksukk sfsEuCsf
kk
kguss kkk 1其中
1,2,3,4?k
生产存储问题的基本方程：
最优化原理：
一个过程的最优策略具有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略最短路问题的基本方程：
11,m in kkkk
u
sfusd
k
kk sf k=4,3,2,1
055?sf
生产存储问题的基本方程为：



0
1,2,3,4)(m i n
55
11
sf
ksfsEucsf kkkk
ukk k

kk usd,
11, kkkk
u
sfusdo p t
k
kk sf
k=n,n-1,n-2,…,3,2,1
011 nn sf?
动态规划的基本方程为：
其中 opt为最优，可取 min或 max