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:

58274310265591162318
8728837899565798523
13624361936985212218
2842425788183145978
5129823333759241061
78496588305838788713
16488017354187198928
71129489983682639219
62853963938288936624
38114948547985326239

Subtract row minima

We subtract the row minimum from each row:

48173301645816138(-10)
7920029818757717715(-8)
0493048805672895(-13)
2539395485150115675(-3)
422073242466015152(-9)
6536527517452565740(-13)
03264119257137312(-16)
590827786247051807(-12)
3861153969586469420(-24)
2703837436874215128(-11)

Subtract column minima

We subtract the column minimum from each column:

4817330030813128
7920029657257687615
0493048644172585
25393954690085575
42207324851012052
653652751302562730
0326413107107212
59082777097048797
3861153953436466410
2703837275374185028
(-16)(-15)(-3)(-1)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

4817330030813128  x
7920029657257687615  x
0493048644172585  x
25393954690085575  x
42207324851012052  x
653652751302562730
0326413107107212  x
59082777097048797
3861153953436466410
2703837275374185028
xx

Create additional zeros

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

4818330030813129
7921029657257687616
0503048644172586
25403954690085576
42217324851012053
643651740292461720
0336413107107213
58081766986947787
3761143852426365400
2603736265273174928

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

4818330030813129  x
7921029657257687616  x
0503048644172586  x
25403954690085576  x
42217324851012053  x
643651740292461720  x
0336413107107213  x
58081766986947787
3761143852426365400  x
2603736265273174928
x

Create additional zeros

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

4825330030813129
7928029657257687616
0573048644172586
25473954690085576
42287324851012053
644351740292461720
0406413107107213
51074696216240710
3768143852426365400
1903029194566104221

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

4825330030813129  x
7928029657257687616  x
0573048644172586  x
25473954690085576  x
42287324851012053  x
644351740292461720  x
0406413107107213  x
51074696216240710
3768143852426365400
1903029194566104221
xx

Create additional zeros

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

48263300308131210
7929029657257687617
0583048644172587
25483954690085577
42297324851012054
644451740292461721
0416413107107214
50073686106139700
3668133751416264390
180292818446594121

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

48263300308131210  x
7929029657257687617  x
0583048644172587  x
25483954690085577  x
42297324851012054  x
644451740292461721  x
0416413107107214  x
50073686106139700  x
3668133751416264390  x
180292818446594121  x

The optimal assignment

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

48263300308131210
7929029657257687617
0583048644172587
25483954690085577
42297324851012054
644451740292461721
0416413107107214
50073686106139700
3668133751416264390
180292818446594121

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

58274310265591162318
8728837899565798523
13624361936985212218
2842425788183145978
5129823333759241061
78496588305838788713
16488017354187198928
71129489983682639219
62853963938288936624
38114948547985326239

The optimal value equals 164.