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:

748256485727625242
85511062783550813947
86784288124885295060
39305333783475931374
909155074361651880
57669241478378914990
2922853765960783931
36663196354011478559
77452788551992634647
622447587472916627

Subtract row minima

We subtract the row minimum from each row:

546236283707405040(-2)
7541052682540712937(-10)
7466307603673173848(-12)
2617402065216280061(-13)
858604569311146375(-5)
16255106423750849(-41)
2114045685152703123(-8)
2555208524290367448(-11)
582686936073442728(-19)
016386981412310561(-6)

Subtract column minima

We subtract the column minimum from each column:

532236283707405039
7527052682540712936
7452307603673173847
263402065216280060
857204569311146374
16115106423750848
210045685152703122
2541208524290367447
581286936073442727
02386981412310560
(-14)(-1)

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

532236283707405039  x
7527052682540712936
7452307603673173847  x
263402065216280060  x
857204569311146374
16115106423750848  x
210045685152703122  x
2541208524290367447  x
581286936073442727  x
02386981412310560  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:

532266283707405039
7224049652237682633
7452337603673173847
263432065216280060
82690426628843071
16115406423750848
210345685152703122
2541238524290367447
5812116936073442727
02416981412310560

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

532266283707405039  x
7224049652237682633
7452337603673173847  x
263432065216280060
82690426628843071
16115406423750848  x
210345685152703122  x
2541238524290367447  x
5812116936073442727  x
02416981412310560  x
xx

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:

532296283707405339
6921046621934652630
7452367603673174147
230431762185977057
79660396325540068
161157064237501148
210645685152703422
2541268524290367747
5812146936073443027
02446981412310590

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

532296283707405339  x
6921046621934652630
7452367603673174147  x
230431762185977057
79660396325540068
161157064237501148  x
210645685152703422
2541268524290367747  x
5812146936073443027  x
02446981412310590  x
xxx

Create additional zeros

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

537346283707405839
6421041571429602625
7457417603673174647
180431257135472052
74660345820035063
161662064237501648
160640634647653417
2546318524290368247
5817196936073443527
07496981412310640

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

537346283707405839  x
6421041571429602625
7457417603673174647  x
180431257135472052
74660345820035063
161662064237501648  x
160640634647653417
2546318524290368247
5817196936073443527  x
07496981412310640  x
xxxx

Create additional zeros

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

549466283708607039
522102945229482613
7469537603685175847
604304515460040
6266022468023051
162874064249502848
4062851344753345
1346317312170248235
5829316936085444727
019616981413510760

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

549466283708607039  x
522102945229482613
7469537603685175847  x
604304515460040
6266022468023051
162874064249502848
4062851344753345
1346317312170248235
5829316936085444727  x
019616981413510760  x
xxxxx

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:

550476383708707139
512102944129472612
7470547703686175947
504304405459039
6166022457022050
152874054149492847
3062850334752344
1246317311160238234
5830327036086444827
020627081413610770

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

550476383708707139  x
512102944129472612
7470547703686175947  x
504304405459039
6166022457022050
152874054149492847
3062850334752344
1246317311160238234
5830327036086444827
020627081413610770  x
xxxxxx

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:

553506683739007439
48210294112944269
7473578003989176247
204304105456036
5866022427019047
122874024149462844
0062847334749341
94631738160208231
5530327033086414824
023657381443910800

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

553506683739007439  x
48210294112944269  x
7473578003989176247  x
204304105456036  x
5866022427019047  x
122874024149462844  x
0062847334749341  x
94631738160208231  x
5530327033086414824  x
023657381443910800  x

The optimal assignment

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

553506683739007439
48210294112944269
7473578003989176247
204304105456036
5866022427019047
122874024149462844
0062847334749341
94631738160208231
5530327033086414824
023657381443910800

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

748256485727625242
85511062783550813947
86784288124885295060
39305333783475931374
909155074361651880
57669241478378914990
2922853765960783931
36663196354011478559
77452788551992634647
622447587472916627

The optimal value equals 169.