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

 72 88 3 34 48 59 69 11 68 87 52 9 82 8 7 31

Subtract row minima

We subtract the row minimum from each row:

 69 85 0 31 (-3) 37 48 58 0 (-11) 59 78 43 0 (-9) 75 1 0 24 (-7)

Subtract column minima

We subtract the column minimum from each column:

 32 84 0 31 0 47 58 0 22 77 43 0 38 0 0 24 (-37) (-1)

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

 32 84 0 31 x 0 47 58 0 x 22 77 43 0 x 38 0 0 24 x

The optimal assignment

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

 32 84 0 31 0 47 58 0 22 77 43 0 38 0 0 24

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

 72 88 3 34 48 59 69 11 68 87 52 9 82 8 7 31

The optimal value equals 68.