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:

4583502113754807897
40373752368433382332
5789752313793441627
50157688102093389449
6474406095081328828
21781585959890558447
33347582154118237361
51864251294753919724
1078868654875563177
57999717538482953661

Subtract row minima

We subtract the row minimum from each row:

4482492003653797796(-1)
171414291361101509(-23)
5486722010760411324(-3)
405667801083288439(-10)
5565315104172237919(-9)
663070808375406932(-15)
18196067026385846(-15)
276218275232967730(-24)
573818104370512672(-5)
4082800366765781944(-17)

Subtract column minima

We subtract the column minimum from each column:

3977492002653717796
1291429135110709
4981722010660331324
35066780083208439
5060315103172157919
158070807375326932
13146067016305846
225718275132959730
068818103370432672
3577800365765701944
(-5)(-5)(-10)(-8)

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

3977492002653717796
1291429135110709  x
4981722010660331324  x
35066780083208439  x
5060315103172157919
158070807375326932  x
13146067016305846  x
225718275132959730  x
068818103370432672  x
3577800365765701944  x
x

Create additional zeros

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

246234501138566281
1291429285110709
4981722025660331324
350667815083208439
35451636016570644
158070957375326932
131460671516305846
2257182720132959730
0688181153370432672
3577800515765701944

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

246234501138566281
1291429285110709  x
4981722025660331324  x
350667815083208439  x
35451636016570644
158070957375326932  x
131460671516305846
2257182720132959730  x
0688181153370432672  x
3577800515765701944  x
xx

Create additional zeros

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

21593120835565978
12914293151101009
4981722028660361324
350667818083238439
32421333013540611
158070987375356932
101157641513005543
2257182723132962730
0688181183370462672
3577800545765731944

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

21593120835565978
12914293151101009  x
4981722028660361324
350667818083238439  x
32421333013540611
158070987375356932  x
101157641513005543
2257182723132962730  x
0688181183370462672  x
3577800545765731944  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:

20583010735565877
12914293251111109
4880711928650361223
350667819084248439
31411232012540600
158070997376366932
91056631512005442
2257182724133063730
0688181193371472672
3577800555766741944

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

20583010735565877
12914293251111109  x
4880711928650361223
350667819084248439  x
31411232012540600
158070997376366932  x
91056631512005442
2257182724133063730
0688181193371472672  x
3577800555766741944  x
xxxx

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:

19572900635565777
129142933511212010
4779701828640361123
350667820085258440
30401131011540590
1580701007377376933
8955621511005342
2156172624123063720
0688181203372482673
3577800565767751945

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

19572900635565777
129142933511212010  x
4779701828640361123
350667820085258440  x
30401131011540590
1580701007377376933  x
8955621511005342
2156172624123063720
0688181203372482673  x
3577800565767751945
xxxxx

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:

13512300035565177
129143539511818016
417364182858036523
350668426091318446
243453105540530
1580761067383436939
234962155004742
155011262463063660
0688187263378542679
2971740565167751345

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

13512300035565177  x
129143539511818016  x
417364182858036523  x
350668426091318446  x
243453105540530  x
1580761067383436939  x
234962155004742  x
155011262463063660  x
0688187263378542679  x
2971740565167751345  x

The optimal assignment

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

13512300035565177
129143539511818016
417364182858036523
350668426091318446
243453105540530
1580761067383436939
234962155004742
155011262463063660
0688187263378542679
2971740565167751345

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

4583502113754807897
40373752368433382332
5789752313793441627
50157688102093389449
6474406095081328828
21781585959890558447
33347582154118237361
51864251294753919724
1078868654875563177
57999717538482953661

The optimal value equals 176.