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:

59583588402778418484
97493414996442305241
28312275115192512
6483132276691129028
7745137443373568783
1327909046369738939
1136733636685539363
1117808759594988514
50651017477188911832
3866714059236461371

Subtract row minima

We subtract the row minimum from each row:

323186113051145757(-27)
8335200855028163827(-14)
2611025394990490(-2)
6281110256489108826(-2)
7442107140070538480(-3)
418818137278829840(-9)
833703333655236330(-3)
3972067878690776(-8)
40550737617881822(-10)
3563683756206158068(-3)

Subtract column minima

We subtract the column minimum from each column:

29308611002345757
80342008250063827
2301025092180490
598011022646108826
7141107137042438480
117818134276019840
532703330652426330
0872064875880776
37540734615071822
3262683753203348068
(-3)(-1)(-3)(-28)(-10)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

29308611002345757
80342008250063827  x
2301025092180490  x
598011022646108826  x
7141107137042438480
117818134276019840
532703330652426330
0872064875880776  x
37540734615071822  x
3262683753203348068  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:

2829760902235657
80342008251063828
23010250102180491
598011022656108827
704097036041428380
016808033275918830
431693229652325320
0872064885880777
37540734625071823
3262683753213348069

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

2829760902235657
80342008251063828  x
23010250102180491  x
598011022656108827  x
704097036041428380
016808033275918830  x
431693229652325320  x
0872064885880777  x
37540734625071823  x
3262683753213348069  x
x

Create additional zeros

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

2526457601905354
80342008254063828
23010250132180491
598011022686108827
673766733038398077
016808033305918830
431693229682325320
0872064915880777
37540734655071823
3262683753243348069

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

2526457601905354
80342008254063828  x
23010250132180491  x
598011022686108827
673766733038398077
016808033305918830
431693229682325320
0872064915880777
37540734655071823  x
3262683753243348069  x
xxxxx

Create additional zeros

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

2522057201504954
843420482580103832
27010290172184495
59767018685708427
673326729034397677
012768029305518790
427653225681925280
0468060915480737
415401134695075827
3662684153283352073

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

2522057201504954
843420482580103832  x
27010290172184495  x
59767018685708427
673326729034397677
012768029305518790
427653225681925280
0468060915480737
415401134695075827
3662684153283352073  x
xxxxxx

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:

2520057001304754
863422682600123834
29012310192186497
59747016685508227
673126727032397477
010768027305318770
425653223681725260
0268058915280717
415201132694875627
3862704353303354075

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

2520057001304754  x
863422682600123834  x
29012310192186497  x
59747016685508227  x
673126727032397477  x
010768027305318770  x
425653223681725260  x
0268058915280717  x
415201132694875627  x
3862704353303354075  x

The optimal assignment

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

2520057001304754
863422682600123834
29012310192186497
59747016685508227
673126727032397477
010768027305318770
425653223681725260
0268058915280717
415201132694875627
3862704353303354075

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

59583588402778418484
97493414996442305241
28312275115192512
6483132276691129028
7745137443373568783
1327909046369738939
1136733636685539363
1117808759594988514
50651017477188911832
3866714059236461371

The optimal value equals 137.