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:

9538482315518520
882876254464784
3198346571271
845097512732609
59605439248077
1285311674793
369345232521627
231563614881478

Subtract row minima

We subtract the row minimum from each row:

8023338036705(-15)
842472210424380(-4)
016531624968(-3)
754188421823510(-9)
04554934197572(-5)
1184300573782(-1)
298638161814550(-7)
15755534073390(-8)

Subtract column minima

We subtract the column minimum from each column:

8019288032615
842067210383480
012031620068
753783421819420
00504934156672
1180250569692
298233161810460
15350534069300
(-4)(-5)(-4)(-9)

Cover all zeros with a minimum number of lines

There are 5 lines required to cover all zeros:

8019288032615
842067210383480
012031620068  x
753783421819420
00504934156672  x
1180250569692  x
298233161810460
15350534069300
xx

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:

7716255029585
811764180353180
012031650071
723480391816390
00504937156675
1180250869695
26793013187430
12047504066270

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

7716255029585
811764180353180
012031650071  x
723480391816390
00504937156675  x
1180250869695  x
26793013187430
12047504066270  x
xx

Create additional zeros

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

7211200024535
761259130302680
012031700076
672975341811340
00504942156680
118025013696910
2174258182380
12047504566275

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

7211200024535
761259130302680
012031700076  x
672975341811340
00504942156680  x
118025013696910
2174258182380
12047504566275  x
xxx

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:

709180022515
741057130282480
012033720078
65277334189320
00505144156682
97823013676710
1972238180360
12047524766277

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

709180022515
741057130282480
012033720078  x
65277334189320  x
00505144156682  x
97823013676710
1972238180360  x
12047524766277  x
xx

Create additional zeros

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

654130017460
69552130231975
012038770078
65277339239320
00505649156682
4731801362625
19722313230360
12047575266277

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

654130017460
69552130231975
012038770078  x
65277339239320
00505649156682  x
4731801362625
19722313230360  x
12047575266277  x
xxx

Create additional zeros

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

61090013420
65148130191575
012042810082
61236939235280
00506053156686
0691401358585
19722317270364
120476156662711

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

61090013420
65148130191575
012042810082  x
61236939235280
00506053156686
0691401358585
19722317270364  x
120476156662711
xxxxx

Create additional zeros

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

6104008370
65143130141075
517047860087
61236439230230
00456053106186
069901353535
24772322320369
120426156612211

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

6104008370
65143130141075
517047860087  x
61236439230230
00456053106186
069901353535
24772322320369
120426156612211
xxxxxx

Create additional zeros

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

6100008330
6513913014675
921051904091
61236039230190
00416053105786
069501353495
24771922320329
120386156611811

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

6100008330  x
6513913014675  x
921051904091  x
61236039230190  x
00416053105786  x
069501353495  x
24771922320329  x
120386156611811  x

The optimal assignment

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

6100008330
6513913014675
921051904091
61236039230190
00416053105786
069501353495
24771922320329
120386156611811

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

9538482315518520
882876254464784
3198346571271
845097512732609
59605439248077
1285311674793
369345232521627
231563614881478

The optimal value equals 115.