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:

53583118936492
258646276592
3275982653128
5134986525182
57756794853492
10633258356562
9593927934624

Subtract row minima

We subtract the row minimum from each row:

3540130754674(-18)
208141221087(-5)
3073960632926(-2)
4932966304980(-2)
2341336051058(-34)
0532248255552(-10)
8603018843715(-9)

Subtract column minima

We subtract the column minimum from each column:

354000754659
208128221072
3073830632911
4932836304965
2341206051043
053948255537
860171884370
(-13)(-15)

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

354000754659  x
208128221072
3073830632911  x
4932836304965  x
2341206051043
053948255537  x
860171884370  x
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:

354000754759
198027210071
3073830633011
4932836305065
2240195950042
053948255637
860171884380

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

354000754759  x
198027210071
3073830633011  x
4932836305065
2240195950042
053948255637  x
860171884380  x
xx

Create additional zeros

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

354000946659
061820052
3073830824911
3013644405046
32104050023
053948447537
8601718103570

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

354000946659
061820052
3073830824911
3013644405046
32104050023
053948447537
8601718103570  x
xxxxx

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:

352900946648
050820041
306283082490
302644405035
31004050012
042948447526
9702829114680

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

352900946648  x
050820041  x
306283082490  x
302644405035  x
31004050012  x
042948447526  x
9702829114680  x

The optimal assignment

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

352900946648
050820041
306283082490
302644405035
31004050012
042948447526
9702829114680

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

53583118936492
258646276592
3275982653128
5134986525182
57756794853492
10633258356562
9593927934624

The optimal value equals 139.