用networkx解决图论问题(1)

设备更新问题

例:某种工程设备的役龄为4年,每年年初都面临着是否更新的问题:若卖旧买新,就要支付一定的购置费用;若继续使用,则要支付更多的维护费用,且使用年限越长维护费用越多。若役龄期内每年的年初购置价格、当年维护费用及年末剩余净值如下表所示。

年份 1 2 3 4
年初购置费用/万元 25 26 28 31
当年维护费用/万元 10 14 18 26
年末剩余净值/万元 20 16 13 11

请为该设备制订一个4年役龄期内的更新计划,使总的支付费用最少。
解:可以把这个问题化为图论中的最短路径问题。
构造赋权有向图D = (V,A,W),其中顶点集V = {v1,v2,…,v5},这里vi(i=1,2,3,4)表示第i年年初的时刻,v5表示第4年年末的时刻,A为弧的集合,邻接矩阵W = (wij)5X5,这里wij为第i年年初至第j年年初(或j-1年年末)期间所支付的费用,计算公式为

$w_{ij}=p_{i}+\sum\limits_{k=1}^{j-i}a_{k}-r_{j-i} $

其中pi为第i年年初的购置价格,ak为第k年当年的维护费用,ri为已使用i年的旧设备的出售价格(残值)。则邻接矩阵为

$ W = \begin{bmatrix} 0 & 15 & 33 & 54 & 82 \\ \infty & 0 & 16 & 34 & 55 \\ \infty & \infty & 0 & 18 & 36 \\ \infty & \infty & \infty & 0 & 21 \\ \infty & \infty & \infty & \infty & 0 \end{bmatrix} $

那么制订总的支付费用最小的设备更新计划,就是在下图所示的有向图D中寻找顶点v1到顶点v5的费用最短路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

p = [25, 26, 28, 31] # 购置价格
a = [10, 14, 18, 26] # 维护费用
r = [20, 16, 13, 11] # 售出残值

w = np.zeros((5, 5)) # 权值矩阵初始化
for i in range(5):
for j in range(i+1, 5):
w[i, j] = p[i] + np.sum(a[0:j-i]) - r[j-i-1]
print(w)

G = nx.DiGraph(w)
p = nx.dijkstra_path(G, source=0, target=4, weight='weight')
print('最短路径是', np.array(p)+1)

d = nx.dijkstra_path_length(G, source=0, target=4, weight='weight')
print('最短距离是', d)

s = dict(zip(range(5), range(1,6)))
pos = nx.shell_layout(G) # 设置布局
G_w = nx.get_edge_attributes(G, 'weight')
nx.draw(G, pos, font_weight='bold', labels=s, node_color='r')
nx.draw_networkx_edge_labels(G, pos, edge_labels=G_w)
nx.draw_networkx_edges(G, pos, width=3)
plt.show()
0%