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

Size: 3x3 4x4 5x5 6x6 7x7 8x8 9x9 10x10

Don't show the steps of the Hungarian algorithm
Maximize the total cost

This is the original cost matrix:

7683745654
7776356987
7715999119
6217394327
7227618277

Subtract row minima

We subtract the row minimum from each row:

22292020(-54)
424103452(-35)
62084764(-15)
450222610(-17)
450345550(-27)

Subtract column minima

We subtract the column minimum from each column:

0292000
204103252
40084744
230222410
230345350
(-22)(-2)

Cover all zeros with a minimum number of lines

There are 3 lines required to cover all zeros:

0292000  x
204103252  x
40084744
230222410
230345350
x

Create additional zeros

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

0332000
204503252
36080700
19018206
190304946

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

0332000  x
204503252  x
36080700  x
19018206
190304946
x

Create additional zeros

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

0392000
205103252
36680700
13012140
130244340

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

0392000  x
205103252  x
36680700
13012140
130244340
xx

Create additional zeros

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

05120012
206303264
24668580
10020
10123140

Cover all zeros with a minimum number of lines

There are 4 lines required to cover all zeros:

05120012  x
206303264
24668580
10020
10123140
xxx

Create additional zeros

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

05221013
196303164
23668570
00010
00123040

Cover all zeros with a minimum number of lines

There are 5 lines required to cover all zeros:

05221013  x
196303164  x
23668570  x
00010  x
00123040  x

The optimal assignment

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

05221013
196303164
23668570
00010
00123040

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

7683745654
7776356987
7715999119
6217394327
7227618277

The optimal value equals 199.