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

 47 42 60 26 50 78 63 17 71 50 15 84 37 47 59 31

Subtract row minima

We subtract the row minimum from each row:

 21 16 34 0 (-26) 33 61 46 0 (-17) 56 35 0 69 (-15) 6 16 28 0 (-31)

Subtract column minima

We subtract the column minimum from each column:

 15 0 34 0 27 45 46 0 50 19 0 69 0 0 28 0 (-6) (-16)

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

 15 0 34 0 x 27 45 46 0 x 50 19 0 69 x 0 0 28 0 x

The optimal assignment

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

 15 0 34 0 27 45 46 0 50 19 0 69 0 0 28 0

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

 47 42 60 26 50 78 63 17 71 50 15 84 37 47 59 31

The optimal value equals 111.