第五章 动态规划 1 多阶段决策过程及实例 2 动态规划的基本概念和基本方程 3 动态规划的最优性原理和最优性定理 4 动态规划与静态规划的关系1 多阶段决策过程及实例 在实际中，有一类问题可以看作是一活动的 过程，由于它的特殊性，可将过程分为若干个相 互联系阶段，在每个阶段都要依据该阶段所处的 状态作出相应的决策，该决策又引起该阶段状态 的转移，决定了下一阶段的状态，当每个阶段的 决策确定后，由这些决策组成一个决策序列，即 整个过程的一条活动路线。这类活动过程称为多 阶段决策过程。这类问题称为多阶段决策问题。 1 2 n 状态 状态 状态 状态 状态 决策 决策 决策 例1 最短路线问题 如下图，是一线路网络，两点之间连线上的数字表 示两点之间的距离（或费用）试求一条由A 到G 的铺管线 路，使总距离为最短（或总费用最小）。 1 状态 状态 状态 状态 状态 决策 决策 决策 2 3 4 5 6 状态 状态 决策 决策 决策 B 2 C 3 D 2 E 3 F 2 G B 2 C 3 D 2 E 3 F 2 G A V 6,6 =3 A B 1 B 2 C 1 C 2 C 3 C 4
