【管理运筹学】第 8 章 | 动态规划（5，设备更新问题）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【管理运筹学】第 8 章 | 动态规划（5，设备更新问题）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

系列文章

引言

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

五、设备更新问题

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

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

$\alpha$ —— 折扣因子（ $0\leq \alpha \leq 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 \begin{Bmatrix} 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{Bmatrix}$ 其中， $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\}$ 。根据递推关系有 $g_5(t)=\max \begin{Bmatrix} 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{Bmatrix}$ 可得到 $g_5(1)=\max \begin{Bmatrix} R:&32-4-33+0=-5 \\ K:& 28-5+0=23\end{Bmatrix}=23,x_5(1)=K$ $g_5(2)=\max \begin{Bmatrix} R:&32-4-33+0=-5 \\ K:& 24-6+0=18\end{Bmatrix}=18,x_5(2)=K$ $g_5(3)=\max \begin{Bmatrix} R:&32-4-36+0=-8 \\ K:& 22-9+0=13\end{Bmatrix}=13,x_5(3)=K$ $g_5(4)=\max \begin{Bmatrix} R:&32-4-37+0=-9 \\ K:& 16-10+0=6\end{Bmatrix}=6,x_5(4)=K$ $g_5(5)=\max \begin{Bmatrix} R:&32-4-38+0=-10 \\ K:& 14-10+0=4\end{Bmatrix}=4,x_5(5)=K$ $j = 4$ ，第 4 年时，状态变量可取 ${1,2,3,4\}$ ，有 $g_4(1)=\max \begin{Bmatrix} R:&30-4-32+23=17 \\ K:& 26-5+18=39\end{Bmatrix}=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\}$ ，有 $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\}$ ，有 $g_2(1)=46,x_2(1)=K;g_2(2)=36,x_2(2)=R.$

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