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:

23	2	17	45	59	27	45	10	63	35
65	42	88	66	80	9	30	3	51	47
79	61	75	41	5	88	3	86	33	52
16	95	83	98	11	57	48	39	93	74
66	47	62	95	70	98	87	68	57	68
24	71	86	39	53	47	97	75	75	23
84	87	97	15	24	88	46	12	68	55
63	29	15	88	41	44	69	48	22	3
28	83	21	37	31	76	17	56	81	7
97	48	77	25	70	27	53	2	37	42

Subtract row minima

We subtract the row minimum from each row:

21	0	15	43	57	25	43	8	61	33	(-2)
62	39	85	63	77	6	27	0	48	44	(-3)
76	58	72	38	2	85	0	83	30	49	(-3)
5	84	72	87	0	46	37	28	82	63	(-11)
19	0	15	48	23	51	40	21	10	21	(-47)
1	48	63	16	30	24	74	52	52	0	(-23)
72	75	85	3	12	76	34	0	56	43	(-12)
60	26	12	85	38	41	66	45	19	0	(-3)
21	76	14	30	24	69	10	49	74	0	(-7)
95	46	75	23	68	25	51	0	35	40	(-2)

Subtract column minima

We subtract the column minimum from each column:

20	0	3	40	57	19	43	8	51	33
61	39	73	60	77	0	27	0	38	44
75	58	60	35	2	79	0	83	20	49
4	84	60	84	0	40	37	28	72	63
18	0	3	45	23	45	40	21	0	21
0	48	51	13	30	18	74	52	42	0
71	75	73	0	12	70	34	0	46	43
59	26	0	82	38	35	66	45	9	0
20	76	2	27	24	63	10	49	64	0
94	46	63	20	68	19	51	0	25	40
(-1)		(-12)	(-3)		(-6)			(-10)

Cover all zeros with a minimum number of lines

There are 10 lines required to cover all zeros:

20	0	3	40	57	19	43	8	51	33	x
61	39	73	60	77	0	27	0	38	44	x
75	58	60	35	2	79	0	83	20	49	x
4	84	60	84	0	40	37	28	72	63	x
18	0	3	45	23	45	40	21	0	21	x
0	48	51	13	30	18	74	52	42	0	x
71	75	73	0	12	70	34	0	46	43	x
59	26	0	82	38	35	66	45	9	0	x
20	76	2	27	24	63	10	49	64	0	x
94	46	63	20	68	19	51	0	25	40	x

The optimal assignment

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

20	0	3	40	57	19	43	8	51	33
61	39	73	60	77	0	27	0	38	44
75	58	60	35	2	79	0	83	20	49
4	84	60	84	0	40	37	28	72	63
18	0	3	45	23	45	40	21	0	21
0	48	51	13	30	18	74	52	42	0
71	75	73	0	12	70	34	0	46	43
59	26	0	82	38	35	66	45	9	0
20	76	2	27	24	63	10	49	64	0
94	46	63	20	68	19	51	0	25	40

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

23	2	17	45	59	27	45	10	63	35
65	42	88	66	80	9	30	3	51	47
79	61	75	41	5	88	3	86	33	52
16	95	83	98	11	57	48	39	93	74
66	47	62	95	70	98	87	68	57	68
24	71	86	39	53	47	97	75	75	23
84	87	97	15	24	88	46	12	68	55
63	29	15	88	41	44	69	48	22	3
28	83	21	37	31	76	17	56	81	7
97	48	77	25	70	27	53	2	37	42

The optimal value equals 145.

23	2	17	45	59	27	45	10	63	35
65	42	88	66	80	9	30	3	51	47
79	61	75	41	5	88	3	86	33	52
16	95	83	98	11	57	48	39	93	74
66	47	62	95	70	98	87	68	57	68
24	71	86	39	53	47	97	75	75	23
84	87	97	15	24	88	46	12	68	55
63	29	15	88	41	44	69	48	22	3
28	83	21	37	31	76	17	56	81	7
97	48	77	25	70	27	53	2	37	42

20	0	3	40	57	19	43	8	51	33	x
61	39	73	60	77	0	27	0	38	44	x
75	58	60	35	2	79	0	83	20	49	x
4	84	60	84	0	40	37	28	72	63	x
18	0	3	45	23	45	40	21	0	21	x
0	48	51	13	30	18	74	52	42	0	x
71	75	73	0	12	70	34	0	46	43	x
59	26	0	82	38	35	66	45	9	0	x
20	76	2	27	24	63	10	49	64	0	x
94	46	63	20	68	19	51	0	25	40	x

20	0	3	40	57	19	43	8	51	33
61	39	73	60	77	0	27	0	38	44
75	58	60	35	2	79	0	83	20	49
4	84	60	84	0	40	37	28	72	63
18	0	3	45	23	45	40	21	0	21
0	48	51	13	30	18	74	52	42	0
71	75	73	0	12	70	34	0	46	43
59	26	0	82	38	35	66	45	9	0
20	76	2	27	24	63	10	49	64	0
94	46	63	20	68	19	51	0	25	40

23	2	17	45	59	27	45	10	63	35
65	42	88	66	80	9	30	3	51	47
79	61	75	41	5	88	3	86	33	52
16	95	83	98	11	57	48	39	93	74
66	47	62	95	70	98	87	68	57	68
24	71	86	39	53	47	97	75	75	23
84	87	97	15	24	88	46	12	68	55
63	29	15	88	41	44	69	48	22	3
28	83	21	37	31	76	17	56	81	7
97	48	77	25	70	27	53	2	37	42

23	2	17	45	59	27	45	10	63	35
65	42	88	66	80	9	30	3	51	47
79	61	75	41	5	88	3	86	33	52
16	95	83	98	11	57	48	39	93	74
66	47	62	95	70	98	87	68	57	68
24	71	86	39	53	47	97	75	75	23
84	87	97	15	24	88	46	12	68	55
63	29	15	88	41	44	69	48	22	3
28	83	21	37	31	76	17	56	81	7
97	48	77	25	70	27	53	2	37	42

20	0	3	40	57	19	43	8	51	33	x
61	39	73	60	77	0	27	0	38	44	x
75	58	60	35	2	79	0	83	20	49	x
4	84	60	84	0	40	37	28	72	63	x
18	0	3	45	23	45	40	21	0	21	x
0	48	51	13	30	18	74	52	42	0	x
71	75	73	0	12	70	34	0	46	43	x
59	26	0	82	38	35	66	45	9	0	x
20	76	2	27	24	63	10	49	64	0	x
94	46	63	20	68	19	51	0	25	40	x

20	0	3	40	57	19	43	8	51	33
61	39	73	60	77	0	27	0	38	44
75	58	60	35	2	79	0	83	20	49
4	84	60	84	0	40	37	28	72	63
18	0	3	45	23	45	40	21	0	21
0	48	51	13	30	18	74	52	42	0
71	75	73	0	12	70	34	0	46	43
59	26	0	82	38	35	66	45	9	0
20	76	2	27	24	63	10	49	64	0
94	46	63	20	68	19	51	0	25	40

23	2	17	45	59	27	45	10	63	35
65	42	88	66	80	9	30	3	51	47
79	61	75	41	5	88	3	86	33	52
16	95	83	98	11	57	48	39	93	74
66	47	62	95	70	98	87	68	57	68
24	71	86	39	53	47	97	75	75	23
84	87	97	15	24	88	46	12	68	55
63	29	15	88	41	44	69	48	22	3
28	83	21	37	31	76	17	56	81	7
97	48	77	25	70	27	53	2	37	42

23	2	17	45	59	27	45	10	63	35
65	42	88	66	80	9	30	3	51	47
79	61	75	41	5	88	3	86	33	52
16	95	83	98	11	57	48	39	93	74
66	47	62	95	70	98	87	68	57	68
24	71	86	39	53	47	97	75	75	23
84	87	97	15	24	88	46	12	68	55
63	29	15	88	41	44	69	48	22	3
28	83	21	37	31	76	17	56	81	7
97	48	77	25	70	27	53	2	37	42

20	0	3	40	57	19	43	8	51	33	x
61	39	73	60	77	0	27	0	38	44	x
75	58	60	35	2	79	0	83	20	49	x
4	84	60	84	0	40	37	28	72	63	x
18	0	3	45	23	45	40	21	0	21	x
0	48	51	13	30	18	74	52	42	0	x
71	75	73	0	12	70	34	0	46	43	x
59	26	0	82	38	35	66	45	9	0	x
20	76	2	27	24	63	10	49	64	0	x
94	46	63	20	68	19	51	0	25	40	x

20	0	3	40	57	19	43	8	51	33
61	39	73	60	77	0	27	0	38	44
75	58	60	35	2	79	0	83	20	49
4	84	60	84	0	40	37	28	72	63
18	0	3	45	23	45	40	21	0	21
0	48	51	13	30	18	74	52	42	0
71	75	73	0	12	70	34	0	46	43
59	26	0	82	38	35	66	45	9	0
20	76	2	27	24	63	10	49	64	0
94	46	63	20	68	19	51	0	25	40

23	2	17	45	59	27	45	10	63	35
65	42	88	66	80	9	30	3	51	47
79	61	75	41	5	88	3	86	33	52
16	95	83	98	11	57	48	39	93	74
66	47	62	95	70	98	87	68	57	68
24	71	86	39	53	47	97	75	75	23
84	87	97	15	24	88	46	12	68	55
63	29	15	88	41	44	69	48	22	3
28	83	21	37	31	76	17	56	81	7
97	48	77	25	70	27	53	2	37	42