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:

73887625286126606575
15125486891227364780
23636511765952526559
853934543644258591
105620202622263940
46888724735985897521
7670927444156772879
8486467317636784227
3520161271396667680
59915079683827313594

Subtract row minima

We subtract the row minimum from each row:

48635103361354050(-25)
30427477015243568(-12)
1252540654841415448(-11)
813530139600218187(-4)
50115152117213435(-5)
256766352386468540(-21)
7266887003752732475(-4)
7605659236828703419(-8)
2813950689596973(-7)
32642352411104867(-27)

Subtract column minima

We subtract the column minimum from each column:

45635003361313250
00417477015202768
952530654841374648
783529139600177387
20015152117172635
226765352386464460
6966877003752691675
7305559236828662619
2513850689556173
29642252411100067
(-3)(-1)(-4)(-8)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

45635003361313250
00417477015202768  x
952530654841374648
783529139600177387  x
20015152117172635  x
226765352386464460  x
6966877003752691675
7305559236828662619  x
2513850689556173
29642252411100067  x
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:

44624903350303149
00417578015202768
851520654740364547
783529240600177387
20016162117172635
226765453386464460
6865867003651681574
7305560246828662619
2412750588546072
29642253421100067

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

44624903350303149
00417578015202768  x
851520654740364547
783529240600177387
20016162117172635  x
226765453386464460  x
6865867003651681574
7305560246828662619  x
2412750588546072
29642253421100067  x
xxx

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:

39574403300252644
00418083020202768
346470654240314042
733024240550126882
20021212122172635
226765958386964460
6360817003151631069
7305565296833662619
197250088495567
29642258471150067

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

39574403300252644
00418083020202768  x
346470654240314042
733024240550126882
20021212122172635  x
226765958386964460  x
6360817003151631069  x
7305565296833662619  x
197250088495567  x
29642258471150067  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:

36544100270222341
00418383023202768
043440623940283739
70272123752096579
20024212125172635
2267651258387264460
6360817303154631069
7305568296836662619
197280091495567
29642261471180067

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

36544100270222341
00418383023202768
043440623940283739
70272123752096579
20024212125172635  x
2267651258387264460  x
6360817303154631069
7305568296836662619
197280091495567
29642261471180067  x
xxxxxx

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:

36543900270202139
00398383023182566
043420623940263537
70271923752076377
42026232327172635
2469651460407464460
636079730315461867
7305368296836642417
197080091475365
316622634913100067

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

36543900270202139
00398383023182566
043420623940263537
70271923752076377
42026232327172635
2469651460407464460  x
636079730315461867
7305368296836642417
197080091475365
316622634913100067  x
xxxxxxx

Create additional zeros

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

36543900270131432
00398383023111859
043420623940192830
70271923752005670
42026232327101928
3176722167478164460
636079730315454160
7305368296836571710
197080091404658
387329705620170067

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

36543900270131432  x
00398383023111859  x
043420623940192830  x
70271923752005670  x
42026232327101928  x
3176722167478164460  x
636079730315454160  x
7305368296836571710  x
197080091404658  x
387329705620170067  x

The optimal assignment

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

36543900270131432
00398383023111859
043420623940192830
70271923752005670
42026232327101928
3176722167478164460
636079730315454160
7305368296836571710
197080091404658
387329705620170067

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

73887625286126606575
15125486891227364780
23636511765952526559
853934543644258591
105620202622263940
46888724735985897521
7670927444156772879
8486467317636784227
3520161271396667680
59915079683827313594

The optimal value equals 164.