最短路径问题

例子

计划从 A 地铺设一条输油管道到 E 地，中间须经过三个中间站。第一个中间站可设在 B1 或 B2，第二个中间站可以有 C1、C2、C3 三种选择，第三个中间站可取 D1 或 D2。各地之间的距离（单位为 km）标在箭线旁边，如图所示。要求确定一个方案，使得从 A 到 E 的距离最短。

思路

动态规划是解决这类问题最有效的方法之一。它的基本思路是：从终点 E 出发，反向求出倒数第一阶段，倒数第二阶段……直到起点 A 的各最短子路径。最终求出从起点到终点的最短路径，这种算法称为逆序法。

资源分配问题

设有某种资源(如煤、电、资金、机器设备、劳力等)，总数量为 a，可用于 n 种产品的生产，若以数量 x 用于第 i 种产品的生产，其相应的收益为 gi(Xi)，(i=1,2，…，n)，问应如何分配，才能使生产 n 种产品的总收益最大？

例子

某公司现有 400 万元用于投资甲、乙、丙三个项目，限制投资以百万元计，已知甲、乙、丙三项投资的可能方案及相应增加的收益如表所示，试确定使总收益最大的投资方案。

投资收益值

本例表面看来不是多阶段决策问题，但为了应用动态规划方法处理这类问题，通常把资源分配给一个或几个使用单位的过程作为阶段。比如在此问题中，规定对甲项目投资为第一阶段，对乙、丙项目投资依次为第二、第三阶段，于是项目阶段取值 k=1，2，3。取状态变量 S 为投入第 k 阶段至第 n 阶段的总投资额；决策变量 x 为第 k 阶段的投资额，则状态转移方程为：