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

 23 80 7 56 52 26 12 93 13 93 20 74 86 95 40 72

Subtract row minima

We subtract the row minimum from each row:

 16 73 0 49 (-7) 40 14 0 81 (-12) 0 80 7 61 (-13) 46 55 0 32 (-40)

Subtract column minima

We subtract the column minimum from each column:

 16 59 0 17 40 0 0 49 0 66 7 29 46 41 0 0 (-14) (-32)

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

 16 59 0 17 x 40 0 0 49 x 0 66 7 29 x 46 41 0 0 x

The optimal assignment

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

 16 59 0 17 40 0 0 49 0 66 7 29 46 41 0 0

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

 23 80 7 56 52 26 12 93 13 93 20 74 86 95 40 72

The optimal value equals 118.