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:

31	88	61	39	21	24	42	77
74	40	56	75	36	49	65	25
34	50	42	47	86	33	64	41
2	70	83	70	82	74	1	52
61	31	66	36	84	20	37	52
45	6	28	48	7	95	90	63
58	69	43	37	58	90	79	83
32	33	13	31	49	47	30	56

Subtract row minima

We subtract the row minimum from each row:

10	67	40	18	0	3	21	56	(-21)
49	15	31	50	11	24	40	0	(-25)
1	17	9	14	53	0	31	8	(-33)
1	69	82	69	81	73	0	51	(-1)
41	11	46	16	64	0	17	32	(-20)
39	0	22	42	1	89	84	57	(-6)
21	32	6	0	21	53	42	46	(-37)
19	20	0	18	36	34	17	43	(-13)

Subtract column minima

We subtract the column minimum from each column:

9	67	40	18	0	3	21	56
48	15	31	50	11	24	40	0
0	17	9	14	53	0	31	8
0	69	82	69	81	73	0	51
40	11	46	16	64	0	17	32
38	0	22	42	1	89	84	57
20	32	6	0	21	53	42	46
18	20	0	18	36	34	17	43
(-1)

Cover all zeros with a minimum number of lines

There are 8 lines required to cover all zeros:

9	67	40	18	0	3	21	56	x
48	15	31	50	11	24	40	0	x
0	17	9	14	53	0	31	8	x
0	69	82	69	81	73	0	51	x
40	11	46	16	64	0	17	32	x
38	0	22	42	1	89	84	57	x
20	32	6	0	21	53	42	46	x
18	20	0	18	36	34	17	43	x

The optimal assignment

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

9	67	40	18	0	3	21	56
48	15	31	50	11	24	40	0
0	17	9	14	53	0	31	8
0	69	82	69	81	73	0	51
40	11	46	16	64	0	17	32
38	0	22	42	1	89	84	57
20	32	6	0	21	53	42	46
18	20	0	18	36	34	17	43

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

31	88	61	39	21	24	42	77
74	40	56	75	36	49	65	25
34	50	42	47	86	33	64	41
2	70	83	70	82	74	1	52
61	31	66	36	84	20	37	52
45	6	28	48	7	95	90	63
58	69	43	37	58	90	79	83
32	33	13	31	49	47	30	56

The optimal value equals 157.

31	88	61	39	21	24	42	77
74	40	56	75	36	49	65	25
34	50	42	47	86	33	64	41
2	70	83	70	82	74	1	52
61	31	66	36	84	20	37	52
45	6	28	48	7	95	90	63
58	69	43	37	58	90	79	83
32	33	13	31	49	47	30	56

9	67	40	18	0	3	21	56	x
48	15	31	50	11	24	40	0	x
0	17	9	14	53	0	31	8	x
0	69	82	69	81	73	0	51	x
40	11	46	16	64	0	17	32	x
38	0	22	42	1	89	84	57	x
20	32	6	0	21	53	42	46	x
18	20	0	18	36	34	17	43	x

9	67	40	18	0	3	21	56
48	15	31	50	11	24	40	0
0	17	9	14	53	0	31	8
0	69	82	69	81	73	0	51
40	11	46	16	64	0	17	32
38	0	22	42	1	89	84	57
20	32	6	0	21	53	42	46
18	20	0	18	36	34	17	43

31	88	61	39	21	24	42	77
74	40	56	75	36	49	65	25
34	50	42	47	86	33	64	41
2	70	83	70	82	74	1	52
61	31	66	36	84	20	37	52
45	6	28	48	7	95	90	63
58	69	43	37	58	90	79	83
32	33	13	31	49	47	30	56

31	88	61	39	21	24	42	77
74	40	56	75	36	49	65	25
34	50	42	47	86	33	64	41
2	70	83	70	82	74	1	52
61	31	66	36	84	20	37	52
45	6	28	48	7	95	90	63
58	69	43	37	58	90	79	83
32	33	13	31	49	47	30	56

9	67	40	18	0	3	21	56	x
48	15	31	50	11	24	40	0	x
0	17	9	14	53	0	31	8	x
0	69	82	69	81	73	0	51	x
40	11	46	16	64	0	17	32	x
38	0	22	42	1	89	84	57	x
20	32	6	0	21	53	42	46	x
18	20	0	18	36	34	17	43	x

9	67	40	18	0	3	21	56
48	15	31	50	11	24	40	0
0	17	9	14	53	0	31	8
0	69	82	69	81	73	0	51
40	11	46	16	64	0	17	32
38	0	22	42	1	89	84	57
20	32	6	0	21	53	42	46
18	20	0	18	36	34	17	43

31	88	61	39	21	24	42	77
74	40	56	75	36	49	65	25
34	50	42	47	86	33	64	41
2	70	83	70	82	74	1	52
61	31	66	36	84	20	37	52
45	6	28	48	7	95	90	63
58	69	43	37	58	90	79	83
32	33	13	31	49	47	30	56

31	88	61	39	21	24	42	77
74	40	56	75	36	49	65	25
34	50	42	47	86	33	64	41
2	70	83	70	82	74	1	52
61	31	66	36	84	20	37	52
45	6	28	48	7	95	90	63
58	69	43	37	58	90	79	83
32	33	13	31	49	47	30	56

9	67	40	18	0	3	21	56	x
48	15	31	50	11	24	40	0	x
0	17	9	14	53	0	31	8	x
0	69	82	69	81	73	0	51	x
40	11	46	16	64	0	17	32	x
38	0	22	42	1	89	84	57	x
20	32	6	0	21	53	42	46	x
18	20	0	18	36	34	17	43	x

9	67	40	18	0	3	21	56
48	15	31	50	11	24	40	0
0	17	9	14	53	0	31	8
0	69	82	69	81	73	0	51
40	11	46	16	64	0	17	32
38	0	22	42	1	89	84	57
20	32	6	0	21	53	42	46
18	20	0	18	36	34	17	43

31	88	61	39	21	24	42	77
74	40	56	75	36	49	65	25
34	50	42	47	86	33	64	41
2	70	83	70	82	74	1	52
61	31	66	36	84	20	37	52
45	6	28	48	7	95	90	63
58	69	43	37	58	90	79	83
32	33	13	31	49	47	30	56