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:

3	2	1
12	23	23
123	23	12

Subtract row minima

We subtract the row minimum from each row:

2	1	0	(-1)
0	11	11	(-12)
111	11	0	(-12)

Subtract column minima

We subtract the column minimum from each column:

2	0	0
0	10	11
111	10	0
	(-1)

Cover all zeros with a minimum number of lines

There are 3 lines required to cover all zeros:

2	0	0	x
0	10	11	x
111	10	0	x

The optimal assignment

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

2	0	0
0	10	11
111	10	0

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

3	2	1
12	23	23
123	23	12

The optimal value equals 26.