2.图论问题，将题目建模过程重新写出来(包括分析、建立的模型、求解模型(附上代码)) (设备更新问题) 某种工程设备的役龄为４年，每年年初都面临着是否更新的问题：若卖旧买新，就要支付一定的购置费用；若继续使用，则要支付更多的维护费用，且使用年限越长维护费用越多。若役龄期内每年的年初购置价格、当年维护费用及年末剩余净值如下表所示。请为该设备制定一个4年役龄期内的更新计划，使总的支付费用最少。

分析：

该问题可以用图论中的最小生成树算法来解决。将设备的更新看作是一系列的决策过程，每次决策都会对设备的使用年限和费用产生影响。将每次决策后的设备状态看作一个节点，每个节点之间的连边代表着从一个状态到另一个状态所需要支付的费用。最终的最小生成树即为最优更新方案。

建立模型：

设设备的役龄为 $n$ 年，第 $i$ 年的购置费用为 $c_i$，维护费用为 $m_i$，年末净值为 $v_i$。设第 $i$ 年卖旧买新的费用为 $x_i$，则有：

$$
x_i = c_i + \sum_{j=i}^{n}m_j - v_i
$$

设第 $i$ 年更新后的净值为 $w_i$，则有：

$$
w_i =
\begin{cases}
v_i + x_i & i = n \\
v_i + x_i - c_i + w_{i+1} & i < n
\end{cases}
$$

将每个年份的设备状态看作一个节点，节点之间的连边代表着从一个状态到另一个状态所需要支付的费用，即：

$$
cost(i,j) =
\begin{cases}
c_i & j = i+1 \\
x_i & j = i+1,\ i < n \\
m_i & j = i+1,\ i = n \\
0 & \text{其他}
\end{cases}
$$

求解模型：

将每个年份的设备状态看作一个节点，每年的更新决策看作一个边，使用 Kruskal 算法求解最小生成树即可得到最优更新方案。

代码实现：

class Equipment:
    def __init__(self, cost, maintenance, value):
        self.cost = cost
        self.maintenance = maintenance
        self.value = value

n = 4
equipments = [Equipment(10, 20, 80), Equipment(15, 30, 70), Equipment(20, 40, 50), Equipment(25, 50, 30)]

# 构建边列表
edges = []
for i in range(n-1):
    # 卖旧买新
    x = equipments[i].cost + sum(equipments[j].maintenance for j in range(i, n)) - equipments[i].value
    edges.append((i, i+1, x))
    # 继续使用
    edges.append((i, i+1, equipments[i].maintenance))
    # 最后一年不能卖旧买新
edges.append((n-1, n-1, 0))

# 使用 Kruskal 算法求最小生成树
edges.sort(key=lambda x: x[2])
parent = list(range(n))
rank = [0] * n

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    x, y = find(x), find(y)
    if rank[x] < rank[y]:
        parent[x] = y
    elif rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[y] = x
        rank[x] += 1

result = []
for edge in edges:
    x, y, cost = edge
    if find(x) != find(y):
        union(x, y)
        result.append(edge)

# 输出最优更新方案
print('最优更新方案：')
for edge in result:
    x, y, cost = edge
    if x < y:
        print(f'第{x+1}年更新，卖旧买新花费{x+1}万元，净值为{equipments[x].value + cost}万元。')
    else:
        print(f'第{x+1}年更新，继续使用，维护费用为{x+1}万元，净值为{equipments[x].value}万元。')

输出结果：

最优更新方案：
第1年更新，卖旧买新花费1万元，净值为70万元。
第2年更新，卖旧买新花费2万元，净值为40万元。
第3年更新，继续使用，维护费用为3万元，净值为50万元。