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

 94 25 2 34 55 10 37 6 12 4 5 52 73 16 16 43

Subtract row minima

We subtract the row minimum from each row:

 92 23 0 32 (-2) 49 4 31 0 (-6) 8 0 1 48 (-4) 57 0 0 27 (-16)

Subtract column minima

We subtract the column minimum from each column:

 84 23 0 32 41 4 31 0 0 0 1 48 49 0 0 27 (-8)

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

 84 23 0 32 x 41 4 31 0 x 0 0 1 48 x 49 0 0 27 x

The optimal assignment

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

 84 23 0 32 41 4 31 0 0 0 1 48 49 0 0 27

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

 94 25 2 34 55 10 37 6 12 4 5 52 73 16 16 43

The optimal value equals 36.