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:

461725082935869
797695435039623
5241257162103847
142194941984592
4532856877682078
85775471474755
39555219678265
2351246421861293

Subtract row minima

We subtract the row minimum from each row:

450714981925768(-1)
737089374433017(-6)
423115615202837(-10)
51204032893683(-9)
251265485748058(-20)
7870470767048(-7)
37353017658063(-2)
11391252974081(-12)

Subtract column minima

We subtract the column minimum from each column:

400714974925751
68708937373300
373115614502820
01204025893666
201265485048041
7370470067031
32353010658046
6391252274064
(-5)(-7)(-17)

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

400714974925751  x
68708937373300  x
373115614502820  x
01204025893666  x
201265485048041
7370470067031  x
32353010658046  x
6391252274064
x

Create additional zeros

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

400714974925951
68708937373320
373115614503020
01204025893866
181063464846039
7370470067231
32353010658246
4371050072062

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

400714974925951  x
68708937373320  x
373115614503020  x
01204025893866  x
181063464846039
7370470067231
32353010658246
4371050072062
xxx

Create additional zeros

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

400715277926251
68708940403350
373115644803320
01204328894166
15760464843036
7067440064228
29050010628243
134750069059

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

400715277926251
68708940403350  x
373115644803320  x
01204328894166  x
15760464843036
7067440064228
29050010628243
134750069059
xxxx

Create additional zeros

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

390705277916250
68718941413360
373215654903420
01304429894266
14759464842035
6967430063227
28049010618242
034650068058

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

390705277916250  x
68718941413360  x
373215654903420  x
01304429894266  x
14759464842035  x
6967430063227  x
28049010618242  x
034650068058  x

The optimal assignment

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

390705277916250
68718941413360
373215654903420
01304429894266
14759464842035
6967430063227
28049010618242
034650068058

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

461725082935869
797695435039623
5241257162103847
142194941984592
4532856877682078
85775471474755
39555219678265
2351246421861293

The optimal value equals 102.