当 x2 3 时，r2 (4,3) f3(4 3) 11 4 ； 当 x2 4 时，r2 (4,4) f3(4 4) 11 0 11 ； 当 x2 0 时，r2 (4,0) f3(4 0) 0 12 12 ； 由于 s2 4 ，不可能分2厂5台设备，故 x2 5 时，
s2 T1(s1, x1) s1 x1 s3 T2 (s2 , x2 ) s2 x2
从sk 与xk 的定义，可知
s3 x3
以下我们从第三阶段开始计算。
管理运筹学
14
第三阶段:
显然将 s3 (s3 0,1,2,3,4,5)台设备都分配给第3工厂时， 也就是s3 x3 时，第3阶段的指标值（即第3厂的盈利）
6+6=12
12
D2
C2
7+10=17
5+6=11
11
D2
C3
1+10=11
6+6=12
11
D1
分析得知：如果经过C1，则最短路为C1-D2-E； 如果经过C2，则最短路为C2-D2-E； 如果经过C3，则最短路为C3-D1-E。
管理运筹学
4
第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分 析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题：
即最优2子过程最优指标函数值为
f2 (s2 ) mxa2 x[r2 (s2, x2 ) f3(s3)]
管理运筹学
17
因为 s3 s2 x2,上式也可写成
其数值计算f2 (如s2 )表 m1x0a2 －xr27(所s2,示x2 )。 f3(s2 x2 )
s2 x2
0
0
1
00 －
表10－7
r2 (s2 , x2 ) f3 (s3 x2 )
本阶段最优终点 （最优决策)
E E
管理运筹学
3
第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点 和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路 径问题：
表10-2
阶段3
本阶段始点 本阶段各终点（决策）
（状态）
D1
D2
本阶段最优终点 到E的最短距离 （最优决策)
C1
8+10=18
为最大，即
max x3
r3
(s3
,
x3
)
r3
(s3
,
s3
)
由于第3阶段是最后的阶段，故有
f3
(s3
)
max x3
r3
(s3
,
x3
)
r3
(s3
,
s3
).
其中 x3可取值为0,1,2,3,4,5。其数值计算见表10－6。
管理运筹学
15
s3 x3
0
00
1－
2－
3－
4－
5－
表10－6
r3 (s3, x3 )
opt fk (sk )
{rk (sk , xk ) fk1(sk1)}
xk Dk (sk )
k 1, 2,L , n
上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式 可以
写为
opt fk (sk )
{rk (sk , xk ) fk1(sk1)}
xk Dk (sk )
表10-4
本阶段始 点(状态)
A
阶段1 本阶段各终点（决策）
B1
B2
B3
B4
4+12=16 3+13=16 3+14=17 2+12=14
到E的最 本阶段最优终 短距离 点(最优决策)
12
C2
最后，可以得到：从A到E的最短路径为A B4 C3 D1 E
管理运筹学
6
以上计算过程及结果，可用图2表示，可以看到，以上方法不仅 得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最 短路径。
4 14
A
3
3
2
12 B1 2
61
13 4 B2 7
2
48 B3 3 14
75 1
B4 12
12 C1 8
6
11 7 C2
5
1 C3 6 11
10
D1 10
0
E
D2 6 6
以上过程，仅用了22次加法，计算效率远高于穷举法。
管理运筹学
7
§2 基本概念、基本方程与最优化原理
一、基本概念：
1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划 分。
18
其中在 s2 4 的这一行里， 当 x2 1 时，
r2 (s2 , x2 ) f3(s2 x2 ) r2 (4,1) f3(4 1) r2 (4,1) f3(3) 5 11 16
当 x2 2 时，可知 r2 (s2, x2 ) f3(s2 x2 ) r2 (4,2) f3(4 2) r2 (4,2) f3(2) 10 6 16;
r2 (4,5) f3(4 5) 栏空着不填。 从这些数值中取得最大即得 f2 (4)，即有 f2 (4)=16。在此行
中我们在取最大值的 r2 (s2 , x2 ) f3(s2 x2 )上面加一横以
示区别，也可知这时x2 的最优决策为1或2。
管理运筹学
19
第一阶段：
把 s1(s1 5) 台设备分配给第1，第2，第3厂时，最大
盈数利值为计算f1(见5) 表 m1xa10x－[r1(85, x1) f1(5 x1)],其中 x1可取值0,1,2,3,4,5.
s1 x1 0
表10-8
r1(5, x1) f2 (5 x1)
1
2
3
4
5 f1( x) x*1
5 0 21 3＋16 7 14 9+10 12+5 13+0 21 0,2
包中物品的价值最高。
这个问题可以用整数规划模型来描述。设xi为第i种 物品装入背包的件数（i =1, 2, …, n），背包中物品的总
价值为z，则
Max z = c1x1+c2x2+ … +cnxn s.t. w1x1+w2x2+…+wnxn≤W x1, x2, …, xn0 且为整数。
管理运筹学
22
12 13 14 12
本阶段最优终 点（最优决策)
C2 C3 C3 C3
分析得知：如果经过B1，则走B1-C2-D2-E； 如果经过B2，则走B2-C3-D1-E； 如果经过B3，则走B3-C3-D1-E； 如果经过B4，则走B4-C3-D1-E。
管理运筹学
5
第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对始点和终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：
1
2
3
4
5 f3(s3) x*3
－－ －－－ 0 0
4 － －－－ 4 1
－ 6－ －－ 6 2
－ － 11 － － 11 3
－ － － 12 － 12 4
－ － － － 12 12 5
管理运筹学
16
其中 x*3 表示取3子过程上最优指标值f3(s3)时的 x3
决策，例如在表10-6中可知当s3 =4时，有 r3(4,4) 12; 有
第十章 动态规划
管理运筹学
1
§1 多阶段决策过程最优化问题举例
例1 最短路径问题
下图表示从起点A到终点E之间各点的距离。求A到E的最
短路径。
4
A
3
2 B1
1 6
4 B2 7
2
C1
8
6
7 C2 5
D1
10
E
3 2
48
B3 3
1 6
C3
D2
6
75 1
4
管理运筹学
2
讨论： 1、以上求从A到E的最短路径问题，可以转化为四个性质完全相
k 1, 2,L , n
以上式子称为动态规划最优指标的递推方程，是动态规划的基本 方程。
终端条件：为了使以上的递推方程有递推的起点，必须要设定最 优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1) = 0。
管理运筹学
11
三、最优化原理 作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状
同，但规模较小的子问题，即分别从Di 、Ci、Bi、A到E的最短路 径问题。
从最短路上每一点到终点的部分道路,也一定是从该点到终点的最短路. 第四阶段：两个始点D1和D2，终点只有一个；
表10-1
阶段4
本阶段始点 本阶段各终点（决策） 到E的最短距离
（状态）
E
D1
10
10
D2
6
6
分析得知：从D1和D2到E的最短路径唯一。
管理运筹学
20
知 x*2 2，再由s3 s2 x*2 3 2 1 ,求得 x*3 s3 1 ， 即分配给甲厂2台，乙厂2台，丙厂1台。
这两种分配方案都能得到最高的总盈利21万元。
管理运筹学
21
二、背包问题
设有n种物品，每一种物品数量无限。第i种物品每件
重量为wi公斤，每件价值ci元。现有一只可装载重量为W 公斤的背包，求各种物品应各取多少件放入背包，使背
xk+1, …, xn)称指标具有可乘性。
管理运筹学
9
二、基本方程：
最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指 标Vk,n的最优值，即
opt f k (sk )