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:

78489398689876717
685474827046348847
72183380934403561
2673972252418245579
794954795872167514
2957304966280839832
36661819162526645192
48677359766240633930
3711137522435296685
52427264308479547644

Subtract row minima

We subtract the row minimum from each row:

74085358249472313(-4)
604666746238260039(-8)
71173279833393450(-1)
1764881343327336480(-9)
0242477251659687(-7)
2351244305674779226(-6)
2050230910483576(-16)
183743294632103390(-30)
3610036512334286584(-1)
2212423405449244614(-30)

Subtract column minima

We subtract the column minimum from each column:

74085328208472313
604666716234160039
71173276829293450
1764881043286336480
0242447247559687
2351244005264779226
205020050483576
18374326462803390
3610033511924286584
2212423105039244614
(-3)(-4)(-10)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

74085328208472313  x
604666716234160039  x
71173276829293450
1764881043286336480
0242447247559687  x
2351244005264779226
205020050483576  x
18374326462803390  x
3610033511924286584  x
2212423105039244614
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:

74085328708472318
604666716734160044
66122771824242900
125983543235831430
02424477475596812
1846193504759728726
205020550483581
18374326512803395
3610033561924286589
177372604534194114

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

74085328708472318  x
604666716734160044  x
66122771824242900  x
125983543235831430  x
02424477475596812  x
1846193504759728726
205020550483581  x
18374326512803395  x
3610033561924286589  x
177372604534194114
x

Create additional zeros

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

74085329408472318
604666717434160044
661227711524242900
125983550235831430
02424484475596812
1139122804052658019
2050201250483581
18374326582803395
3610033631924286589
10030190382712347

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

74085329408472318  x
604666717434160044  x
661227711524242900  x
125983550235831430  x
02424484475596812  x
1139122804052658019  x
2050201250483581  x
18374326582803395  x
3610033631924286589  x
10030190382712347  x

The optimal assignment

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

74085329408472318
604666717434160044
661227711524242900
125983550235831430
02424484475596812
1139122804052658019
2050201250483581
18374326582803395
3610033631924286589
10030190382712347

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

78489398689876717
685474827046348847
72183380934403561
2673972252418245579
794954795872167514
2957304966280839832
36661819162526645192
48677359766240633930
3711137522435296685
52427264308479547644

The optimal value equals 146.