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:

8776581703072735728
59405366635394653615
3365289572702981248
8880405241503367462
99778665804051667965
2159109818922569810
61269621751626291138
57244159795345812398
57525879526834405727
1167877389485965171

Subtract row minima

We subtract the row minimum from each row:

8675570692971725627(-1)
4425385148387950210(-15)
2557208764622173160(-8)
8476364837462963058(-4)
5937462540011263925(-40)
1250189901347891(-9)
501585106451518027(-11)
341183656302258075(-23)
302531522541713300(-27)
359796508677884363(-8)

Subtract column minima

We subtract the column minimum from each column:

8374560692964595627
4124375148387237210
2256198764621460160
8175354837462250058
563645254004133925
94908990634891
4714841064585027
310173656301545075
27243052254100300
058786508670754363
(-3)(-1)(-1)(-7)(-13)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

8374560692964595627  x
4124375148387237210
2256198764621460160
8175354837462250058
563645254004133925  x
94908990634891  x
4714841064585027
310173656301545075  x
27243052254100300  x
058786508670754363  x
xx

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:

8374560692964596132
3619324643336732210
175114825957955160
7670304332411745058
563645254004134430
94908990634946
42979559030027
310173656301545580
27243052254100355
058786508670754868

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

8374560692964596132  x
3619324643336732210
175114825957955160
7670304332411745058  x
563645254004134430  x
94908990634946  x
42979559030027  x
310173656301545580  x
27243052254100355  x
058786508670754868  x
x

Create additional zeros

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

8374560692964596141
2710233734245823120
842573504804670
7670304332411745067
563645254004134439
949089906349415
42979559030036
310173656301545589
272430522541003514
058786508670754877

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

8374560692964596141  x
2710233734245823120
842573504804670
7670304332411745067
563645254004134439
949089906349415  x
42979559030036
310173656301545589  x
272430522541003514
058786508670754877  x
xxxxx

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:

8374560693469646646
225183229245823120
337068454804670
7165253827411745067
513140203504134439
9490899511399920
37474054030036
3101736563520501094
221925472041003514
058786509175805382

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

8374560693469646646
225183229245823120
337068454804670
7165253827411745067
513140203504134439
9490899511399920
37474054030036
3101736563520501094  x
221925472041003514
058786509175805382  x
xxxxxxx

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:

8071560663469646646
192183226245823120
034068424804670
6862253824411745067
482840203204134439
6460896511399920
34174051030036
3102039563823531397
191625471741003514
058816809478835685

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

8071560663469646646  x
192183226245823120  x
034068424804670  x
6862253824411745067  x
482840203204134439  x
6460896511399920  x
34174051030036  x
3102039563823531397  x
191625471741003514  x
058816809478835685  x

The optimal assignment

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

8071560663469646646
192183226245823120
034068424804670
6862253824411745067
482840203204134439
6460896511399920
34174051030036
3102039563823531397
191625471741003514
058816809478835685

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

8776581703072735728
59405366635394653615
3365289572702981248
8880405241503367462
99778665804051667965
2159109818922569810
61269621751626291138
57244159795345812398
57525879526834405727
1167877389485965171

The optimal value equals 198.