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:

335121371909347471
47508644184664272
1684479165117367993
13195050629264554989
3081874349412065
75197654276264643028
4472116511540774476
34988878884456157
4952374997115979676
36804228497111187128

Subtract row minima

We subtract the row minimum from each row:

314901169887327269(-2)
45486623982644050(-2)
0674378155016357892(-1)
063737497951423676(-13)
2970863339301964(-1)
56057358434545119(-19)
4371015501439764375(-1)
29938373833905602(-5)
4401869946610929171(-5)
256931173860076017(-11)

Subtract column minima

We subtract the column minimum from each column:

31490066747327269
45486513668644050
0674367123616357892
063726466551423676
2970750199301964
56057245294545119
43710447039764375
29938362802505602
4401858915210929171
25693163546076017
(-11)(-3)(-14)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

31490066747327269  x
45486513668644050  x
0674367123616357892
063726466551423676
2970750199301964  x
56057245294545119
43710447039764375  x
29938362802505602  x
4401858915210929171
25693163546076017  x
xx

Create additional zeros

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

36540066747327269
50536513668644050
067386273111307387
063221416046373171
34120750199301964
5605219024404064
48760447039764375
34988362802505602
440135386475878666
30743163546076017

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

36540066747327269  x
50536513668644050  x
067386273111307387
063221416046373171
34120750199301964  x
5605219024404064  x
48760447039764375  x
34988362802505602  x
440135386475878666  x
30743163546076017  x
x

Create additional zeros

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

42540066747327269
56536513668644050
06132561255246781
002615355440312565
40120750199301964
6205219024404064
54760447039764375
40988362802505602
500135386475878666
36743163546076017

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

42540066747327269  x
56536513668644050  x
06132561255246781
002615355440312565
40120750199301964  x
6205219024404064  x
54760447039764375  x
40988362802505602  x
500135386475878666
36743163546076017  x
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:

43550066747327269
57546513668644050
06131550244236680
002514345339302464
41130750199301964
6315219024404064
55770447039764375
41998362802505602
500125285464868565
37753163546076017

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

43550066747327269  x
57546513668644050  x
06131550244236680
002514345339302464
41130750199301964  x
6315219024404064
55770447039764375  x
41998362802505602  x
500125285464868565
37753163546076017  x
xxx

Create additional zeros

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

47590070747327269
61586514068644050
06127510200196276
002110344935262060
45170754199301964
6314815020363620
59810451039764375
451038362842505602
50084885420828161
41793163946076017

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

47590070747327269  x
61586514068644050
06127510200196276
002110344935262060
45170754199301964  x
6314815020363620
59810451039764375  x
451038362842505602  x
50084885420828161
41793163946076017
xxxxx

Create additional zeros

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

49610072749327271
61584494066643830
06125490180176076
00198344735241860
47190756199501966
6314613018363400
61830453041764377
471058362862525604
50064685400807961
41792943944055817

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

49610072749327271  x
61584494066643830
06125490180176076
00198344735241860
47190756199501966  x
6314613018363400
61830453041764377  x
471058362862525604
50064685400807961
41792943944055817
xxxxxx

Create additional zeros

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

536500767413327675
61580454062643430
06121450140136076
00154344335201860
512307510199902370
631429014363000
65870457045764781
471057958862125204
50024285360767961
41792503940015817

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

536500767413327675  x
61580454062643430  x
06121450140136076  x
00154344335201860  x
512307510199902370  x
631429014363000  x
65870457045764781  x
471057958862125204  x
50024285360767961  x
41792503940015817  x

The optimal assignment

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

536500767413327675
61580454062643430
06121450140136076
00154344335201860
512307510199902370
631429014363000
65870457045764781
471057958862125204
50024285360767961
41792503940015817

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

335121371909347471
47508644184664272
1684479165117367993
13195050629264554989
3081874349412065
75197654276264643028
4472116511540774476
34988878884456157
4952374997115979676
36804228497111187128

The optimal value equals 115.