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:

7695790753180385
6396975686141084
299986654861862691
439053285072505187
2624339889108812
69951411729669527
8239647315782131
6112632545924426
5882290357375238

Subtract row minima

We subtract the row minimum from each row:

7145285702675330(-5)
57363690808478(-6)
3736039223560065(-26)
15622502244222359(-28)
242231968786790(-2)
628874022598820(-7)
7936614012751828(-3)
5910610525722404(-2)
5680088337173216(-2)

Subtract column minima

We subtract the column minimum from each column:

6815285701869330
54063690722478
0706039222754065
12592502236162359
211931968700790
598574014538820
763361404691828
567610524916404
5377088336367216
(-3)(-3)(-8)(-6)

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

6815285701869330  x
54063690722478  x
0706039222754065  x
12592502236162359
211931968700790  x
598574014538820
763361404691828
567610524916404
5377088336367216  x
xx

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:

6815289741869330
54063734722478
0706043262754065
8552102232121955
2119311009100790
558134010498416
722957400651424
523570524512360
5377092376367216

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

6815289741869330
54063734722478  x
0706043262754065  x
8552102232121955
2119311009100790  x
558134010498416  x
722957400651424  x
523570524512360
5377092376367216  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:

6705189731768320
54063744722479
0706044262754066
7542002131111855
2119311019100791
558135010498417
722957500651425
512560514411350
5377093376367217

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

6705189731768320
54063744722479
0706044262754066  x
7542002131111855
2119311019100791  x
558135010498417  x
722957500651425  x
512560514411350
5377093376367217  x
xxx

Create additional zeros

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

6504989711566300
52061742700279
0726046262754068
554180192991655
2121311039100793
558337010498419
723157700651427
49254049429330
5379095376367219

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

6504989711566300
52061742700279
0726046262754068  x
554180192991655
2121311039100793
558337010498419
723157700651427
49254049429330
5379095376367219  x
xxxxxx

Create additional zeros

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

6304789711566280
50059742700079
0746048282956070
354160192991455
1921291039100773
538317010498219
703155700651227
47252049429310
53810973965692111

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

6304789711566280  x
50059742700079  x
0746048282956070  x
354160192991455  x
1921291039100773  x
538317010498219  x
703155700651227  x
47252049429310  x
53810973965692111  x

The optimal assignment

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

6304789711566280
50059742700079
0746048282956070
354160192991455
1921291039100773
538317010498219
703155700651227
47252049429310
53810973965692111

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

7695790753180385
6396975686141084
299986654861862691
439053285072505187
2624339889108812
69951411729669527
8239647315782131
6112632545924426
5882290357375238

The optimal value equals 114.