最优法求解？

来源：百度知道 编辑：UC知道 时间：2024/05/11 15:25:50
3.某台机器可连续工作4年，也可以每年末卖掉，换一台新的。已知于各年出购置一台新机器的价格及不同役龄机器年末的处理价格如下表所示，又新机器第一年运行及维护费用为0.3万元，使用1-3年后机器每年的运行及维护费用为：0.8，1.5，2.0万元。试确定该机器的最优更新策略，使4年内用于更换，购买及运行维修的总费用为最省（单位万元）
J 第一年 第二年 第三年 第四年
年初购置价 2.5 2.6 2.8 3.1
使用J年后的处理价 2.0 1.6 1.3 1.1

解：把求得总费用最少问题化为最短路问题，用vi表示“第i年初购进一台新机器”，设v5表示第4年年底，从vi到v5各画一条弧，弧（vi，vj）表示在第i年年初购进的一台新机器一直使用到第j年年初。然后对每条弧赋予权数，弧（vi，vj）的权数即为从第i年年初购进新机器使用到第j-1年年底所花费的购置费及更换、运行维修费的综合。
权数表（单位：万元）

这是一个最短路的问题，用 Dijkstra 算法求解可得到这问题的解为 4.8，
即在 4 年内购买、更换及运行维修最小的总费用为：4.8 万元。
最优更新策略为：第一年末不更新
第二年末更新
第三年末不更新
第四年末处理机器