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:

20	61	72	24	50	22	81	63	77	20
82	44	15	11	29	55	45	94	9	89
28	87	56	36	89	7	70	32	70	32
90	37	78	28	84	18	2	92	50	1
29	96	5	29	2	7	97	58	81	97
84	71	32	34	64	29	57	34	15	62
76	43	23	91	1	79	12	47	78	12
37	88	68	71	8	1	2	35	77	36
92	46	37	84	72	21	85	55	33	14
30	91	11	8	41	27	55	84	92	58

Subtract row minima

We subtract the row minimum from each row:

0	41	52	4	30	2	61	43	57	0	(-20)
73	35	6	2	20	46	36	85	0	80	(-9)
21	80	49	29	82	0	63	25	63	25	(-7)
89	36	77	27	83	17	1	91	49	0	(-1)
27	94	3	27	0	5	95	56	79	95	(-2)
69	56	17	19	49	14	42	19	0	47	(-15)
75	42	22	90	0	78	11	46	77	11	(-1)
36	87	67	70	7	0	1	34	76	35	(-1)
78	32	23	70	58	7	71	41	19	0	(-14)
22	83	3	0	33	19	47	76	84	50	(-8)

Subtract column minima

We subtract the column minimum from each column:

0	9	49	4	30	2	60	24	57	0
73	3	3	2	20	46	35	66	0	80
21	48	46	29	82	0	62	6	63	25
89	4	74	27	83	17	0	72	49	0
27	62	0	27	0	5	94	37	79	95
69	24	14	19	49	14	41	0	0	47
75	10	19	90	0	78	10	27	77	11
36	55	64	70	7	0	0	15	76	35
78	0	20	70	58	7	70	22	19	0
22	51	0	0	33	19	46	57	84	50
	(-32)	(-3)				(-1)	(-19)

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

0	9	49	4	30	2	60	24	57	0	x
73	3	3	2	20	46	35	66	0	80	x
21	48	46	29	82	0	62	6	63	25	x
89	4	74	27	83	17	0	72	49	0	x
27	62	0	27	0	5	94	37	79	95	x
69	24	14	19	49	14	41	0	0	47	x
75	10	19	90	0	78	10	27	77	11	x
36	55	64	70	7	0	0	15	76	35	x
78	0	20	70	58	7	70	22	19	0	x
22	51	0	0	33	19	46	57	84	50	x

The optimal assignment

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

0	9	49	4	30	2	60	24	57	0
73	3	3	2	20	46	35	66	0	80
21	48	46	29	82	0	62	6	63	25
89	4	74	27	83	17	0	72	49	0
27	62	0	27	0	5	94	37	79	95
69	24	14	19	49	14	41	0	0	47
75	10	19	90	0	78	10	27	77	11
36	55	64	70	7	0	0	15	76	35
78	0	20	70	58	7	70	22	19	0
22	51	0	0	33	19	46	57	84	50

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

20	61	72	24	50	22	81	63	77	20
82	44	15	11	29	55	45	94	9	89
28	87	56	36	89	7	70	32	70	32
90	37	78	28	84	18	2	92	50	1
29	96	5	29	2	7	97	58	81	97
84	71	32	34	64	29	57	34	15	62
76	43	23	91	1	79	12	47	78	12
37	88	68	71	8	1	2	35	77	36
92	46	37	84	72	21	85	55	33	14
30	91	11	8	41	27	55	84	92	58

The optimal value equals 133.

20	61	72	24	50	22	81	63	77	20
82	44	15	11	29	55	45	94	9	89
28	87	56	36	89	7	70	32	70	32
90	37	78	28	84	18	2	92	50	1
29	96	5	29	2	7	97	58	81	97
84	71	32	34	64	29	57	34	15	62
76	43	23	91	1	79	12	47	78	12
37	88	68	71	8	1	2	35	77	36
92	46	37	84	72	21	85	55	33	14
30	91	11	8	41	27	55	84	92	58

0	9	49	4	30	2	60	24	57	0	x
73	3	3	2	20	46	35	66	0	80	x
21	48	46	29	82	0	62	6	63	25	x
89	4	74	27	83	17	0	72	49	0	x
27	62	0	27	0	5	94	37	79	95	x
69	24	14	19	49	14	41	0	0	47	x
75	10	19	90	0	78	10	27	77	11	x
36	55	64	70	7	0	0	15	76	35	x
78	0	20	70	58	7	70	22	19	0	x
22	51	0	0	33	19	46	57	84	50	x

0	9	49	4	30	2	60	24	57	0
73	3	3	2	20	46	35	66	0	80
21	48	46	29	82	0	62	6	63	25
89	4	74	27	83	17	0	72	49	0
27	62	0	27	0	5	94	37	79	95
69	24	14	19	49	14	41	0	0	47
75	10	19	90	0	78	10	27	77	11
36	55	64	70	7	0	0	15	76	35
78	0	20	70	58	7	70	22	19	0
22	51	0	0	33	19	46	57	84	50

20	61	72	24	50	22	81	63	77	20
82	44	15	11	29	55	45	94	9	89
28	87	56	36	89	7	70	32	70	32
90	37	78	28	84	18	2	92	50	1
29	96	5	29	2	7	97	58	81	97
84	71	32	34	64	29	57	34	15	62
76	43	23	91	1	79	12	47	78	12
37	88	68	71	8	1	2	35	77	36
92	46	37	84	72	21	85	55	33	14
30	91	11	8	41	27	55	84	92	58

20	61	72	24	50	22	81	63	77	20
82	44	15	11	29	55	45	94	9	89
28	87	56	36	89	7	70	32	70	32
90	37	78	28	84	18	2	92	50	1
29	96	5	29	2	7	97	58	81	97
84	71	32	34	64	29	57	34	15	62
76	43	23	91	1	79	12	47	78	12
37	88	68	71	8	1	2	35	77	36
92	46	37	84	72	21	85	55	33	14
30	91	11	8	41	27	55	84	92	58

0	9	49	4	30	2	60	24	57	0	x
73	3	3	2	20	46	35	66	0	80	x
21	48	46	29	82	0	62	6	63	25	x
89	4	74	27	83	17	0	72	49	0	x
27	62	0	27	0	5	94	37	79	95	x
69	24	14	19	49	14	41	0	0	47	x
75	10	19	90	0	78	10	27	77	11	x
36	55	64	70	7	0	0	15	76	35	x
78	0	20	70	58	7	70	22	19	0	x
22	51	0	0	33	19	46	57	84	50	x

0	9	49	4	30	2	60	24	57	0
73	3	3	2	20	46	35	66	0	80
21	48	46	29	82	0	62	6	63	25
89	4	74	27	83	17	0	72	49	0
27	62	0	27	0	5	94	37	79	95
69	24	14	19	49	14	41	0	0	47
75	10	19	90	0	78	10	27	77	11
36	55	64	70	7	0	0	15	76	35
78	0	20	70	58	7	70	22	19	0
22	51	0	0	33	19	46	57	84	50

20	61	72	24	50	22	81	63	77	20
82	44	15	11	29	55	45	94	9	89
28	87	56	36	89	7	70	32	70	32
90	37	78	28	84	18	2	92	50	1
29	96	5	29	2	7	97	58	81	97
84	71	32	34	64	29	57	34	15	62
76	43	23	91	1	79	12	47	78	12
37	88	68	71	8	1	2	35	77	36
92	46	37	84	72	21	85	55	33	14
30	91	11	8	41	27	55	84	92	58

20	61	72	24	50	22	81	63	77	20
82	44	15	11	29	55	45	94	9	89
28	87	56	36	89	7	70	32	70	32
90	37	78	28	84	18	2	92	50	1
29	96	5	29	2	7	97	58	81	97
84	71	32	34	64	29	57	34	15	62
76	43	23	91	1	79	12	47	78	12
37	88	68	71	8	1	2	35	77	36
92	46	37	84	72	21	85	55	33	14
30	91	11	8	41	27	55	84	92	58

0	9	49	4	30	2	60	24	57	0	x
73	3	3	2	20	46	35	66	0	80	x
21	48	46	29	82	0	62	6	63	25	x
89	4	74	27	83	17	0	72	49	0	x
27	62	0	27	0	5	94	37	79	95	x
69	24	14	19	49	14	41	0	0	47	x
75	10	19	90	0	78	10	27	77	11	x
36	55	64	70	7	0	0	15	76	35	x
78	0	20	70	58	7	70	22	19	0	x
22	51	0	0	33	19	46	57	84	50	x

0	9	49	4	30	2	60	24	57	0
73	3	3	2	20	46	35	66	0	80
21	48	46	29	82	0	62	6	63	25
89	4	74	27	83	17	0	72	49	0
27	62	0	27	0	5	94	37	79	95
69	24	14	19	49	14	41	0	0	47
75	10	19	90	0	78	10	27	77	11
36	55	64	70	7	0	0	15	76	35
78	0	20	70	58	7	70	22	19	0
22	51	0	0	33	19	46	57	84	50

20	61	72	24	50	22	81	63	77	20
82	44	15	11	29	55	45	94	9	89
28	87	56	36	89	7	70	32	70	32
90	37	78	28	84	18	2	92	50	1
29	96	5	29	2	7	97	58	81	97
84	71	32	34	64	29	57	34	15	62
76	43	23	91	1	79	12	47	78	12
37	88	68	71	8	1	2	35	77	36
92	46	37	84	72	21	85	55	33	14
30	91	11	8	41	27	55	84	92	58