用networkx解决图论问题(3)

在人员分派问题中,工作人员适合做的各项工作效益未必一致,需要制订一个分派方案,使公司总效益最大。解决这个问题可以用库恩-曼克莱斯(Kuhn-Munkres)算法。

例:假设要分配5个人做5项不同的工作,每个人做不同工作产生的效益由临接矩阵

$ W = (w_{ij})_{5\times5} = \begin{bmatrix} 3 & 5 & 5 & 4 & 1 \\ 2 & 2 & 0 & 2 & 2 \\ 2 & 4 & 4 & 1 & 0 \\ 0 & 2 & 2 & 1 & 0 \\ 1 & 2 & 1 & 3 & 3 \end{bmatrix} $

表示。试求使效益达到最大的分配方案。

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
# -*- coding: utf-8 -*-
import numpy as np
import networkx as nx
from networkx.algorithms.matching import max_weight_matching

a = np.array([[3,5,5,4,1],
[2,2,0,2,2],
[2,4,4,1,0],
[0,2,2,1,0],
[1,2,1,3,3]])
b = np.zeros((10,10))
b[0:5,5:] = a
G = nx.Graph(b)

s0 = max_weight_matching(G) # 返回值为(人员,工作)集合
s = [sorted(w) for w in s0]

L1 = [x[0] for x in s]
L1 = np.array(L1) + 1 # 人员编号
L2 = [x[1] for x in s]
L2 = np.array(L2) - 4 # 工作编号

c = a[L1 - 1, L2 - 1] # 提取对应的效益
d = c.sum() # 计算总的效益

print('工作分配对应关系为:\n人员编号:',L1)
print('工作编号:',L2)
print('总的效益为:',d)
0%