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:

93	2	23	66	83	59	90
80	46	35	4	96	37	5
73	57	46	64	81	12	60
99	94	77	93	14	20	46
98	77	28	2	88	82	10
83	35	16	3	69	33	40
69	83	31	70	25	16	86

Subtract row minima

We subtract the row minimum from each row:

91	0	21	64	81	57	88	(-2)
76	42	31	0	92	33	1	(-4)
61	45	34	52	69	0	48	(-12)
85	80	63	79	0	6	32	(-14)
96	75	26	0	86	80	8	(-2)
80	32	13	0	66	30	37	(-3)
53	67	15	54	9	0	70	(-16)

Subtract column minima

We subtract the column minimum from each column:

38	0	8	64	81	57	87
23	42	18	0	92	33	0
8	45	21	52	69	0	47
32	80	50	79	0	6	31
43	75	13	0	86	80	7
27	32	0	0	66	30	36
0	67	2	54	9	0	69
(-53)		(-13)				(-1)

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

38	0	8	64	81	57	87	x
23	42	18	0	92	33	0	x
8	45	21	52	69	0	47	x
32	80	50	79	0	6	31	x
43	75	13	0	86	80	7	x
27	32	0	0	66	30	36	x
0	67	2	54	9	0	69	x

The optimal assignment

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

38	0	8	64	81	57	87
23	42	18	0	92	33	0
8	45	21	52	69	0	47
32	80	50	79	0	6	31
43	75	13	0	86	80	7
27	32	0	0	66	30	36
0	67	2	54	9	0	69

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

93	2	23	66	83	59	90
80	46	35	4	96	37	5
73	57	46	64	81	12	60
99	94	77	93	14	20	46
98	77	28	2	88	82	10
83	35	16	3	69	33	40
69	83	31	70	25	16	86

The optimal value equals 120.

93	2	23	66	83	59	90
80	46	35	4	96	37	5
73	57	46	64	81	12	60
99	94	77	93	14	20	46
98	77	28	2	88	82	10
83	35	16	3	69	33	40
69	83	31	70	25	16	86

38	0	8	64	81	57	87	x
23	42	18	0	92	33	0	x
8	45	21	52	69	0	47	x
32	80	50	79	0	6	31	x
43	75	13	0	86	80	7	x
27	32	0	0	66	30	36	x
0	67	2	54	9	0	69	x

38	0	8	64	81	57	87
23	42	18	0	92	33	0
8	45	21	52	69	0	47
32	80	50	79	0	6	31
43	75	13	0	86	80	7
27	32	0	0	66	30	36
0	67	2	54	9	0	69

93	2	23	66	83	59	90
80	46	35	4	96	37	5
73	57	46	64	81	12	60
99	94	77	93	14	20	46
98	77	28	2	88	82	10
83	35	16	3	69	33	40
69	83	31	70	25	16	86

93	2	23	66	83	59	90
80	46	35	4	96	37	5
73	57	46	64	81	12	60
99	94	77	93	14	20	46
98	77	28	2	88	82	10
83	35	16	3	69	33	40
69	83	31	70	25	16	86

38	0	8	64	81	57	87	x
23	42	18	0	92	33	0	x
8	45	21	52	69	0	47	x
32	80	50	79	0	6	31	x
43	75	13	0	86	80	7	x
27	32	0	0	66	30	36	x
0	67	2	54	9	0	69	x

38	0	8	64	81	57	87
23	42	18	0	92	33	0
8	45	21	52	69	0	47
32	80	50	79	0	6	31
43	75	13	0	86	80	7
27	32	0	0	66	30	36
0	67	2	54	9	0	69

93	2	23	66	83	59	90
80	46	35	4	96	37	5
73	57	46	64	81	12	60
99	94	77	93	14	20	46
98	77	28	2	88	82	10
83	35	16	3	69	33	40
69	83	31	70	25	16	86

93	2	23	66	83	59	90
80	46	35	4	96	37	5
73	57	46	64	81	12	60
99	94	77	93	14	20	46
98	77	28	2	88	82	10
83	35	16	3	69	33	40
69	83	31	70	25	16	86

38	0	8	64	81	57	87	x
23	42	18	0	92	33	0	x
8	45	21	52	69	0	47	x
32	80	50	79	0	6	31	x
43	75	13	0	86	80	7	x
27	32	0	0	66	30	36	x
0	67	2	54	9	0	69	x

38	0	8	64	81	57	87
23	42	18	0	92	33	0
8	45	21	52	69	0	47
32	80	50	79	0	6	31
43	75	13	0	86	80	7
27	32	0	0	66	30	36
0	67	2	54	9	0	69

93	2	23	66	83	59	90
80	46	35	4	96	37	5
73	57	46	64	81	12	60
99	94	77	93	14	20	46
98	77	28	2	88	82	10
83	35	16	3	69	33	40
69	83	31	70	25	16	86