Solving Assignment Problem for n persons and 2n jobs using the Method of main submatrix

摘要：

In this paper, the transformation φ keeping solution is given and the main submatrix method solving assignment problem for n persons to do 2n things are presented. For a given matrix an×2n=(Aij)n×2n,applying the transformation φ,φ(An×2n)=A(1)n×2n=(a(1)ij )n×2n,is gotten ,and (a(1)11,a(1)12) is a group of row-smallest elements in the main submatrix A(1)1×2 .In generally, supposing (at(k),j2t-1,,at(k)t,j2t)|1≤t≤k are k groups of independent row-smallest elements of A(k)n×2n which is the main submatrix of A(k)n×2n=(a(k)ij)n×2n,(1≤k<n),we have φ(A(k)n×2n))=A(k+1)n×2n=(a(k+1)ij)n×2n,and k+1 groups of independent row-smallest elements (a(k+1)t,j2t-1,a(k+1)t,j2t)|1≤t≤k+1can be found out in A(k+1)(k+1)×2(k+1) (1≤k<n)which is the main submatrix of A(k+1)n×2n·continuously ,A(n)n×2n=(a(n)ij)n×2n can be gotten and n groups of independent row-smallest elements (a(n)t,y2t-1,a(n)t,y2t)|1≤t≤k+1 can be found out in (A(k+1)(k+1)×2(k+1)(1≤k<n) which is the main submatrix of A(k+1)n×2n .continuously,A(n)n×2n=(a(n)ij)n×2n can be gotten and n groups of independent row-smallest elements a(n)t,y2t-1,a(n)t,y2t)|1≤t≤k+1 can be found in A(n)n×2n,and A(n)n×2n is equivalent to An×2n in solution.Lastly, an example solving with the method is given.

关键词： n persons do 2n things assignment problem the change theory keeping solution the main submatrix method

作者: Liangze Zhou

作者单位: System Engineering Institute Jingchu Technology University, Jingmen, Hubei,China

会议类型: 国际会议

会议名称: 2007 Conference on Systems Science, Management Science and System Dynamics(第二届系统科学、管理科学与系统动力学国际会议)

会议地点: 上海

会议语种:英文

页码: 3135-3140

在线出版日期: 2007-10-19（万方平台首次上网日期，不代表论文的发表时间）