“人少任务多”型指派问题的一种新算法

对于“人少任务多”型指派问题的解法,人们已经提出了很多解法,如“加边补零”法[1],“加边补最小值”法[2],只是前面提到的这些方法总体思路都是将其转化为标准指派问题来求解;对此,提出了一种不同于传统解法的差额法,方法不必一开始就去用新的矩阵去代替原系数矩阵,而是可直接在原系数矩阵上进行求解;方法简洁,直观,而且优于传统算法.

A New Algorithm for Assignment Problems with "Tasks More Than the Number of Persons"

With regard to the solution to the assignment problems with ＂tasks more than the number of persons＂, there are many solving methods such as＂adding rows with zeros＂, adding rows with minimum value , the whole idea of all these methods mentioned above is to solve the problems by transforming them into standard assignment problems, therefore, this paper proposes a difference method different from traditional solving methods, this method, which is simple, visual and better than traditional algorithms, does not need to use new matrix to replace original coefficient matrix at the beginning but directly solves the problems on the original coefficient matrix.