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

 82 71 93 31 55 92 72 17 31 29 99 76 5 82 61 81

Subtract row minima

We subtract the row minimum from each row:

 51 40 62 0 (-31) 38 75 55 0 (-17) 2 0 70 47 (-29) 0 77 56 76 (-5)

Subtract column minima

We subtract the column minimum from each column:

 51 40 7 0 38 75 0 0 2 0 15 47 0 77 1 76 (-55)

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

 51 40 7 0 x 38 75 0 0 x 2 0 15 47 x 0 77 1 76 x

The optimal assignment

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

 51 40 7 0 38 75 0 0 2 0 15 47 0 77 1 76

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

 82 71 93 31 55 92 72 17 31 29 99 76 5 82 61 81

The optimal value equals 137.