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:

89633844159191
96958778434292
88679745936159
15147372281932
89979277202479
96914986724315
75558198451122

Subtract row minima

We subtract the row minimum from each row:

7448232907676(-15)
545345361050(-42)
4322520481614(-45)
10595814518(-14)
697772570459(-20)
8176347157280(-15)
6444708734011(-11)

Subtract column minima

We subtract the column minimum from each column:

734802907676
535322361050
4222290481614
00365814518
687749570459
8076117157280
6344478734011
(-1)(-23)

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

734802907676  x
535322361050
4222290481614  x
00365814518  x
687749570459  x
8076117157280  x
6344478734011
x

Create additional zeros

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

734802907776
525221350049
4222290481714
00365814618
687749570559
8076117157290
6243468633010

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

734802907776  x
525221350049
4222290481714  x
00365814618  x
687749570559
8076117157290  x
6243468633010
xx

Create additional zeros

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

7348029108776
424211250039
4222290582714
003658241618
586739470549
8076117167390
523336763300

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

7348029108776  x
424211250039
4222290582714  x
003658241618  x
586739470549
8076117167390
523336763300
xxx

Create additional zeros

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

7348029219887
31310140039
4222290693825
003658352729
475628360549
696506067390
412225653300

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

7348029219887
31310140039
4222290693825  x
003658352729  x
475628360549
696506067390
412225653300
xxxx

Create additional zeros

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

5934015219887
1717000039
4222430835239
005058494143
334228220549
555104667390
27825513300

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

5934015219887
1717000039
4222430835239
005058494143  x
334228220549
555104667390
27825513300
xxxxx

Create additional zeros

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

5126015219887
99000039
3414430835239
005866574951
253428220549
474304667390
19025513300

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

5126015219887  x
99000039  x
3414430835239  x
005866574951  x
253428220549  x
474304667390  x
19025513300  x

The optimal assignment

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

5126015219887
99000039
3414430835239
005866574951
253428220549
474304667390
19025513300

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

89633844159191
96958778434292
88679745936159
15147372281932
89979277202479
96914986724315
75558198451122

The optimal value equals 230.