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:

96409824575386902
4850733862573486
16372169573646891
78361539623779349
32515195311893
134662414157465460
602522598074488084
151587383516238193
188660365843861913

Subtract row minima

We subtract the row minimum from each row:

94389622555184880(-2)
4446693458169082(-4)
13341866540616588(-3)
75331236590749046(-3)
31405094201792(-1)
03349282844334147(-13)
3830375852265862(-22)
00722320186678(-15)
573472345307360(-13)

Subtract column minima

We subtract the column minimum from each column:

9438960355184880
4446691238169082
13341844340616588
75331214390749046
31402874201792
033496844334147
3830153852265862
007210186678
57347125307360
(-22)(-20)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

9438960355184880  x
4446691238169082  x
13341844340616588
75331214390749046
31402874201792  x
033496844334147  x
3830153852265862  x
007210186678  x
57347125307360  x
x

Create additional zeros

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

9438960356384880
44466912381369082
122632220495376
632102270627834
314028741401792
033496856334147
3830153864265862
0072101386678
57347125427360

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

9438960356384880  x
44466912381369082  x
122632220495376
632102270627834
314028741401792  x
033496856334147  x
3830153864265862
0072101386678  x
57347125427360  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:

9438970356484880
44467012381469082
021631210485275
622001260617733
314128741501792
033506857334147
3720143764255761
0073101486678
57348125437360

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

9438970356484880  x
44467012381469082  x
021631210485275
622001260617733
314128741501792  x
033506857334147
3720143764255761
0073101486678  x
57348125437360  x
xxx

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:

9538980356584880
45467112381569082
020630200475174
621900250607632
324228741601792
032505757324046
3710133664245660
1074101586678
67349125447360

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

9538980356584880
45467112381569082  x
020630200475174
621900250607632
324228741601792  x
032505757324046
3710133664245660
1074101586678  x
67349125447360
xxxxx

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:

9537980346583870
46467213381669083
019630190465074
621800240597532
334329741701793
031505657313946
3700133564235560
2075201686679
67249124447250

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

9537980346583870  x
46467213381669083  x
019630190465074  x
621800240597532  x
334329741701793  x
031505657313946  x
3700133564235560  x
2075201686679  x
67249124447250  x

The optimal assignment

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

9537980346583870
46467213381669083
019630190465074
621800240597532
334329741701793
031505657313946
3700133564235560
2075201686679
67249124447250

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

96409824575386902
4850733862573486
16372169573646891
78361539623779349
32515195311893
134662414157465460
602522598074488084
151587383516238193
188660365843861913

The optimal value equals 133.