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:

388849493718328
7067484757965468
67717879069694
24269621737699
21968451797121
7054758861359556
602099744913023
441032629477186

Subtract row minima

We subtract the row minimum from each row:

300768685637520(-8)
2320101049721(-47)
61111818409088(-6)
15178712646700(-9)
1388037916313(-8)
351940532606021(-35)
531392037842316(-7)
37325558706479(-7)

Subtract column minima

We subtract the column minimum from each column:

170768676637520
102010149721
48111817509088
2178712556700
088037016313
221940531706021
401392028842316
24325557806479
(-13)(-9)

Cover all zeros with a minimum number of lines

There are 5 lines required to cover all zeros:

170768676637520  x
102010149721
48111817509088
2178712556700  x
088037016313  x
221940531706021
401392028842316
24325557806479
xx

Create additional zeros

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

170768776647520
91900049620
47010817408987
2178713556800
088038026313
211839531605920
391291027842215
23224557706378

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

170768776647520
91900049620  x
47010817408987
2178713556800  x
088038026313  x
211839531605920
391291027842215  x
23224557706378
xx

Create additional zeros

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

70667766646510
92900059620
3700716407977
2278713557800
0980380126313
11182943604910
392291027942215
13214456705368

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

70667766646510  x
92900059620  x
3700716407977  x
2278713557800  x
0980380126313  x
11182943604910
392291027942215  x
13214456705368
x

Create additional zeros

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

70667766666510
92900061620
3700716427977
2278713558000
0980380146313
916274140478
392291027962215
11012436505166

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

70667766666510
92900061620  x
3700716427977  x
2278713558000  x
0980380146313  x
916274140478
392291027962215  x
11012436505166
xx

Create additional zeros

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

3062736266616
93300065620
3740716467977
2318713558400
01020380186313
516233700434
3926910271002215
708396104762

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

3062736266616
93300065620
3740716467977
2318713558400  x
01020380186313  x
516233700434
3926910271002215
708396104762
xxxxx

Create additional zeros

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

0062736266583
63300065317
3440716467674
2349016588700
01053413216313
216233700401
3626910271001912
408396104459

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

0062736266583
63300065317
3440716467674
2349016588700  x
01053413216313
216233700401
3626910271001912
408396104459
xxxxxx

Create additional zeros

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

0062736266572
63300065216
3440716467573
3359117598800
01053413216212
216233700390
3626910271001811
408396104358

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

0062736266572  x
63300065216  x
3440716467573  x
3359117598800  x
01053413216212  x
216233700390  x
3626910271001811  x
408396104358  x

The optimal assignment

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

0062736266572
63300065216
3440716467573
3359117598800
01053413216212
216233700390
3626910271001811
408396104358

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

388849493718328
7067484757965468
67717879069694
24269621737699
21968451797121
7054758861359556
602099744913023
441032629477186

The optimal value equals 182.