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

 77 86 26 97 27 92 66 62 30 31 94 11 17 34 30 31

Subtract row minima

We subtract the row minimum from each row:

 51 60 0 71 (-26) 0 65 39 35 (-27) 19 20 83 0 (-11) 0 17 13 14 (-17)

Subtract column minima

We subtract the column minimum from each column:

 51 43 0 71 0 48 39 35 19 3 83 0 0 0 13 14 (-17)

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

 51 43 0 71 x 0 48 39 35 x 19 3 83 0 x 0 0 13 14 x

The optimal assignment

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

 51 43 0 71 0 48 39 35 19 3 83 0 0 0 13 14

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

 77 86 26 97 27 92 66 62 30 31 94 11 17 34 30 31

The optimal value equals 98.