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:

4	86	92	70	14	67	3	18
67	29	89	51	73	51	28	25
84	93	20	87	94	80	36	39
9	15	36	68	46	46	37	19
75	11	66	34	73	53	97	65
61	23	35	31	4	38	76	35
55	44	11	94	85	7	47	60
94	93	41	59	75	47	66	95

Subtract row minima

We subtract the row minimum from each row:

1	83	89	67	11	64	0	15	(-3)
42	4	64	26	48	26	3	0	(-25)
64	73	0	67	74	60	16	19	(-20)
0	6	27	59	37	37	28	10	(-9)
64	0	55	23	62	42	86	54	(-11)
57	19	31	27	0	34	72	31	(-4)
48	37	4	87	78	0	40	53	(-7)
53	52	0	18	34	6	25	54	(-41)

Subtract column minima

We subtract the column minimum from each column:

1	83	89	49	11	64	0	15
42	4	64	8	48	26	3	0
64	73	0	49	74	60	16	19
0	6	27	41	37	37	28	10
64	0	55	5	62	42	86	54
57	19	31	9	0	34	72	31
48	37	4	69	78	0	40	53
53	52	0	0	34	6	25	54
			(-18)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

1	83	89	49	11	64	0	15	x
42	4	64	8	48	26	3	0	x
64	73	0	49	74	60	16	19	x
0	6	27	41	37	37	28	10	x
64	0	55	5	62	42	86	54	x
57	19	31	9	0	34	72	31	x
48	37	4	69	78	0	40	53	x
53	52	0	0	34	6	25	54	x

The optimal assignment

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

1	83	89	49	11	64	0	15
42	4	64	8	48	26	3	0
64	73	0	49	74	60	16	19
0	6	27	41	37	37	28	10
64	0	55	5	62	42	86	54
57	19	31	9	0	34	72	31
48	37	4	69	78	0	40	53
53	52	0	0	34	6	25	54

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

4	86	92	70	14	67	3	18
67	29	89	51	73	51	28	25
84	93	20	87	94	80	36	39
9	15	36	68	46	46	37	19
75	11	66	34	73	53	97	65
61	23	35	31	4	38	76	35
55	44	11	94	85	7	47	60
94	93	41	59	75	47	66	95

The optimal value equals 138.

4	86	92	70	14	67	3	18
67	29	89	51	73	51	28	25
84	93	20	87	94	80	36	39
9	15	36	68	46	46	37	19
75	11	66	34	73	53	97	65
61	23	35	31	4	38	76	35
55	44	11	94	85	7	47	60
94	93	41	59	75	47	66	95

1	83	89	49	11	64	0	15	x
42	4	64	8	48	26	3	0	x
64	73	0	49	74	60	16	19	x
0	6	27	41	37	37	28	10	x
64	0	55	5	62	42	86	54	x
57	19	31	9	0	34	72	31	x
48	37	4	69	78	0	40	53	x
53	52	0	0	34	6	25	54	x

1	83	89	49	11	64	0	15
42	4	64	8	48	26	3	0
64	73	0	49	74	60	16	19
0	6	27	41	37	37	28	10
64	0	55	5	62	42	86	54
57	19	31	9	0	34	72	31
48	37	4	69	78	0	40	53
53	52	0	0	34	6	25	54

4	86	92	70	14	67	3	18
67	29	89	51	73	51	28	25
84	93	20	87	94	80	36	39
9	15	36	68	46	46	37	19
75	11	66	34	73	53	97	65
61	23	35	31	4	38	76	35
55	44	11	94	85	7	47	60
94	93	41	59	75	47	66	95

4	86	92	70	14	67	3	18
67	29	89	51	73	51	28	25
84	93	20	87	94	80	36	39
9	15	36	68	46	46	37	19
75	11	66	34	73	53	97	65
61	23	35	31	4	38	76	35
55	44	11	94	85	7	47	60
94	93	41	59	75	47	66	95

1	83	89	49	11	64	0	15	x
42	4	64	8	48	26	3	0	x
64	73	0	49	74	60	16	19	x
0	6	27	41	37	37	28	10	x
64	0	55	5	62	42	86	54	x
57	19	31	9	0	34	72	31	x
48	37	4	69	78	0	40	53	x
53	52	0	0	34	6	25	54	x

1	83	89	49	11	64	0	15
42	4	64	8	48	26	3	0
64	73	0	49	74	60	16	19
0	6	27	41	37	37	28	10
64	0	55	5	62	42	86	54
57	19	31	9	0	34	72	31
48	37	4	69	78	0	40	53
53	52	0	0	34	6	25	54

4	86	92	70	14	67	3	18
67	29	89	51	73	51	28	25
84	93	20	87	94	80	36	39
9	15	36	68	46	46	37	19
75	11	66	34	73	53	97	65
61	23	35	31	4	38	76	35
55	44	11	94	85	7	47	60
94	93	41	59	75	47	66	95

4	86	92	70	14	67	3	18
67	29	89	51	73	51	28	25
84	93	20	87	94	80	36	39
9	15	36	68	46	46	37	19
75	11	66	34	73	53	97	65
61	23	35	31	4	38	76	35
55	44	11	94	85	7	47	60
94	93	41	59	75	47	66	95

1	83	89	49	11	64	0	15	x
42	4	64	8	48	26	3	0	x
64	73	0	49	74	60	16	19	x
0	6	27	41	37	37	28	10	x
64	0	55	5	62	42	86	54	x
57	19	31	9	0	34	72	31	x
48	37	4	69	78	0	40	53	x
53	52	0	0	34	6	25	54	x

1	83	89	49	11	64	0	15
42	4	64	8	48	26	3	0
64	73	0	49	74	60	16	19
0	6	27	41	37	37	28	10
64	0	55	5	62	42	86	54
57	19	31	9	0	34	72	31
48	37	4	69	78	0	40	53
53	52	0	0	34	6	25	54

4	86	92	70	14	67	3	18
67	29	89	51	73	51	28	25
84	93	20	87	94	80	36	39
9	15	36	68	46	46	37	19
75	11	66	34	73	53	97	65
61	23	35	31	4	38	76	35
55	44	11	94	85	7	47	60
94	93	41	59	75	47	66	95