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:

8818513139094
98324938704288
32776891867078
74376261447198
56507610304048
70513432379751
22653530386899

Subtract row minima

We subtract the row minimum from each row:

07377558286(-8)
660176381056(-32)
0453659543846(-32)
370252473461(-37)
4640660203038(-10)
38192056519(-32)
043138164677(-22)

Subtract column minima

We subtract the column minimum from each column:

07375507267
66015633037
0453459492827
370232422442
4640640152019
3819000550
043118113658
(-2)(-5)(-10)(-19)

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

07375507267  x
66015633037  x
0453459492827
370232422442  x
4640640152019  x
3819000550  x
043118113658
x

Create additional zeros

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

87375507267
74015633037
0372651412019
450232422442
5440640152019
4619000550
0353032850

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

87375507267  x
74015633037  x
0372651412019
450232422442  x
5440640152019
4619000550  x
0353032850
xx

Create additional zeros

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

117375807267
77015933037
0342351381716
480232722442
5437610121716
4919030550
0320002547

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

117375807267  x
77015933037  x
0342351381716  x
480232722442  x
5437610121716  x
4919030550  x
0320002547  x

The optimal assignment

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

117375807267
77015933037
0342351381716
480232722442
5437610121716
4919030550
0320002547

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

8818513139094
98324938704288
32776891867078
74376261447198
56507610304048
70513432379751
22653530386899

The optimal value equals 220.