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:

36	67	35	4	93	72	81
17	10	49	85	16	53	34
60	60	78	49	10	46	88
48	91	8	22	86	18	87
23	81	93	34	76	90	63
58	35	51	53	97	18	56
92	20	37	30	61	79	8

Subtract row minima

We subtract the row minimum from each row:

32	63	31	0	89	68	77	(-4)
7	0	39	75	6	43	24	(-10)
50	50	68	39	0	36	78	(-10)
40	83	0	14	78	10	79	(-8)
0	58	70	11	53	67	40	(-23)
40	17	33	35	79	0	38	(-18)
84	12	29	22	53	71	0	(-8)

Subtract column minima

Because each column contains a zero, subtracting column minima has no effect.

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

32	63	31	0	89	68	77	x
7	0	39	75	6	43	24	x
50	50	68	39	0	36	78	x
40	83	0	14	78	10	79	x
0	58	70	11	53	67	40	x
40	17	33	35	79	0	38	x
84	12	29	22	53	71	0	x

The optimal assignment

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

32	63	31	0	89	68	77
7	0	39	75	6	43	24
50	50	68	39	0	36	78
40	83	0	14	78	10	79
0	58	70	11	53	67	40
40	17	33	35	79	0	38
84	12	29	22	53	71	0

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

36	67	35	4	93	72	81
17	10	49	85	16	53	34
60	60	78	49	10	46	88
48	91	8	22	86	18	87
23	81	93	34	76	90	63
58	35	51	53	97	18	56
92	20	37	30	61	79	8

The optimal value equals 81.

36	67	35	4	93	72	81
17	10	49	85	16	53	34
60	60	78	49	10	46	88
48	91	8	22	86	18	87
23	81	93	34	76	90	63
58	35	51	53	97	18	56
92	20	37	30	61	79	8

32	63	31	0	89	68	77	x
7	0	39	75	6	43	24	x
50	50	68	39	0	36	78	x
40	83	0	14	78	10	79	x
0	58	70	11	53	67	40	x
40	17	33	35	79	0	38	x
84	12	29	22	53	71	0	x

32	63	31	0	89	68	77
7	0	39	75	6	43	24
50	50	68	39	0	36	78
40	83	0	14	78	10	79
0	58	70	11	53	67	40
40	17	33	35	79	0	38
84	12	29	22	53	71	0

36	67	35	4	93	72	81
17	10	49	85	16	53	34
60	60	78	49	10	46	88
48	91	8	22	86	18	87
23	81	93	34	76	90	63
58	35	51	53	97	18	56
92	20	37	30	61	79	8

36	67	35	4	93	72	81
17	10	49	85	16	53	34
60	60	78	49	10	46	88
48	91	8	22	86	18	87
23	81	93	34	76	90	63
58	35	51	53	97	18	56
92	20	37	30	61	79	8

32	63	31	0	89	68	77	x
7	0	39	75	6	43	24	x
50	50	68	39	0	36	78	x
40	83	0	14	78	10	79	x
0	58	70	11	53	67	40	x
40	17	33	35	79	0	38	x
84	12	29	22	53	71	0	x

32	63	31	0	89	68	77
7	0	39	75	6	43	24
50	50	68	39	0	36	78
40	83	0	14	78	10	79
0	58	70	11	53	67	40
40	17	33	35	79	0	38
84	12	29	22	53	71	0

36	67	35	4	93	72	81
17	10	49	85	16	53	34
60	60	78	49	10	46	88
48	91	8	22	86	18	87
23	81	93	34	76	90	63
58	35	51	53	97	18	56
92	20	37	30	61	79	8

36	67	35	4	93	72	81
17	10	49	85	16	53	34
60	60	78	49	10	46	88
48	91	8	22	86	18	87
23	81	93	34	76	90	63
58	35	51	53	97	18	56
92	20	37	30	61	79	8

32	63	31	0	89	68	77	x
7	0	39	75	6	43	24	x
50	50	68	39	0	36	78	x
40	83	0	14	78	10	79	x
0	58	70	11	53	67	40	x
40	17	33	35	79	0	38	x
84	12	29	22	53	71	0	x

32	63	31	0	89	68	77
7	0	39	75	6	43	24
50	50	68	39	0	36	78
40	83	0	14	78	10	79
0	58	70	11	53	67	40
40	17	33	35	79	0	38
84	12	29	22	53	71	0

36	67	35	4	93	72	81
17	10	49	85	16	53	34
60	60	78	49	10	46	88
48	91	8	22	86	18	87
23	81	93	34	76	90	63
58	35	51	53	97	18	56
92	20	37	30	61	79	8