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

 76 87 13 30 66 48 16 42 43 8 1 37 85 33 49 64

Subtract row minima

We subtract the row minimum from each row:

 63 74 0 17 (-13) 50 32 0 26 (-16) 42 7 0 36 (-1) 52 0 16 31 (-33)

Subtract column minima

We subtract the column minimum from each column:

 21 74 0 0 8 32 0 9 0 7 0 19 10 0 16 14 (-42) (-17)

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

 21 74 0 0 x 8 32 0 9 x 0 7 0 19 x 10 0 16 14 x

The optimal assignment

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

 21 74 0 0 8 32 0 9 0 7 0 19 10 0 16 14

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

 76 87 13 30 66 48 16 42 43 8 1 37 85 33 49 64

The optimal value equals 122.