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:

13867293837165285
768078792311989645
391850613178578918
82637710416554853
609492447421151447
417027859165625458
22479225541523777
185354774214451687
893758906240977032

Subtract row minima

We subtract the row minimum from each row:

8816788786660230(-5)
65696768120878534(-11)
2103243136039710(-18)
7859736012514449(-4)
468078306071033(-14)
14430586438352731(-27)
1540851847816070(-7)
439406328031273(-14)
575265830865380(-32)

Subtract column minima

We subtract the column minimum from each column:

4816782786659230
61696762120868534
1703237136038710
7459730012504449
428078246070033
10430526438342731
1140851247815070
039405728030273
535265230864380
(-4)(-6)(-1)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

4816782786659230
61696762120868534  x
1703237136038710  x
7459730012504449  x
428078246070033  x
10430526438342731  x
1140851247815070  x
039405728030273  x
535265230864380
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:

0776378746255190
61696762120868538
1703237136038714
7459730012504453
428078246070037
10430526438342735
1140851247815074
039405728030277
491224826460340

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

0776378746255190
61696762120868538
1703237136038714  x
7459730012504453  x
428078246070037  x
10430526438342735  x
1140851247815074  x
039405728030277
491224826460340
xxx

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:

0766277736254180
61686661110858438
1803237136138715
7559730013504454
438078246080038
11430526439342736
1240851247915075
038395627029177
490214725459330

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

0766277736254180
61686661110858438
1803237136138715
7559730013504454  x
438078246080038  x
11430526439342736  x
1240851247915075  x
038395627029177
490214725459330
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:

0766176726253170
61686560100848338
1803136126137705
7660730014504455
448178246090039
12440526440342737
13418512471015076
038385526028077
490204624458320

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

0766176726253170
61686560100848338
1803136126137705
7660730014504455  x
448178246090039  x
12440526440342737  x
13418512471015076
038385526028077
490204624458320
xxxxx

Create additional zeros

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

0765166626243170
6168555000748338
180212626127705
8670730024505465
54917824601901049
22540526450343747
134175237105076
038284516018077
490103614448320

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

0765166626243170  x
6168555000748338  x
180212626127705  x
8670730024505465  x
54917824601901049  x
22540526450343747  x
134175237105076  x
038284516018077  x
490103614448320  x

The optimal assignment

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

0765166626243170
6168555000748338
180212626127705
8670730024505465
54917824601901049
22540526450343747
134175237105076
038284516018077
490103614448320

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

13867293837165285
768078792311989645
391850613178578918
82637710416554853
609492447421151447
417027859165625458
22479225541523777
185354774214451687
893758906240977032

The optimal value equals 159.