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

 99 91 58 21 67 24 15 67 51 90 2 41 35 74 93 76

Subtract row minima

We subtract the row minimum from each row:

 78 70 37 0 (-21) 52 9 0 52 (-15) 49 88 0 39 (-2) 0 39 58 41 (-35)

Subtract column minima

We subtract the column minimum from each column:

 78 61 37 0 52 0 0 52 49 79 0 39 0 30 58 41 (-9)

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

 78 61 37 0 x 52 0 0 52 x 49 79 0 39 x 0 30 58 41 x

The optimal assignment

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

 78 61 37 0 52 0 0 52 49 79 0 39 0 30 58 41

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

 99 91 58 21 67 24 15 67 51 90 2 41 35 74 93 76

The optimal value equals 82.