13 13
1
C1
10
6 81Βιβλιοθήκη 185 3B116 8
3
6
2 3 D1 2 1 D2 2
7
7
E1
5 5 5 5 E2 2 6
3 4
A
B2
7
C2 5 9 9 3 C3 C4
3 4
6
F1 F2
6
4
3 3 3
G
8
6 12
8 3
9
D3
3
E3
Ⅰ
Ⅱ
Ⅲ
Ⅳ
Ⅴ
Ⅵ
• 例2、某企业有5000万元的一笔投资款，拟投资三个 项目，对每个项目的投资方案、投资金额、投资效益 （新增加收益）如表。问这笔资金应如何分配使用， 使总收益最大？
0 2 3 4
0 7 11 13
一、确定基本要素及递推关系
• 1、 企业Ⅰ K=3 过程进行方向 企业Ⅱ K=2 企业Ⅲ K=1
• 2、状态转移方程 • 3、递推关系式
sk Sk 1 xk 1
f 0* ( S 0 ) 0, * * f k 1 ( S k 1 ) max{Rk 1 ( S k 1 , xk 1 ) f k ( S k )} xk 1 Sk 1 {Rk 1 ( S k 1 , xk 1 ) f k* ( S k 1 xk 1 )} max xk 1 Sk 1
第二节 动态规划的基本方法
• 动态规划的基本解法： • 1、网络图解法； • 2、表格法； • 3、迭代法。 • 三种方法的共同点： • 都是用逆推计算方法，即由最后一个阶 段往回推到最前的一个阶段实现最优。
一、网络图解法
• 例1、如图给定一个线路网络，两点之间连线上的 数字表示两点之间的距离（或费用），试求一条由 • A G 的铺管线路，使总距离最短（或费用 最少）。
投资金额 （万元） 0 1000 2000 3000 4000 投资效益（万元）
项目Ⅰ
0 1500 2600 3500 ----
项目Ⅱ
0 ---2800 3900 4000
项目Ⅲ
0 1300 2500 -------
4100
B
2000(2600) 5300
3000(3900) 2000(2800)
表一
S1（万元） 0 1
f (S1（万元） ) 0 0
* 1
* x1
0 0
2 3 4 4 4 4
2 3 4 5 6 7
7 11 13 13 13 13
表二
表三
三、连续型动态规划的函数迭代法
三、函数迭代法求解动态规划的步骤
0
F
0(0) 1000(1300)
6800
C
1000(1500) 2800 3000(3500)
4000(4200) 2000(2800) 1300 3000(3900)
A
2000(2800)
4000(4000)
G
2000(2500) 200(2500) 2500
I
D
0(0) 6400
0(0)
E
3000(3900)
H
Ⅰ
Ⅱ
Ⅲ
二、表格法
• 例3 某公司欲将7万元的资金分配给下属三个企业， 资金分配方案及在此方案下各企业的预期收益如表， 公司在现有方案中，采用哪种组合才使公司的预期 收益最高？
企业
分配方案 及收益 分配
Ⅰ
收益 分配
Ⅱ
收益 分配
Ⅲ
收益
1 2 3 4
0 1 2 3
0 5 8 10
0 1 3 5
0 3 9 11