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:

9250161539567354
2973084771781388
59475835584912238
454777993117141793
38866553696485466
882639808112415394
25442317171134412
64788936475583339
7795346585347643

Subtract row minima

We subtract the row minimum from each row:

7048141337547152(-2)
2202377701074311(-7)
55435431540871834(-4)
313363851730379(-14)
08563523393455163(-3)
76142768690294182(-12)
214019131373008(-4)
04182875869522733(-6)
1734740524741037(-6)

Subtract column minima

We subtract the column minimum from each column:

70291037547151
220464571074310
55433518410871833
31334472430378
08544392093455162
7614855560294181
214000073007
04163744569522732
1732827394741036
(-19)(-13)(-13)(-1)

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

70291037547151  x
220464571074310  x
55433518410871833
31334472430378  x
08544392093455162
7614855560294181
214000073007  x
04163744569522732
1732827394741036  x
xx

Create additional zeros

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

150291045547151
300464571874310
55352710330791025
393344724110378
07736311293374354
766047480213373
2940000153007
03355663769441924
9732827395541036

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

150291045547151  x
300464571874310  x
55352710330791025  x
393344724110378  x
07736311293374354
766047480213373  x
2940000153007  x
03355663769441924
9732827395541036  x
x

Create additional zeros

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

270291045547151
420464571874310
67352710330791025
513344724110378
0652419081253142
886047480213373
4140000153007
0214354255732712
21732827395541036

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

270291045547151  x
420464571874310  x
67352710330791025  x
513344724110378  x
0652419081253142  x
886047480213373  x
4140000153007  x
0214354255732712  x
21732827395541036  x

The optimal assignment

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

270291045547151
420464571874310
67352710330791025
513344724110378
0652419081253142
886047480213373
4140000153007
0214354255732712
21732827395541036

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

9250161539567354
2973084771781388
59475835584912238
454777993117141793
38866553696485466
882639808112415394
25442317171134412
64788936475583339
7795346585347643

The optimal value equals 132.