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:

63361388428141
51544664599101
9419803792901121
9275243849943169
9978693260236014
41605389863272
5282548493401179
6291177284663069

Subtract row minima

We subtract the row minimum from each row:

62351287417040(-1)
5044365449890(-1)
83869268179010(-11)
68510142570745(-24)
85645518469460(-14)
33524501782464(-8)
417143738229068(-11)
457405567491352(-17)

Subtract column minima

We subtract the column minimum from each column:

29311287400040
1704365439190
50469268072010
35470142463745
52605518452460
0484500712464
86743738122068
127005566421352
(-33)(-4)(-1)(-7)

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

29311287400040  x
1704365439190  x
50469268072010
35470142463745
52605518452460  x
0484500712464  x
86743738122068
127005566421352
xx

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:

29311687400440
17047654391130
4606922766806
31430102059741
52605918452500
0484900712864
46343697718064
86605162381348

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

29311687400440  x
17047654391130
4606922766806
31430102059741
52605918452500
0484900712864  x
46343697718064
86605162381348
xxxx

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:

29331887400642
15047634189130
4406920746606
2943081857741
50605916430500
0505100713066
26343677516064
66604960361348

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

29331887400642
15047634189130
4406920746606
2943081857741
50605916430500
0505100713066  x
26343677516064
66604960361348
xxxxx

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:

27331885380642
13047613989130
4206918726606
2743061657741
48605914410500
0525300733268
06343657316064
46604758361348

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

27331885380642  x
13047613989130  x
4206918726606  x
2743061657741
48605914410500  x
0525300733268  x
06343657316064  x
46604758361348
x

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:

27332285380642
13051613989130
4207318726606
2339021253337
48606314410500
0525700733268
06347657316064
0620435432944

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

27332285380642
13051613989130
4207318726606
2339021253337
48606314410500
0525700733268  x
06347657316064
0620435432944
xxxxxx

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:

27332283360642
13051593789130
4207316706606
2339001053337
48606312390500
2545900753470
06347637116064
0620415232944

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

27332283360642  x
13051593789130  x
4207316706606  x
2339001053337  x
48606312390500  x
2545900753470  x
06347637116064  x
0620415232944  x

The optimal assignment

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

27332283360642
13051593789130
4207316706606
2339001053337
48606312390500
2545900753470
06347637116064
0620415232944

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

63361388428141
51544664599101
9419803792901121
9275243849943169
9978693260236014
41605389863272
5282548493401179
6291177284663069

The optimal value equals 154.