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

 22 85 99 63 96 61 65 98 15 15 15 92 91 60 16 91

Subtract row minima

We subtract the row minimum from each row:

 0 63 77 41 (-22) 35 0 4 37 (-61) 0 0 0 77 (-15) 75 44 0 75 (-16)

Subtract column minima

We subtract the column minimum from each column:

 0 63 77 4 35 0 4 0 0 0 0 40 75 44 0 38 (-37)

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

 0 63 77 4 x 35 0 4 0 x 0 0 0 40 x 75 44 0 38 x

The optimal assignment

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

 0 63 77 4 35 0 4 0 0 0 0 40 75 44 0 38

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

 22 85 99 63 96 61 65 98 15 15 15 92 91 60 16 91

The optimal value equals 151.