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:

923395887246636
7128153256314089
856341763445572
6746695360347191
274032224792218
1981166631968485
945295108410717
1166328531333479

Subtract row minima

We subtract the row minimum from each row:

882991846806232(-4)
561301741162574(-15)
815901359405168(-4)
331235192603757(-34)
233628180751814(-4)
36505015806869(-16)
8745883773640(-7)
055217420222368(-11)

Subtract column minima

We subtract the column minimum from each column:

881791816804432
5610144116774
814701059403368
33035162601957
23242815075014
35304715805069
8733880773460
04321712022568
(-12)(-3)(-18)

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

881791816804432  x
5610144116774
814701059403368
33035162601957  x
23242815075014  x
35304715805069
8733880773460  x
04321712022568  x
x

Create additional zeros

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

881792816804432
5500134015673
80460958393267
33036162601957
23242915075014
25204614794968
8733890773460
04322712022568

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

881792816804432
5500134015673
80460958393267
33036162601957
23242915075014  x
25204614794968
8733890773460  x
04322712022568  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:

861792796604230
5300113815471
78460756393065
31036142401755
23263115077014
05204412794766
8735910775460
04524712024568

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

861792796604230
5300113815471
78460756393065
31036142401755
23263115077014  x
05204412794766
8735910775460  x
04524712024568
xxxx

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:

861792756203826
530073415067
78460352392661
31036102001351
27303515081014
0520408794362
9139950779460
04524671624164

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

861792756203826  x
530073415067  x
78460352392661
31036102001351  x
27303515081014  x
0520408794362
9139950779460  x
04524671624164
xx

Create additional zeros

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

871793756203826
540173415067
78450251382560
32037102001351
28303615081014
0510397784261
9239960779460
04424661523063

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

871793756203826
540173415067
78450251382560
32037102001351
28303615081014  x
0510397784261
9239960779460  x
04424661523063
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:

871793736003824
540153215065
78450049382558
3203781801349
30323815083214
0510375784259
94419807711480
04424641323061

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

871793736003824  x
540153215065  x
78450049382558  x
3203781801349  x
30323815083214  x
0510375784259  x
94419807711480  x
04424641323061  x

The optimal assignment

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

871793736003824
540153215065
78450049382558
3203781801349
30323815083214
0510375784259
94419807711480
04424641323061

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

923395887246636
7128153256314089
856341763445572
6746695360347191
274032224792218
1981166631968485
945295108410717
1166328531333479

The optimal value equals 145.