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:

8802216458122649360
7883614291556609945
25823936571523349039
92925588717826485
9092406338675249763
77347734512860295425
1772645651195764178
6997132411588689282
161788766342158859
61755231154193186

Subtract row minima

We subtract the row minimum from each row:

072148377314568552(-8)
7277553685490549339(-6)
106724214208197524(-15)
88521544677422081(-4)
8385335631604542056(-7)
529529263354290(-25)
1166585045135103572(-6)
61895163507808474(-8)
121384725901718455(-4)
5514917548132520(-6)

Subtract column minima

We subtract the column minimum from each column:

07190347314568552
7276502882490549339
106619133908197524
88416461677422081
8384284828604542056
528471233354290
1165534242135103572
6188080507808474
121279645601718455
550449248132520
(-1)(-5)(-8)(-3)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

07190347314568552  x
7276502882490549339  x
106619133908197524
88416461677422081
8384284828604542056
528471233354290  x
1165534242135103572  x
6188080507808474  x
121279645601718455
550449248132520  x
xx

Create additional zeros

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

07190347414568652
7276502882500549439
96518123807187523
87315450677321080
8283274727604441055
528471234354300
1165534242145103672
6188080517808574
111178635501608454
550449249132530

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

07190347414568652  x
7276502882500549439  x
96518123807187523
87315450677321080  x
8283274727604441055  x
528471234354300  x
1165534242145103672
6188080517808574  x
111178635501608454
550449249132530  x
xx

Create additional zeros

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

07190348114638652
7276502882570619439
2581153100186816
87315450747328080
8283274727674448055
52847123113511300
458463535144402965
6188080587878574
447156480907747
550449256133230

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

07190348114638652  x
7276502882570619439
2581153100186816
87315450747328080  x
8283274727674448055  x
52847123113511300  x
458463535144402965
6188080587878574  x
447156480907747
550449256133230  x
xxx

Create additional zeros

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

07190348316658652
7074482680570619237
056932900186614
87315450767530080
8283274727694650055
52847123133713300
256443333144402763
6188080608098574
226954460907545
550449258153430

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

07190348316658652  x
7074482680570619237  x
056932900186614  x
87315450767530080  x
8283274727694650055  x
52847123133713300  x
256443333144402763  x
6188080608098574  x
226954460907545  x
550449258153430  x

The optimal assignment

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

07190348316658652
7074482680570619237
056932900186614
87315450767530080
8283274727694650055
52847123133713300
256443333144402763
6188080608098574
226954460907545
550449258153430

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

8802216458122649360
7883614291556609945
25823936571523349039
92925588717826485
9092406338675249763
77347734512860295425
1772645651195764178
6997132411588689282
161788766342158859
61755231154193186

The optimal value equals 117.