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

 97 85 18 24 85 71 17 24 24 8 50 30 11 84 8 34

Subtract row minima

We subtract the row minimum from each row:

 79 67 0 6 (-18) 68 54 0 7 (-17) 16 0 42 22 (-8) 3 76 0 26 (-8)

Subtract column minima

We subtract the column minimum from each column:

 76 67 0 0 65 54 0 1 13 0 42 16 0 76 0 20 (-3) (-6)

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

 76 67 0 0 x 65 54 0 1 x 13 0 42 16 x 0 76 0 20 x

The optimal assignment

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

 76 67 0 0 65 54 0 1 13 0 42 16 0 76 0 20

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

 97 85 18 24 85 71 17 24 24 8 50 30 11 84 8 34

The optimal value equals 60.