Hungarian Method for Assignment Problem
Input : A Cost Table.
Output : An equivalent cost table has all the zero elements required for a complete set of assignments which
constitute an optimal solution.
Strategy : To concert the cost table into equivalent cost tables until we get an optimal solution.
Algorithm :
Step - 1 : Subtract the minimum element in each row from every entry in that row of a cost table.
Step - 2 : Subtract the minimum element in each column from every entry in that column of the resulting
equivalent cost table. This step results in at least one zero in every row and column. If there is
a complete set of assignments with zero elements is possible than the resultant equivalent cost
table is the optimal solution otherwise go to next step.
Step - 3 : Draw a set of minimum number of lines through some of the rows and columns in such a way as
to cover all the zeros. Subtract the minimum element from every element without a line through
them and then add that minimum element that lies at the intersection of two lines. Now if there is
a complete set of assignments with zero elements is possible than the resultant equivalent cost
table is the optimal solution otherwise repeat this step( step 3).
The total cost of the optimal solution is the sum of amounts that have been subtracted from each
row of the cost matrix.