不平衡指派问题的主子阵算法

Principal Submatrix Algorithm for the Unbalanced Assignment Problem

针对人数和任务数不相等的不平衡指派问题,提出了求解该类指派问题的主子阵算法.给出从低阶主子阵向高阶主子阵寻找主子阵行最小元的变换定理,并举例分析其具体的演算过程.该算法的特点是将求解变换限定在指派矩阵的主子阵上,即不需要考虑指派矩阵整体,只需要在指派矩阵局部进行运算,并从指派矩阵的1阶主子阵的行最小元出发,逐步有规律地找到各阶主子阵的行最小元,最终求得指派问题的最优解.

A principal submatrix algorithm for solving unbalanced assignment problems with unequal numbers of people and tasks was proposed.The transformation theorem for finding the row minimum element of the principal submatrix from a low order principal submatrix to a high order principal submatrix is given,and the specific calculation process is given with an example.The characteristic of this algorithm is that the transformation is limited to the principal submatrix of the assignment matrix,which does not need to consider the entire assignment matrix.This algorithm only needs to perform operations locally on the assignment matrix.Starting from the row minimum elements of the first order principal submatrix of the assignment matrix,it systematically finds the row minimum elements of each order principal submatrix step by step,and finally obtains the optimal solution of the assignment problem.