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:

292574581507616692
8857539539439337228
5265864497860828764
6870321466874917764
10272688528573728210
744357529139137710
5990352625320159974
430724514834664583
89147527231383613582
86966656779108530

Subtract row minima

We subtract the row minimum from each row:

242069076457111187(-5)
8049458731358529140(-8)
0215359447355778259(-5)
6769310456773907663(-1)
017167842756362720(-10)
71105449883610747(-3)
5788330605118139772(-2)
127694211804361550(-3)
761621410070482269(-13)
8036005017347924(-6)

Subtract column minima

We subtract the column minimum from each column:

24196906645537087
8048458721356725130
0205359347337738159
6768310356755867563
016167832754558710
7100543988186737
57873305051099672
12669421802557540
76062140052442169
8026004015507824
(-1)(-10)(-18)(-4)(-1)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

24196906645537087  x
8048458721356725130
0205359347337738159
6768310356755867563  x
016167832754558710
7100543988186737  x
57873305051099672  x
12669421802557540
76062140052442169  x
8026004015507824  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:

25196906645537088
8047448620346624120
0195258337236728059
6868310356755867564
015157731744457700
7200543988186738
58873305051099673
12568410792456530
77062140052442170
8126004015507825

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

25196906645537088  x
8047448620346624120
0195258337236728059
6868310356755867564  x
015157731744457700
7200543988186738  x
58873305051099673  x
12568410792456530  x
77062140052442170  x
8126004015507825  x
xx

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:

371969066455370100
80353274822541200
074046216024606859
8068310356755867576
0336519623245580
84005439881867320
70873305051099685
1325684107924565312
89062140052442182
9326004015507837

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

371969066455370100
80353274822541200
074046216024606859
8068310356755867576
0336519623245580
84005439881867320  x
70873305051099685  x
1325684107924565312  x
89062140052442182  x
9326004015507837  x
xxxx

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:

371666063425040100
8032297451951900
043746185721576859
8065280326452837576
0006516592942580
87005739881867623
73873335051099988
1625684407924565615
92062170052442485
9626034015508140

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

371666063425040100  x
8032297451951900  x
043746185721576859  x
8065280326452837576  x
0006516592942580  x
87005739881867623  x
73873335051099988  x
1625684407924565615  x
92062170052442485  x
9626034015508140  x

The optimal assignment

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

371666063425040100
8032297451951900
043746185721576859
8065280326452837576
0006516592942580
87005739881867623
73873335051099988
1625684407924565615
92062170052442485
9626034015508140

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

292574581507616692
8857539539439337228
5265864497860828764
6870321466874917764
10272688528573728210
744357529139137710
5990352625320159974
430724514834664583
89147527231383613582
86966656779108530

The optimal value equals 107.