设备更新问题-动态规划

孙泽辉

发布于：2021年8月21日

字数：914字

时长：4分钟

次浏览

讲的超级细的运筹学up更新了，讲的太清楚了赶紧记下来！。

题目：

设某台新设备的年效益及其年均维修费、更新净费用如表所示，试确定今后5年内的更新策略，使总收益最大。

class item:
    def __init__(self, _r, _u, _c):
        # 效益r
        self.r = _r
        # 维修费u
        self.u = _u
        # 更新费c
        self.c = _c

# 下标代表役龄（设备用了多少年）
itemList = [
    item(5, 0.5, 0.5),
    item(4.5, 1, 1.5),
    item(4, 1.5, 2.2),
    item(3.75, 2, 2.5),
    item(3, 2.5, 3),
    item(2.5, 3, 3.5)
]

解法

分析变量

因为要求今后5年的策略（是更新还是保留），所以

设：年份k = 1,2,3,4,5

状态变量$S_k$：第k年年初设备的役龄，默认$S_1 = 0$（新设备，第一年的役龄是0）

决策变量$X_k$ ：第k年做出的决策，保留（keep），更新（replacement）

状态转移方程

这是up画决策树，画的超级好~

第0年的时候没得选也没收益一般默认选择保留，不会在刚开始就更新的

显然，当设备年初更新的时候，该年份设备用了一年；当设备保留的时候，该设备的役龄等于上一个状态的役龄+1

既然题目让求最优，那么算出每个阶段能赚到最多的钱，汇总到一起就是能赚到的钱了。

$V_k(S_k,X_k) = \begin{cases} r_k(S_k)\ -\ u_k(S_k) &X_k = K \\ \\ r_k(0)\ - u_k(0)\ +c_k(S_k) &X_k = R \end{cases} \\$

最优指标函数$f_k(S_k) = max(K,R)$

第k年第Sk阶段所获得的收益

这里我们用的逆推法，第k年的收益等于第k年的最优决策所带来的的收益+后一年的最优收益，用公式表示：

$V_k(S_k,X_k) = \begin{cases} f_k(S_k)=max[\ v_k(S_k,X_k)\ +\ f_{k+1}(S_{n}+1)\ ] &X_k = K \\ \\ f_k(S_k)=max[\ v_k(S_k,X_k)\ +\ f_{k+1}(1)\ ] &X_k = R \\ \\ f_{n+1} (S_{n+1})=0 \end{cases} \\$

初始化边界之外的收益为0

保留的时候的年收益是下一年的该年役龄+1的年收益

更新的时候年收益是仅用了下一年一年的役龄的年收益

编程

既然公式推出来了，写代码也就很简单了。

# 初始化一个6*6的dp数组
dp = [[0 for i in range(6)] for j in range(6)]

# 第i阶段
for i in range(4, -1, -1):
    # 第i阶段可能的设备役龄
    for j in range(i + 1):
        keep = itemList[j].r - itemList[j].u
        replacement = itemList[0].r - itemList[0].u - itemList[j].c

        dp[i][j] = max(keep + dp[i + 1][j + 1], replacement + dp[i + 1][1])
print(dp[0][0])

因为当前状态仅仅依赖上一个状态，所以可以将二维dp数组优化成一维的。

# 初始化一个6*6的dp数组
dp = [0 for i in range(6)]

helper = [0 for i in range(6)]

# 第i阶段
for i in range(4, -1, -1):
    # 第i阶段可能的设备役龄
    for j in range(i + 1):
        keep = itemList[j].r - itemList[j].u
        replacement = itemList[0].r - itemList[0].u - itemList[j].c

        dp[j] = max(keep + helper[j + 1], replacement + helper[1])
    helper = dp.copy()
print(dp[0])

总结

动态规划真好玩，像是滚雪球。

附up视频：

运筹学-16-动态规划之设备更新问题_哔哩哔哩_bilibili