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:

48	18	6	0
128	48	16	80
192	72	24	120
144	54	18	90

Negate all values

Because the objective is to maximize the total cost we negate all elements:

-48	-18	-6	0
-128	-48	-16	-80
-192	-72	-24	-120
-144	-54	-18	-90

Make the matrix nonnegative

The cost matrix contains negative elements, we add 192 to each entry to make the cost matrix nonnegative:

144	174	186	192
64	144	176	112
0	120	168	72
48	138	174	102

Subtract row minima

We subtract the row minimum from each row:

30	42	48	(-144)
80	112	48	(-64)
120	168	72
90	126	54	(-48)

Subtract column minima

We subtract the column minimum from each column:

0	0	0	0
0	50	70	0
0	90	126	24
0	60	84	6
	(-30)	(-42)	(-48)

Cover all zeros with a minimum number of lines

There are 3 lines required to cover all zeros:

0	0	0	0	x
0	50	70	0	x
0	90	126	24
0	60	84	6
x

Create additional zeros

The number of lines is smaller than 4. The smallest uncovered number is 6. We subtract this number from all uncovered elements and add it to all elements that are covered twice:

6	0	0	0
6	50	70	0
0	84	120	18
0	54	78	0

Cover all zeros with a minimum number of lines

There are 3 lines required to cover all zeros:

6	0	0	0	x
6	50	70	0
0	84	120	18
0	54	78	0
x			x

Create additional zeros

The number of lines is smaller than 4. The smallest uncovered number is 50. We subtract this number from all uncovered elements and add it to all elements that are covered twice:

56	0	0	50
6	0	20	0
0	34	70	18
0	4	28	0

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

56	0	0	50	x
6	0	20	0	x
0	34	70	18	x
0	4	28	0	x

The optimal assignment

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

56	0	0	50
6	0	20	0
0	34	70	18
0	4	28	0

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

48	18	6	0
128	48	16	80
192	72	24	120
144	54	18	90

The optimal value equals 336.