# Solve an assignment problem online

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):

Don't show the steps of the Hungarian algorithm
Maximize the total cost

This is the original cost matrix:

 43 12 62 31 9 87 68 3 91 82 67 92 17 46 80 9

Subtract row minima

We subtract the row minimum from each row:

 31 0 50 19 (-12) 6 84 65 0 (-3) 24 15 0 25 (-67) 8 37 71 0 (-9)

Subtract column minima

We subtract the column minimum from each column:

 25 0 50 19 0 84 65 0 18 15 0 25 2 37 71 0 (-6)

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

 25 0 50 19 x 0 84 65 0 x 18 15 0 25 x 2 37 71 0 x

The optimal assignment

Because there are 4 lines required, the zeros cover an optimal assignment:

 25 0 50 19 0 84 65 0 18 15 0 25 2 37 71 0

This corresponds to the following optimal assignment in the original cost matrix:

 43 12 62 31 9 87 68 3 91 82 67 92 17 46 80 9

The optimal value equals 97.