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:

96510419819273397
309457499056559319
44386161626308781
29464874547379135
939113733888178652
37475674672357493
652340819528138899
638183323795085
931349196882770

Subtract row minima

We subtract the row minimum from each row:

0561328910182488(-9)
11753830713736740(-19)
03982121222268377(-4)
22394167470308428(-7)
8078060257547339(-13)
32420624167306988(-5)
52102768821507586(-13)
607850293464782(-3)
920338186781669(-1)

Subtract column minima

We subtract the column minimum from each column:

0561327710181888
11753830593736680
0398212022267777
22394167350307828
8078060137546739
32420622967306388
52102768701506986
607850173464182
92033866781069
(-12)(-6)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

0561327710181888  x
11753830593736680  x
0398212022267777  x
22394167350307828  x
8078060137546739
32420622967306388
52102768701506986  x
607850173464182  x
92033866781069  x
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:

0565327710181888
11754230593736680
0398612022267777
22394567350307828
767405697106335
28380582563265984
52103168701506986
607890173464182
92037866781069

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

0565327710181888  x
11754230593736680  x
0398612022267777  x
22394567350307828  x
767405697106335
28380582563265984
52103168701506986
607890173464182  x
92037866781069  x
xx

Create additional zeros

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

05614327710271888
11755130593745680
0399512022357777
22395467350397828
676504706205426
19290491654265075
431315961606077
60781801734154182
92046866790069

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

05614327710271888
11755130593745680  x
0399512022357777
22395467350397828  x
676504706205426
19290491654265075
431315961606077
60781801734154182  x
92046866790069  x
xxxx

Create additional zeros

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

0551431779271787
12755230603746680
0389511021357676
23395567360407828
676404606105325
19280481653264974
430315861505976
61781901834164182
93047876791069

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

0551431779271787  x
12755230603746680  x
0389511021357676  x
23395567360407828  x
676404606105325  x
19280481653264974  x
430315861505976  x
61781901834164182  x
93047876791069  x

The optimal assignment

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

0551431779271787
12755230603746680
0389511021357676
23395567360407828
676404606105325
19280481653264974
430315861505976
61781901834164182
93047876791069

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

96510419819273397
309457499056559319
44386161626308781
29464874547379135
939113733888178652
37475674672357493
652340819528138899
638183323795085
931349196882770

The optimal value equals 106.