非方阵指派问题的求解

The Solution for Assignment Problem of Nonsquare Matrix

本文将2类方阵指派问题——极大极小和总体极小指派问题——的矩阵作业解法推广到非方阵情形,即求解任务与人员数目不等的指派问题,且维持矩阵作业法的效率.假定m>n,则按本文行优先选取算法求解m×n非方阵指派问题的最大逻辑运算量为O(mn2),其效率通常与执行一轮覆盖的矩阵作业法相当.

The operations on matrix for both minimax and global-minimum assignment problems of square matrix are applied to those of nonsquare matrix, namely, in the same efficiency with the operations on matrix, both the minimax and global-minimum assignment problems where number of people is unequal to number of tasks are solved. Supposed m 〉 n, the quantity of logical operations to solve the assignment problem of m × n nonsquare matrix with the selection algorithm of precedence rows in this paper is not bigger than 0（mn^2）. The efficiency of selection algorithm of precedence rows is usually comparable to that of operations on matrix in one covering circle.