非方阵指派问题的求解

The Solution for Assignment Problem of Nonsquare Matrix

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

     

    Abstract: 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 O(mn2).The efficiency of selection algorithm of precedence rows is usually comparable to that of operations on matrix in one covering circle.

     

/

返回文章
返回