非方阵指派问题的求解  

The Solution for Assignment Problem of Nonsquare Matrix

作　　者：杨丽英[1,2] 韩建达[1] 聂义勇[1] 

机构地区：[1]中国科学院沈阳自动化研究所机器人学国家重点实验室,辽宁沈阳110016 [2]中国科学院研究生院,北京100049

出　　处：《信息与控制》2009年第6期641-645,652,共6页Information and Control

基　　金：国家863计划资助项目(2007AA041502)

摘　　要：本文将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.

关 键 词：极大极小指派问题 总体极小指派问题 混合整数线性规划 矩阵作业法 行优先选取算法 

分 类 号：TP24[自动化与计算机技术—检测技术与自动化装置]