运筹学-7复习 (1) _原创文档.pdf

commercialuse

第7章动态规划

7.1解多阶决策问题的动态规划法

1.多阶决策问题的例

(1)最优路径问题—多阶决策问题的例

为了直观，先从最优路径问题谈起，它可以看作一个多阶决策过程。通过最优路径问题

的解可以看到用动态规划法解多阶决策问题的基本思想。

P

P621P

考虑图7-1所示的最优路径问题。一汽车由S点出发到终点F，P和Q是一些可以通

13

4

过的点。图中两点间标出的数字是汽车走这一段路所需的时间(单位为小时)。最优路径问题

24

4SF

是确定一个路径，使汽车沿这条路径由点出发达到点所用时间最短。最优路径问题可以

SPFQ

看作一个多阶决策问题，由到城市甲是第1个阶段，第1个结点或第2个结点做为

S

11

51PQP

第1阶段可以通过的两个站点，由城市甲到城市乙是第2阶段，这个阶段是从或到或

63112

Q，由城市乙到城市丙是第3阶段，这个阶段是从P或Q到P或Q，由城市丙的P或Q

272223333

到F做为第四阶段。QQQ

123

（2）最优路径问题的解

对最优路径问题，存在一个非常明显的原理，即最优路径的一部分还是最优路径。换句

图7-1最优路径问题

话说，如果SQPQF是所求的最优路径，那么，汽车从这一路径上的任何一点，例如P，

1232

出发到F的最优路径必为PQF。这一原理称为最优性原理。根据这一原理可以由后向前

23

递推求出最优路径。

如果汽车已到Q，由Q直接到F用3小时，如果汽车已到P，由P直接到F用4小

3333

时，这两个数字分别标在图7-2中Q和P旁的方括号内。再向前推一步，设