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:

8389661891735473
89738247542535657
49664236623151471
506970269565273
814574345032174228
788210177393772979
276063255091148642
333382976615273436
3520929265937696

Subtract row minima

We subtract the row minimum from each row:

8086631588405170(-3)
87718045520515455(-2)
45623832582747067(-4)
486768249363051(-2)
64285717331502511(-17)
6872076383671969(-10)
13464911367707228(-14)
18186782510121921(-15)
3015878710887191(-5)

Subtract column minima

We subtract the column minimum from each column:

677163887405169
74568038510515454
32473825572747066
355268179263050
51135710321502510
5557006283671968
031494357707227
536775500121920
170878000887190
(-13)(-15)(-7)(-1)(-1)

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

677163887405169
74568038510515454
32473825572747066  x
355268179263050  x
51135710321502510
5557006283671968  x
031494357707227  x
536775500121920
170878000887190  x
xx

Create additional zeros

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

646860584404866
71537735480515151
32473825573050066
355268179266350
481054729150227
5557006286701968
031494358037227
206472470121617
170878003917190

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

646860584404866
71537735480515151  x
32473825573050066  x
355268179266350  x
481054729150227
5557006286701968  x
031494358037227  x
206472470121617  x
170878003917190  x
x

Create additional zeros

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

606456180004462
71537735480555151
32473825573054066
355268179266750
44650325110183
5557006286741968
031494358077227
206472470161617
170878003957190

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

606456180004462
71537735480555151
32473825573054066  x
355268179266750  x
44650325110183
5557006286741968  x
031494358077227  x
206472470161617  x
170878003957190  x
xx

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:

596355079004361
70527634470555050
32473825573155066
355268179267850
43549224110172
5557006287751968
031494358187227
206472471171617
170878004967190

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

596355079004361  x
70527634470555050  x
32473825573155066  x
355268179267850  x
43549224110172  x
5557006287751968  x
031494358187227  x
206472471171617  x
170878004967190  x

The optimal assignment

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

596355079004361
70527634470555050
32473825573155066
355268179267850
43549224110172
5557006287751968
031494358187227
206472471171617
170878004967190

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

8389661891735473
89738247542535657
49664236623151471
506970269565273
814574345032174228
788210177393772979
276063255091148642
333382976615273436
3520929265937696

The optimal value equals 120.