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

 12 42 51 68 64 6 63 2 26 6 65 29 19 20 9 27

Subtract row minima

We subtract the row minimum from each row:

 0 30 39 56 (-12) 62 4 61 0 (-2) 20 0 59 23 (-6) 10 11 0 18 (-9)

Subtract column minima

Because each column contains a zero, subtracting column minima has no effect.

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

 0 30 39 56 x 62 4 61 0 x 20 0 59 23 x 10 11 0 18 x

The optimal assignment

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

 0 30 39 56 62 4 61 0 20 0 59 23 10 11 0 18

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

 12 42 51 68 64 6 63 2 26 6 65 29 19 20 9 27

The optimal value equals 29.