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:

8231881294
525084315943
948738421956
82228929707
638054989011
8821549905

Subtract row minima

We subtract the row minimum from each row:

7220871193(-1)
21195302812(-31)
75681923037(-19)
75158222630(-7)
52694387790(-11)
8601347883(-2)

Subtract column minima

We subtract the column minimum from each column:

0220871193
14195302812
68681923037
68158222630
45694387790
7901347883
(-7)

Cover all zeros with a minimum number of lines

There are 5 lines required to cover all zeros:

0220871193  x
14195302812  x
68681923037  x
68158222630
45694387790
7901347883  x
x

Create additional zeros

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

02208711108
14195302827
68681923052
530677480
30542872640
79013478818

Cover all zeros with a minimum number of lines

There are 5 lines required to cover all zeros:

02208711108  x
14195302827  x
68681923052  x
530677480
30542872640
79013478818
xx

Create additional zeros

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

02908711115
14265302834
68751923059
460600410
23542165570
7206408118

Cover all zeros with a minimum number of lines

There are 5 lines required to cover all zeros:

02908711115  x
14265302834
68751923059  x
460600410
23542165570
7206408118
xxx

Create additional zeros

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

03509311121
8264702234
68811929065
400540350
17541565510
6600407518

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

03509311121  x
8264702234  x
68811929065  x
400540350  x
17541565510  x
6600407518  x

The optimal assignment

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

03509311121
8264702234
68811929065
400540350
17541565510
6600407518

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

8231881294
525084315943
948738421956
82228929707
638054989011
8821549905

The optimal value equals 106.