A Principal Submatrix Algorithm for the Unbalanced Assignment Problem
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.
unbalanced assignment problemoptimal solutionprincipal submatrixrow minimum element
NETL
NSTL
万方数据
维普
