多阶段决策的动态规划方法及实例分析

在生产和科学实验中，有一类活动过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，而在它的每一个阶段都需要做出决策，从而使整个过程达到最好的活动效果。因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线。这种把一个问题可看作一个前后关联且具有链状结构的多阶段过程（见图5-1），就称为多阶段决策过程，也称为序贯决策过程。这种问题就称为多阶段决策问题。

图5-1

在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义。因此，把处理它的方法称为动态规划方法。但是，一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因素，也可把它视为多阶段决策问题，用动态规划方法来处理。

多阶段决策问题很多，现举例如下。

例5-1（最短路线问题） 如图5-2 所示，给定一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），试求一条由A 到G的铺管线路，以使总距离为最短（或总费用最小）。

图5-2(www.xing528.com)

例5-2（机器负荷分配问题） 某种机器可以在高、低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g 和投入生产的机器数量 u1之间的关系为

这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终时完好机器的数量就为au（0＜ a＜ 1）；而在低负荷下生产时，产品的年产量h 和投入生产的机器数量 u2之间的关系为

相应的机器年完好率为b，0＜ b＜ 1。

假定开始生产时完好的机器数量为s1，要求制订一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，以使在五年内产品的总产量达到最高。

还有，如各种资源（人力、物力）分配问题、生产-存储问题、最优装载问题、水库优化调度问题、最优控制问题等，都具有多阶段决策问题的特性，均可用动态规划方法来求解。