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:

32958807318109796
8582386847229380
51404335911858578
2433185055461596
115819995677623428
52293179134253879
228021973255640
864313946838256728
28295023158631216

Subtract row minima

We subtract the row minimum from each row:

230497164918887(-9)
8279356544196077(-3)
4231342602767669(-9)
2029144651057192(-4)
0478884566512317(-11)
45222408427183172(-7)
207819771053438(-2)
73300815525125415(-13)
26274821138429014(-2)

Subtract column minima

We subtract the column minimum from each column:

230497164908873
8279356544195063
4231342602757655
2029144651056178
047888456650233
45222408427173158
207819771052424
7330081552511541
2627482113842800
(-1)(-14)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

230497164908873  x
8279356544195063  x
4231342602757655  x
2029144651056178
047888456650233  x
45222408427173158  x
207819771052424
7330081552511541  x
2627482113842800  x
x

Create additional zeros

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

2304971641008873
8279356544205063
4231342603757655
1928134550055077
047888456750233
45222408428173158
197718670051323
7330081552611541
2627482113852800

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

2304971641008873  x
8279356544205063
4231342603757655  x
1928134550055077
047888456750233  x
45222408428173158  x
197718670051323
7330081552611541  x
2627482113852800  x
xx

Create additional zeros

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

2304971641509373
7774306039200058
4231342608758155
142384045050072
047888457250283
45222408433173658
147213165046318
7330081553111591
2627482113902850

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

2304971641509373  x
7774306039200058  x
4231342608758155  x
142384045050072  x
047888457250283  x
45222408433173658  x
147213165046318  x
7330081553111591  x
2627482113902850  x

The optimal assignment

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

2304971641509373
7774306039200058
4231342608758155
142384045050072
047888457250283
45222408433173658
147213165046318
7330081553111591
2627482113902850

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

32958807318109796
8582386847229380
51404335911858578
2433185055461596
115819995677623428
52293179134253879
228021973255640
864313946838256728
28295023158631216

The optimal value equals 81.