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:

6281698852486984196
21975645134775751353
36881579786728854
3947526065581179679
4240733234745632574
7476372258683534986
9995226061860479531
7775493151435162559
7567482462979908825
49653448465073198039

Subtract row minima

We subtract the row minimum from each row:

5776648301981933691(-5)
88443320346262040(-13)
32477535746324810(-4)
303843515649270580(-9)
3735682729695127069(-5)
6870311652622928920(-6)
9389165401254418925(-6)
7371089111031122155(-4)
0496775392272838118(-7)
3046152927315406120(-19)

Subtract column minima

We subtract the column minimum from each column:

577264670979933691
88043160246062040
32077375646124810
303443355639070580
3731681129594927069
686631052522728920
938516380252418925
736707311029122155
0456759391270838118
3042151327215206120
(-4)(-16)(-10)(-2)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

577264670979933691
88043160246062040
32077375646124810  x
303443355639070580  x
3731681129594927069
686631052522728920  x
938516380252418925
736707311029122155  x
0456759391270838118  x
3042151327215206120  x
xx

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:

557062650777913689
67841140225860038
32077377646124830
303443355839070600
352966929574725067
686631054522728940
918314360050398923
736707313029122355
0456759411270838318
3042151329215206320

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

557062650777913689
67841140225860038
32077377646124830  x
303443355839070600  x
352966929574725067
686631054522728940  x
918314360050398923  x
736707313029122355  x
0456759411270838318  x
3042151329215206320  x
xx

Create additional zeros

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

496456590171853683
0723580165254032
320773713646124890
303443356439070660
292360329514119061
6866310605227281000
918314366050399523
736707319029122955
0456759471270838918
3042151335215206920

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

496456590171853683
0723580165254032
320773713646124890  x
303443356439070660  x
292360329514119061
6866310605227281000  x
918314366050399523  x
736707319029122955  x
0456759471270838918
3042151335215206920  x
xxx

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:

496355580070843682
0713470155153031
330773714646124900
313443356539070670
292259229504018060
6966310615227281010
928314367050399623
746707320029123055
0446658471169828917
3142151336215207020

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

496355580070843682
0713470155153031
330773714646124900  x
313443356539070670  x
292259229504018060
6966310615227281010  x
928314367050399623
746707320029123055  x
0446658471169828917
3142151336215207020  x
xxxx

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:

496153560068823680
0693250154951029
350773716666124920
333443356741070690
292057029503816058
7166310635427281030
928112347048379621
766707322229123255
0426456471167808915
3342151338235207220

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

496153560068823680  x
0693250154951029  x
350773716666124920  x
333443356741070690  x
292057029503816058  x
7166310635427281030  x
928112347048379621  x
766707322229123255  x
0426456471167808915  x
3342151338235207220  x

The optimal assignment

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

496153560068823680
0693250154951029
350773716666124920
333443356741070690
292057029503816058
7166310635427281030
928112347048379621
766707322229123255
0426456471167808915
3342151338235207220

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

6281698852486984196
21975645134775751353
36881579786728854
3947526065581179679
4240733234745632574
7476372258683534986
9995226061860479531
7775493151435162559
7567482462979908825
49653448465073198039

The optimal value equals 123.