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:

8178484165014233476
5471439120576371079
57125494674490714666
14919297839895137218
10203152642235715311
7915144851295181196
24701072889098541566
296663295055785379
7274241024672049045
56642054976186775331

Subtract row minima

We subtract the row minimum from each row:

7774080124610193072(-4)
486537851451031473(-6)
4504282553278593454(-12)
17879847085820595(-13)
010214254122561431(-10)
74109434624013691(-5)
146006278808844556(-10)
276461074853765177(-2)
687020620631608641(-4)
3644034774166573311(-20)

Subtract column minima

We subtract the column minimum from each column:

777408053410192671
48653785739031072
4504282482078593053
17879846373820554
01021424702561390
74109433912013290
146006271688844155
276461003653764776
687020613511608240
3644034702966572910
(-7)(-12)(-4)(-1)

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

777408053410192671
48653785739031072  x
4504282482078593053  x
17879846373820554
01021424702561390  x
74109433912013290  x
146006271688844155
276461003653764776  x
687020613511608240
3644034702966572910
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:

76730794339192570
48653885739032072
4504382482078603053
07779836272810543
01022424702562390
741010433912014290
135906170678744054
276462003653774776
676920512501508139
354303369286557289

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

76730794339192570
48653885739032072
4504382482078603053  x
07779836272810543  x
01022424702562390  x
741010433912014290
135906170678744054
276462003653774776  x
676920512501508139  x
354303369286557289
xxx

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:

72690750299152566
44613881335028068
4504782482082603453
07783836272850583
01026424702962430
7061039358010286
95505766638740050
276466003657775176
676924512501908539
313902965246553285

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

72690750299152566  x
44613881335028068
4504782482082603453  x
07783836272850583  x
01026424702962430  x
7061039358010286
95505766638740050
276466003657775176  x
676924512501908539  x
313902965246553285
xxx

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:

726937502912152866
41583878032025065
4505082482085603753
07786836272880613
01029424703262460
673103632507283
65205463608737047
276469003660775476
676927512502208839
283602662216550282

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

726937502912152866
41583878032025065
4505082482085603753  x
07786836272880613  x
01029424703262460  x
673103632507283
65205463608737047
276469003660775476  x
676927512502208839  x
283602662216550282
xxxx

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:

706737302712132864
39563876030023063
4505282502087603953
07788836472900633
01031424903462480
651103432305281
45005263588735045
276471023662775676
676929514502409039
263402462196548280

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

706737302712132864  x
39563876030023063  x
4505282502087603953  x
07788836472900633  x
01031424903462480  x
651103432305281  x
45005263588735045  x
276471023662775676  x
676929514502409039  x
263402462196548280  x

The optimal assignment

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

706737302712132864
39563876030023063
4505282502087603953
07788836472900633
01031424903462480
651103432305281
45005263588735045
276471023662775676
676929514502409039
263402462196548280

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

8178484165014233476
5471439120576371079
57125494674490714666
14919297839895137218
10203152642235715311
7915144851295181196
24701072889098541566
296663295055785379
7274241024672049045
56642054976186775331

The optimal value equals 126.