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:

9	53	47	70	70	93
24	51	58	63	25	98
31	80	1	59	24	41
38	43	67	34	95	75
18	7	49	98	21	59
82	36	21	82	60	73

Subtract row minima

We subtract the row minimum from each row:

0	44	38	61	61	84	(-9)
0	27	34	39	1	74	(-24)
30	79	0	58	23	40	(-1)
4	9	33	0	61	41	(-34)
11	0	42	91	14	52	(-7)
61	15	0	61	39	52	(-21)

Subtract column minima

We subtract the column minimum from each column:

0	44	38	61	60	44
0	27	34	39	0	34
30	79	0	58	22	0
4	9	33	0	60	1
11	0	42	91	13	12
61	15	0	61	38	12
				(-1)	(-40)

Cover all zeros with a minimum number of lines

There are 6 lines required to cover all zeros:

0	44	38	61	60	44	x
0	27	34	39	0	34	x
30	79	0	58	22	0	x
4	9	33	0	60	1	x
11	0	42	91	13	12	x
61	15	0	61	38	12	x

The optimal assignment

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

0	44	38	61	60	44
0	27	34	39	0	34
30	79	0	58	22	0
4	9	33	0	60	1
11	0	42	91	13	12
61	15	0	61	38	12

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

9	53	47	70	70	93
24	51	58	63	25	98
31	80	1	59	24	41
38	43	67	34	95	75
18	7	49	98	21	59
82	36	21	82	60	73

The optimal value equals 137.

9	53	47	70	70	93
24	51	58	63	25	98
31	80	1	59	24	41
38	43	67	34	95	75
18	7	49	98	21	59
82	36	21	82	60	73

0	44	38	61	60	44	x
0	27	34	39	0	34	x
30	79	0	58	22	0	x
4	9	33	0	60	1	x
11	0	42	91	13	12	x
61	15	0	61	38	12	x

0	44	38	61	60	44
0	27	34	39	0	34
30	79	0	58	22	0
4	9	33	0	60	1
11	0	42	91	13	12
61	15	0	61	38	12

9	53	47	70	70	93
24	51	58	63	25	98
31	80	1	59	24	41
38	43	67	34	95	75
18	7	49	98	21	59
82	36	21	82	60	73

9	53	47	70	70	93
24	51	58	63	25	98
31	80	1	59	24	41
38	43	67	34	95	75
18	7	49	98	21	59
82	36	21	82	60	73

0	44	38	61	60	44	x
0	27	34	39	0	34	x
30	79	0	58	22	0	x
4	9	33	0	60	1	x
11	0	42	91	13	12	x
61	15	0	61	38	12	x

0	44	38	61	60	44
0	27	34	39	0	34
30	79	0	58	22	0
4	9	33	0	60	1
11	0	42	91	13	12
61	15	0	61	38	12

9	53	47	70	70	93
24	51	58	63	25	98
31	80	1	59	24	41
38	43	67	34	95	75
18	7	49	98	21	59
82	36	21	82	60	73

9	53	47	70	70	93
24	51	58	63	25	98
31	80	1	59	24	41
38	43	67	34	95	75
18	7	49	98	21	59
82	36	21	82	60	73

0	44	38	61	60	44	x
0	27	34	39	0	34	x
30	79	0	58	22	0	x
4	9	33	0	60	1	x
11	0	42	91	13	12	x
61	15	0	61	38	12	x

0	44	38	61	60	44
0	27	34	39	0	34
30	79	0	58	22	0
4	9	33	0	60	1
11	0	42	91	13	12
61	15	0	61	38	12

9	53	47	70	70	93
24	51	58	63	25	98
31	80	1	59	24	41
38	43	67	34	95	75
18	7	49	98	21	59
82	36	21	82	60	73