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:

1189246731924294858
1516443845585868361
91606349677169169622
8470956965938768890
304533385411434051
522998816171057148
10378353597543191375
7990274432371649687
7879415641721269589
44199319863442418215

Subtract row minima

We subtract the row minimum from each row:

785206327880254454(-4)
1112403405181827957(-4)
754447335155530806(-16)
7864890905332708284(-6)
26049294507393647(-4)
01794831112506643(-5)
02773434965339365(-10)
7687244129068619384(-3)
080878571014198882(-7)
29478471192726670(-15)

Subtract column minima

We subtract the column minimum from each column:

78506327880254154
1112203405181827657
754427335155530776
7864690905332707984
26029294507393347
01774831112506343
02753434965339065
768744129068619084
080678571014198582
29458471192726640
(-20)(-3)

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

78506327880254154  x
1112203405181827657  x
754427335155530776
7864690905332707984  x
26029294507393347  x
01774831112506343
02753434965339065  x
768744129068619084  x
080678571014198582
29458471192726640  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:

128506327880304154
1612203405181877657
753922284650480721
8364690905332757984
31029294507443347
012697867005838
527534349653314065
818744129068669084
0756235259198077
34458471192731640

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

128506327880304154  x
1612203405181877657  x
753922284650480721  x
8364690905332757984  x
31029294507443347  x
012697867005838  x
527534349653314065  x
818744129068669084  x
0756235259198077  x
34458471192731640  x

The optimal assignment

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

128506327880304154
1612203405181877657
753922284650480721
8364690905332757984
31029294507443347
012697867005838
527534349653314065
818744129068669084
0756235259198077
34458471192731640

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

1189246731924294858
1516443845585868361
91606349677169169622
8470956965938768890
304533385411434051
522998816171057148
10378353597543191375
7990274432371649687
7879415641721269589
44199319863442418215

The optimal value equals 102.