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:

9795637682443211345
6111221510355969116
67569315617642618544
9583786158559051248
2966561437175538020
2468971915146147659
5052582184722853398
6631445244532304745
8752435368915974913
83554255268270693729

Subtract row minima

We subtract the row minimum from each row:

9492607379410181042(-3)
56617105300918611(-5)
5241780466127467029(-15)
907873565350850743(-5)
0946359416973517818(-2)
15598810655238560(-9)
4749551881692550095(-3)
6227041204128264341(-4)
820193031841092448(-5)
572916290564443113(-26)

Subtract column minima

We subtract the column minimum from each column:

9492607379360181042
56617105250918611
5241780465627467029
907873565345850743
0946359416473517818
15598810605238560
4749551881642550095
6227041203628264341
820193031791092448
572916290514443113
(-5)

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

9492607379360181042
56617105250918611
5241780465627467029  x
907873565345850743  x
0946359416473517818  x
15598810605238560  x
4749551881642550095  x
6227041203628264341  x
820193031791092448  x
572916290514443113  x
x

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:

898755687431013537
511125020086816
5241780465632467029
907873565345900743
0946359416478517818
15598810605738560
4749551881643050095
6227041203633264341
820193031791592448
572916290514943113

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

898755687431013537
511125020086816
5241780465632467029  x
907873565345900743  x
0946359416478517818  x
15598810605738560  x
4749551881643050095  x
6227041203633264341  x
820193031791592448  x
572916290514943113
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:

888654677430012436
500114019085805
5241780475633467029
907873565445910743
0946359426479517818
15598810705838560
4749551882643150095
6227041213634264341
820193032791692448
562815280504942102

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

888654677430012436
500114019085805
5241780475633467029  x
907873565445910743  x
0946359426479517818  x
15598810705838560  x
4749551882643150095  x
6227041213634264341  x
820193032791692448
562815280504942102
xxx

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:

868652657428010234
48092017083783
5243780495635467029
908073565645930743
0966359446481517818
15618810906038560
4751551884643350095
6229041233636264341
800172832771690426
54281326048494080

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

868652657428010234  x
48092017083783  x
5243780495635467029  x
908073565645930743  x
0966359446481517818  x
15618810906038560  x
4751551884643350095  x
6229041233636264341  x
800172832771690426  x
54281326048494080  x

The optimal assignment

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

868652657428010234
48092017083783
5243780495635467029
908073565645930743
0966359446481517818
15618810906038560
4751551884643350095
6229041233636264341
800172832771690426
54281326048494080

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

9795637682443211345
6111221510355969116
67569315617642618544
9583786158559051248
2966561437175538020
2468971915146147659
5052582184722853398
6631445244532304745
8752435368915974913
83554255268270693729

The optimal value equals 90.