一、问题引入

某工厂拟在今后三年内购买某种设备5台，考虑到设备维护、现金等各种因素后，预计在第一、第二、第三年初购买该设备可获纯利润如下表所示。问如何指定购买计划才能使该厂获得最大利润。

二、问题求解

（一）关键概念的理解

要使用动态规划的思想解决这个多阶段的决策问题，首先就要明白阶段、状态、决策、策略、状态转移方程、指标函数和最优值函数等基本概念。详情可参见笔者的相关概念理解文章算法导引之动态规划01。

（二）本题分析与解决

为应用动态规划方法求解，先应明确一下问题：

1. 以购买设备时间为顺序，将问题划分成3个阶段；
2. 引进4个状态变量x₁,x₂,x₃,x₄，其中，x_k(k=1,2,3,4)表示第k年初至第三年末可购买的设备台数，并且规定上一年末与下一年初为同一时刻。
3. 决策变量y_k表示第k年初购买设备台数；
4. 状态转移方称为 x_k+1=x_k-y_k；
5. 阶段指标P_k(y_k)表示第k年购买yk台设备所获纯利润；最优指标函数f_k(x_k)表示第k年初至第三年末购买x_k台设备所能获得的最大利润;
6. 由以上所设可得本题的动态规划的基本方程为：
   
   递归出口为：
   
   由上式可得：
   
   k=2时，对应x₂=0、1、2、3、4、5可分别计算如下：
   
   
   
   
   
   
   由此得最优购买方案为2，2，1或者0，2，3，最优值即最大利润为21万元。需要明确的是，动态规划法解决多阶段的决策问题，最优值是唯一的，但是最优方案或者说最优解却不是唯一的。

写在最后：本例来自于专业课老师课上所授，希望对大家理解多阶段决策问题有所帮助。从此例中希望大家建立起多阶段决策问题和动态规划法解题的概念和分析思路，但其实真正在解决问题的时候，尤其在将思路变成算法进而编写为程序的时候我们不会这样严格划分阶段，一来是很多实际问题的阶段划分并不明显，不好把握，二来是这样做无非给自己增加了工作量，使得问题繁琐。就笔者目前接触到的动态规划法解决问题大多数情况下都是采用递归的思路加上备忘录的方法，记录子问题的解来避免冗余计算才是动态规划法最突出的特点。