系列文章

【管理运筹学】第 8 章 | 动态规划（1，多阶段决策过程与动态规划基本概念）
【管理运筹学】第 8 章 | 动态规划（2，动态规划的基本思想与模型求解）
【管理运筹学】第 8 章 | 动态规划（3，资源分配问题）
【管理运筹学】第 8 章 | 动态规划（4，生产与储存问题）
【管理运筹学】第 8 章 | 动态规划（5，设备更新问题）

---

引言

在工业和交通运输企业中，经常碰到设备陈旧或部分损坏需要更新的问题。从经济上来分析，一种设备应该用多少年后进行更新较为恰当，即更新的最佳策略如何，从而使在某一时间内的总收入达到最大（或总费用达到最小）。

---

五、设备更新问题

现以一台机器为例，随着使用年限的增加，机器的使用效率降低，收入减少，维修费用增加。而且机器使用年限越长，它本身的价值就越小，因而更新时所需的净支出费用就愈多。

设 $I_j(t)$ —— 在第 $j$ 年机器役龄为 $t$ 年的一台机器运行所得收入；$O_j(t)$ —— 在第 $j$ 年机器役龄为 $t$ 年的一台机器运行所需费用；$C_j(t)$ —— 在第 $j$ 年机器役龄为 $t$ 年的一台机器更新时所需净费用；

$\alpha$ —— 折扣因子（$0\le \alpha \le 1$），表示 1 年以后的单位收入价值视为现年的 $\alpha$ 单位；$T$ —— 在第 1 年开始时，正在使用的机器的役龄；$n$ —— 计划的年限总数；

$g_j(t)$ —— 在第 $j$ 年开始使用一个机器役龄为 $t$ 年的机器时，从第 $j$ 年至第 $n$ 年内的最佳收入；$x_j(t)$ —— 决策变量，表示在第 $j$ 年开始时的决策。

5.1 问题分析

可以从两个方面对问题进行分析。若在第 $j$ 年开始时购买了新机器，则从第 $j$ 年至第 $n$ 年得到的总收入应等于：在第 $j$ 年中新机器获得的收入 — 在第 $j$ 年的运行费用 — 在第 $j$ 年开始时役龄为 $t$ 年的机器的更新费用 + 第 $j+1$ 年开始使用役龄为 1 年的机器从第 $j+1$ 年至第 $n$ 年的最佳收入。

若在第 $j$ 年开始时继续使用役龄为 $t$ 年的机器，则从第 $j$ 年至第 $n$ 年得到的总收入应等于：在第 $j$ 年由役龄为 $t$ 年的机器得到的收入 — 在第 $j$ 年役龄为 $t$ 年的机器的运行费用 + 在第 $j+1$ 年开始使用役龄为 $t+1$ 年的机器从第 $j+1$ 年至第 $n$ 年的最佳收入。

通过比较两者大小来进行决策，则递推关系的数学表达如下：$$g_j(t)=\max \left\{\begin{array}{cc}R:& I_j(0)-O_j(0)-C_j(t)+\alpha g_{j+1}(1)\\ K:& I_j(t)-O_j(t)+\alpha g_{j+1}(t+1)\end{array}\right\}$$ 其中，$j=1,2,\cdots ,n;t=1,2,\cdots ,j-1,j+T-1$ ；字母 $K$ 表示 keep ，保留；字母 $R$ 表示 replacement ，更新机器。更新机器需要支付更新费用。

研究今后 $n$ 年的计划，故添加边界条件 $g_{n+1}(t)=0$ ；对于 $g_1(t)$ 来说，允许的 $t$ 值只能为 $T$ ，因此此时未购入新机器，只有已经使用了 $T$ 年的旧机器。

上述设备更新问题，是以机龄为状态变量，决策时保留或更新两种。如还考虑对机器进行大修作为一种决策，那时所需的费用和收入，不仅取决于机龄和购置的年限，也取决于上次大修后的时间。因此，必须使用两个状态变量对系统进行描述。

5.2 算例

【例】假设 $n=5,\alpha =1,T=1$ ，有关数据如下表所示。试制定 5 年内中的设备更新策略，使得 5 年内的总收入达到最大。

解释一下表中数据的意思。第 $j$ 年机龄为 $t$ 年的机器，那么它的年序应该为 $j-t$ 。因为第 $j$ 年的时候，这台机器就已经使用了 $t$ 年，说明它是第 $j-t$ 年首次开始工作的。那么 $I_5(0)$ 表示第 5 年的新机器运行的收入，查表，年序为 5-0=5 ，是 32 。$I_3(2)$ 表示第 3 年机龄为 2 年的机器运行所得收入，那么查表，3-2=1，第一年中机龄为 2 年的收入 20 。同理，有 $C_5(2)=33,C_3(1)=31$ ，其余以此类推。

$j=5$ ，即第 5 年时，由于 $T=1$ ，说明第一年时的机器机龄就有 1 年了，那么第 5 年状态变量机龄 $t$ 可取 { 1 , 2 , 3 , 4 , 5 } \{1,2,3,4,5\} {1,2,3,4,5} 。根据递推关系有 $$g_5(t)=\max \left\{\begin{array}{cc}R:& I_5(0)-O_5(0)-C_5(t)+g_6(1)\\ K:& I_5(t)-O_5(t)+g_6(t+1)\end{array}\right\}$$ 可得到 $$g_5(1)=\max \left\{\begin{array}{cc}R:& 32-4-33+0=-5\\ K:& 28-5+0=23\end{array}\right\}=23,x_5(1)=K$$ $$g_5(2)=\max \left\{\begin{array}{cc}R:& 32-4-33+0=-5\\ K:& 24-6+0=18\end{array}\right\}=18,x_5(2)=K$$ $$g_5(3)=\max \left\{\begin{array}{cc}R:& 32-4-36+0=-8\\ K:& 22-9+0=13\end{array}\right\}=13,x_5(3)=K$$ $$g_5(4)=\max \left\{\begin{array}{cc}R:& 32-4-37+0=-9\\ K:& 16-10+0=6\end{array}\right\}=6,x_5(4)=K$$ $$g_5(5)=\max \left\{\begin{array}{cc}R:& 32-4-38+0=-10\\ K:& 14-10+0=4\end{array}\right\}=4,x_5(5)=K$$ $j=4$ ，第 4 年时，状态变量可取 { 1 , 2 , 3 , 4 } \{1,2,3,4\} {1,2,3,4} ，有 $$g_4(1)=\max \left\{\begin{array}{cc}R:& 30-4-32+23=17\\ K:& 26-5+18=39\end{array}\right\}=39,x_5(1)=K$$ 同理，有 $g_4(2)=29,x_4(2)=K;g_4(3)=16,x_4(3)=K;g_4(4)=13,x_4(4)=R.$

$j=3$ 时，状态变量可取 { 1 , 2 , 3 } \{1,2,3\} {1,2,3} ，有 $g_3(1)=48,x_3(1)=K;g_3(2)=31,x_3(2)=R;g_3(3)=27,x_3(3)=R;$

$j=2$ 时，状态变量可取 { 1 , 2 } \{1,2\} {1,2} ，有 $g_2(1)=46,x_2(1)=K;g_2(2)=36,x_2(2)=R.$

$j=1$ 时，状态变量可取 { 1 } \{1\} {1} ，有 $$g_1(1)=\max \left\{\begin{array}{cc}R:& 22-6-32+46=30\\ K:& 18-8+36=46\end{array}\right\}=46,x_1(1)=K.$$ 最后，根据上面的计算结果回溯。第一年，机龄为 1 年，最佳策略为保留；第二年，机龄为 2 年，最佳策略为更新；第三年，机龄变为 1 年，最佳策略为保留；第四年，机龄为 2 年，最佳策略为保留；第五年，机龄为 3 年，最佳策略为保留。

---

写在最后

设备更新问题确实不简单，很有实际意义，不过，只要正确建好了模型，剩下的就是代数字进去算。回忆一下之前的生产与储存问题和资源分配问题，顿时感觉小巫见大巫了。

那到此，大纲要求的三个问题，到此就完结了，后面我们就来看看剩下的两章节内容。