一、分配问题应用案例：
1、男女相亲场景，10男10女为例，可让每人对每个异性进行意向度排序，若是男性优先则可以用男性意向度评分矩阵，女性优先同理，或者使用男女意向评分平均值作为意向度居正，然后用匈牙利算法求最大值，即可获得综合意向度得分最高的分配方法
2、电销和催收用户分配场景，不同电销人员对不同类型的客户效果可能催在差异，例如广东人对年长些的广东人电话营销或者催收时可能效果就更好，甜美女性电销人员对某部分男性营销效果更好，则可以根据用户属性和坐席人员属性测算成功概率，通过成功概率矩阵获得成功期望最高的分配方法
3、多标签多分类场景，匈牙利算法可用于多标签多分类场景的评估，例如可用sigmoid函数替代softmax函数，用多个二分类模型获得预测数据对应各标签的预测概率，选定阈值后，获得测试集总体准确率最高的多标签多分类模型
二、算法原理与实现
二、对于非标准指派问题上，可转化为标准指派问题，具体有以下几种情况
1、默认算法求最小值，将效益举证乘以-1即可求得最大值
2、人多事少，可添加虚拟“事”，所有人在该事情上的系数为0
3、人少事多，可添加虚拟“人”，所有人在各事情上的系数为0
4、某人要多件事，复制该人，该人对所有事情的效益值复制
5、某人不想做某事，将效益值设为最大值或者最小值
三、python案例
1、使用scipy，求得效益总体最大得分配方法
from random import sample from scipy.optimize import linear_sum_assignment import numpy as np #生成一个10*10的矩阵，每行由不重复的0-9数字组成 matrix = np.zeros((10, 10), dtype=int) for i in range(10): row = sample(range(10), 10) matrix[i] = row #获得每行分配的结果,其中row_ind为顺序 row_ind, col_ind = linear_sum_assignment(-1*matrix) print (col_ind) result = np.zeros(matrix.shape) result[row_ind, col_ind] = 1 print(result) res=result*matrix print(res.sum()) #输出 [4 8 5 0 6 3 9 1 7 2] [[0. 0. 0. 0. 1. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 1. 0.] [0. 0. 0. 0. 0. 1. 0. 0. 0. 0.] [1. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 1. 0. 0. 0.] [0. 0. 0. 1. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 1.] [0. 1. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 1. 0. 0.] [0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]] 81.0
2、使用munkres
import munkres # Use Munkres to compute the indices of the minimum cost pairings m = munkres.Munkres() indexes = m.compute(-1*matrix) print(indexes) # Parse the results result = np.zeros(matrix.shape) for row, col in indexes: result[row, col] = 1 print (result) res=result*matrix res.sum() #输出 [(0, 4), (1, 8), (2, 5), (3, 0), (4, 6), (5, 3), (6, 9), (7, 1), (8, 7), (9, 2)] [[0. 0. 0. 0. 1. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 1. 0.] [0. 0. 0. 0. 0. 1. 0. 0. 0. 0.] [1. 0. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 1. 0. 0. 0.] [0. 0. 0. 1. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 0. 0. 1.] [0. 1. 0. 0. 0. 0. 0. 0. 0. 0.] [0. 0. 0. 0. 0. 0. 0. 1. 0. 0.] [0. 0. 1. 0. 0. 0. 0. 0. 0. 0.]] 81.0