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:

3939325063896962
8231248889183258
443652961305793
364586153201029
7694947352158614
1564928833825080
39327321363243
173236045804388

Subtract row minima

We subtract the row minimum from each row:

7701831573730(-32)
64136707101440(-18)
410622658275490(-3)
06155585017726(-3)
62808059381720(-14)
049777318673565(-15)
37307101143041(-2)
142905742774085(-3)

Subtract column minima

We subtract the column minimum from each column:

7701820573030
6413670600740
410622647274790
06155583917026
62808059271650
04977737672865
3730710042341
142905731773385
(-11)(-7)

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

7701820573030
6413670600740  x
410622647274790  x
06155583917026  x
62808059271650  x
04977737672865  x
3730710042341  x
142905731773385
x

Create additional zeros

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

0001113502323
64131370600740
410692647274790
06162583917026
62808759271650
04984737672865
3730780042341
72205024702678

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

0001113502323
64131370600740  x
410692647274790
06162583917026  x
62808759271650  x
04984737672865
3730780042341  x
72205024702678
xxx

Create additional zeros

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

00046431616
71202070600740
410691940204083
76869583917026
69879459271650
04984660602158
4437850042341
72204317631971

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

00046431616  x
71202070600740  x
410691940204083  x
76869583917026  x
69879459271650  x
04984660602158  x
4437850042341  x
72204317631971  x

The optimal assignment

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

00046431616
71202070600740
410691940204083
76869583917026
69879459271650
04984660602158
4437850042341
72204317631971

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

3939325063896962
8231248889183258
443652961305793
364586153201029
7694947352158614
1564928833825080
39327321363243
173236045804388

The optimal value equals 122.