Atama problemi için yeni bir çözüm yaklaşımı

The purpose of this study is to present a new solution approach for the assignment problem. In assignment problem, there are (m) individuals are to be assigned to (m) jobs. If the individual (i) assigned to job (j), the cost incurred will be (cij), and accordingly the cost matrix is denoted by C. It is desired to find the minimal cost assignment or a one-to-one matching of individuals to jobs. There are many solution methods for this problem, but the simplicity and robutsness of the Hungarian method makes it the best known method among all others. The Hungarian method solves the problem by converting the cost matrix into a reduced matrix systematically at each iteration. A part of this process is finding fewest number of lines to cover all zero elements in the reduced matrix. When the size of the problem increases and reduced matrix contains many zeros, it is a tedious task to find minimum number of lines and the way of drawing them. The Hungarian method has an ambiguity at this point. A solution method is presented in this study to eliminate this ambiguity. A systematic and simple procedure is defined to find the fewest number of lines to cover all zero elements in the reduced matrix.