Fill in the cost matrix of an assignment problem and click on 'Solve'. The optimal assignment will be determined and a step by step explanation of the hungarian algorithm will be given.
Fill in the cost matrix (random cost matrix):
This is the cost matrix.
| 93 | 21 | 47 | 82 |
| 50 | 43 | 57 | 38 |
| 30 | 26 | 1 | 64 |
| 2 | 75 | 28 | 79 |
For each row, the minimum element is subtracted from all elements in that row.
| 72 | 0 | 26 | 61 | (-21) |
| 12 | 5 | 19 | 0 | (-38) |
| 29 | 25 | 0 | 63 | (-1) |
| 0 | 73 | 26 | 77 | (-2) |
Because each column already contains a zero, subtracting the column minima has no effect.
A total of 4 lines are required to cover all zeros.
| 72 | 0 | 26 | 61 | x |
| 12 | 5 | 19 | 0 | x |
| 29 | 25 | 0 | 63 | x |
| 0 | 73 | 26 | 77 | x |
Because there are 4 lines required, an optimal assignment exists among the zeros.
| 72 | 0 | 26 | 61 |
| 12 | 5 | 19 | 0 |
| 29 | 25 | 0 | 63 |
| 0 | 73 | 26 | 77 |
This corresponds to the following optimal assignment in the original cost matrix.
| 93 | 21 | 47 | 82 |
| 50 | 43 | 57 | 38 |
| 30 | 26 | 1 | 64 |
| 2 | 75 | 28 | 79 |
The total minimum cost is 62.