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:

73609490884650
44331936216379
1930783668659
22439355859692
88157782298479
62991122867321
13175736444351

Subtract row minima

We subtract the row minimum from each row:

271448444204(-46)
251401724460(-19)
1627750638356(-3)
0217133637470(-22)
7306267146964(-15)
5188011756210(-11)
044423313038(-13)

Subtract column minima

We subtract the column minimum from each column:

271448444000
251401704456
1627750618352
0217133617466
7306267126960
518801173626
044423293034
(-2)(-4)

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

271448444000  x
251401704456  x
1627750618352  x
0217133617466
7306267126960  x
518801173626  x
044423293034
x

Create additional zeros

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

311448444000
291401704456
2027750618352
0176729577062
7706267126960
558801173626
004019252630

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

311448444000  x
291401704456  x
2027750618352  x
0176729577062
7706267126960
558801173626  x
004019252630
xx

Create additional zeros

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

432648444000
412601704456
3239750618352
0175517455850
770505505748
6710001173626
00287131418

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

432648444000  x
412601704456
3239750618352  x
0175517455850
770505505748
6710001173626
00287131418
xxxx

Create additional zeros

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

493254444600
412601103850
3845810678352
0175511455244
770504905142
671000573560
0028113812

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

493254444600  x
412601103850  x
3845810678352  x
0175511455244  x
770504905142  x
671000573560  x
0028113812  x

The optimal assignment

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

493254444600
412601103850
3845810678352
0175511455244
770504905142
671000573560
0028113812

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

73609490884650
44331936216379
1930783668659
22439355859692
88157782298479
62991122867321
13175736444351

The optimal value equals 157.