Assignment Problem (AP)

Assignment Problem can be stated in the form of n x n matrix Cij of real numbers as given in the following table.

                        Jobs
                      1       2        3               ..............n
Person   1 [    c11   c12    c13..........................c1n
              2        c21   c22    c23..........................c2n
               .
               .

               .
              n        cn1     cn2   cn3............................cnn]

Mathematical Formulation :

An Assignment problem can be stated as

Hungarian Method:
These are the steps to be followed in Hungarian Method for Optimal Job Assignment and for cost assignmnet.
STEP I: Check whether the given matrix is a square matrix.If its so then its balanced.If not balanced add "0" in either the row/column based on the matrix.
STEP II: Process row wise entries.Find out the smallest value and subtract the entire row value.
STEP III:Process  column wise entries.Find out the smallest value and subtract the entire column value.
STEP IV:Draw horizontal/vertical lines in such a way that they cover all the zeros ie., it should be crossed in minimum number of straight lines.
STEP V:Check whether Number of Straight lines(N) = Order of Matrix(n).
If N=n then we get the optimal solution.
If N<n then again find out the smallest value from the above matrix and subtract with the other values in the matrix.Leave the rows and columns that are being striked out.In the intersection point add the smallest value.
STEP VI:Finally assign the jobs to the correct person by assigning "0".Find the minimum cost.