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:

4712875606466530
45665878991722677
48956538227701853
422860152038924719
45717823606178694
2530134758658226
89308420397160138
87875664212611857
765031771427483515

Subtract row minima

We subtract the row minimum from each row:

0672471566062126(-4)
05261838587682273(-4)
41885831150631146(-7)
271345052377324(-15)
39657217540118088(-6)
2328114556636024(-2)
8122761231635250(-8)
86865563202501756(-1)
6236176301334211(-14)

Subtract column minima

We subtract the column minimum from each column:

0541371566062126
03950838587682273
41754731150631146
27034052377324
39526117540118088
231504556636024
819651231635250
86734463202501756
622366301334211
(-13)(-11)

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

0541371566062126
03950838587682273
41754731150631146
27034052377324  x
39526117540118088
231504556636024  x
819651231635250  x
86734463202501756  x
622366301334211  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:

0531270556061025
03849828487672172
41744630140621045
28034052477324
39516016530107987
241504556646024
829651231645250
87734463202601756
632366301434211

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

0531270556061025  x
03849828487672172  x
41744630140621045
28034052477324  x
39516016530107987
241504556646024  x
829651231645250  x
87734463202601756  x
632366301434211  x
x

Create additional zeros

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

0531270557061025
03849828497672172
316436204052035
28034053477324
294150643006977
241504556746024
829651231745250
87734463203601756
632366302434211

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

0531270557061025
03849828497672172
316436204052035
28034053477324  x
294150643006977
241504556746024  x
829651231745250  x
87734463203601756
632366302434211  x
xxxx

Create additional zeros

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

049866517061021
03445788097672168
316032160052031
32034053881364
293746239006973
2815045567810424
869651231785690
87694059163601752
672366302838251

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

049866517061021
03445788097672168
316032160052031
32034053881364  x
293746239006973
2815045567810424  x
869651231785690  x
87694059163601752
672366302838251
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:

048765517061020
03344778097672167
315931150052030
33034063982374
293645139006972
2915045577911524
8796512327957100
87683958163601751
672256202838250

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

048765517061020
03344778097672167
315931150052030
33034063982374  x
293645139006972
2915045577911524  x
8796512327957100
87683958163601751
672256202838250
xxxxxx

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:

047664517061020
03243768097672167
315830140052030
34034074083385
293544039006972
3015045588012625
8786411327957100
87673857163601751
672146102838250

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

047664517061020  x
03243768097672167  x
315830140052030  x
34034074083385  x
293544039006972  x
3015045588012625  x
8786411327957100  x
87673857163601751  x
672146102838250  x

The optimal assignment

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

047664517061020
03243768097672167
315830140052030
34034074083385
293544039006972
3015045588012625
8786411327957100
87673857163601751
672146102838250

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

4712875606466530
45665878991722677
48956538227701853
422860152038924719
45717823606178694
2530134758658226
89308420397160138
87875664212611857
765031771427483515

The optimal value equals 103.