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:

82964927278295152
71694446281737261
44388872148377229
318974958943975470
799432672263642
637825941290887727
444960193089877355
229695429930183516
95238431317838434

Subtract row minima

We subtract the row minimum from each row:

80944725258093130(-2)
0987375574666554(-7)
3630806460296421(-8)
05843645812662339(-31)
733372011657036(-6)
51661382078766515(-12)
25304101170685436(-19)
680792683142190(-16)
92208101014808131(-3)

Subtract column minima

We subtract the column minimum from each column:

80913425258091130
0674375574646554
3627676460276421
05530645812642339
730242011655036
5163082078746515
25272801170665436
677662683140190
92176801014788131
(-3)(-13)(-2)

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

80913425258091130  x
0674375574646554
3627676460276421  x
05530645812642339
730242011655036  x
5163082078746515  x
25272801170665436
677662683140190  x
92176801014788131
xx

Create additional zeros

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

86913431258091130
0068374968585948
4227677060276421
0492464526581733
790242611655036
5763088078746515
2521220564604830
1277663283140190
921162048727525

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

86913431258091130  x
0068374968585948  x
4227677060276421  x
0492464526581733  x
790242611655036  x
5763088078746515  x
2521220564604830
1277663283140190  x
921162048727525
x

Create additional zeros

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

86913435258091130
0068414968585948
4227677460276421
0492468526581733
790243011655036
5763092078746515
2117180160564426
1277663683140190
88758004687121

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

86913435258091130  x
0068414968585948  x
4227677460276421  x
0492468526581733  x
790243011655036  x
5763092078746515  x
2117180160564426  x
1277663683140190  x
88758004687121  x

The optimal assignment

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

86913435258091130
0068414968585948
4227677460276421
0492468526581733
790243011655036
5763092078746515
2117180160564426
1277663683140190
88758004687121

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

82964927278295152
71694446281737261
44388872148377229
318974958943975470
799432672263642
637825941290887727
444960193089877355
229695429930183516
95238431317838434

The optimal value equals 138.