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:

5655716855536659
362153245763607799
966539682928883030
17878544799216173
61832388606772923
92303795263946513
3238889994128422
457572438996967
4096818507118440

Subtract row minima

We subtract the row minimum from each row:

5325413825206356(-3)
1503233642395678(-21)
68371140106022(-28)
9070463991135365(-8)
55771782540712317(-6)
8321280435485564(-9)
243008118647614(-8)
053168398592923(-4)
3692414466714036(-4)

Subtract column minima

We subtract the column minimum from each column:

5325413815206354
1503233542395676
68371140006020
9070463891135363
55771782530712315
8321280425485562
243008108647612
053168388592921
3692414456714034
(-1)(-2)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

5325413815206354  x
1503233542395676
68371140006020  x
9070463891135363
55771782530712315  x
8321280425485562  x
243008108647612  x
053168388592921  x
3692414456714034  x
x

Create additional zeros

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

5355413815206354
1202903239365373
68401140006020
6067433588105060
55801782530712315
8324280425485562
243308108647612
056168388592921
3695414456714034

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

5355413815206354  x
1202903239365373
68401140006020  x
6067433588105060
55801782530712315  x
8324280425485562
243308108647612  x
056168388592921  x
3695414456714034  x
xx

Create additional zeros

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

5375415815206354
1002703037345171
68421142006020
406543338684858
55821784530712315
8124260405283540
243508308647612
058170388592921
3697416456714034

Cover all zeros with a minimum number of lines

There are 9 lines required to cover all zeros:

5375415815206354  x
1002703037345171  x
68421142006020  x
406543338684858  x
55821784530712315  x
8124260405283540  x
243508308647612  x
058170388592921  x
3697416456714034  x

The optimal assignment

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

5375415815206354
1002703037345171
68421142006020
406543338684858
55821784530712315
8124260405283540
243508308647612
058170388592921
3697416456714034

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

5655716855536659
362153245763607799
966539682928883030
17878544799216173
61832388606772923
92303795263946513
3238889994128422
457572438996967
4096818507118440

The optimal value equals 99.