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

 45 38 98 97 26 32 99 22 79 88 53 41 81 93 82 42 81 79 56 40 45 38 38 28 35

Subtract row minima

We subtract the row minimum from each row:

 19 12 72 71 0 (-26) 10 77 0 57 66 (-22) 12 0 40 52 41 (-41) 2 41 39 16 0 (-40) 17 10 10 0 7 (-28)

Subtract column minima

We subtract the column minimum from each column:

 17 12 72 71 0 8 77 0 57 66 10 0 40 52 41 0 41 39 16 0 15 10 10 0 7 (-2)

Cover all zeros with a minimum number of lines

There are 5 lines required to cover all zeros:

 17 12 72 71 0 x 8 77 0 57 66 x 10 0 40 52 41 x 0 41 39 16 0 x 15 10 10 0 7 x

The optimal assignment

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

 17 12 72 71 0 8 77 0 57 66 10 0 40 52 41 0 41 39 16 0 15 10 10 0 7

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

 45 38 98 97 26 32 99 22 79 88 53 41 81 93 82 42 81 79 56 40 45 38 38 28 35

The optimal value equals 159.