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:

3	80	94	73	92	2	8
77	99	89	60	49	79	69
11	6	37	51	19	55	84
70	53	69	50	35	39	38
7	92	67	60	79	13	66
48	32	81	11	51	20	48
82	21	72	64	74	93	67

Subtract row minima

We subtract the row minimum from each row:

1	78	92	71	90	0	6	(-2)
28	50	40	11	0	30	20	(-49)
5	0	31	45	13	49	78	(-6)
35	18	34	15	0	4	3	(-35)
0	85	60	53	72	6	59	(-7)
37	21	70	0	40	9	37	(-11)
61	0	51	43	53	72	46	(-21)

Subtract column minima

We subtract the column minimum from each column:

1	78	61	71	90	0	3
28	50	9	11	0	30	17
5	0	0	45	13	49	75
35	18	3	15	0	4	0
0	85	29	53	72	6	56
37	21	39	0	40	9	34
61	0	20	43	53	72	43
		(-31)				(-3)

Cover all zeros with a minimum number of lines

There are 7 lines required to cover all zeros:

1	78	61	71	90	0	3	x
28	50	9	11	0	30	17	x
5	0	0	45	13	49	75	x
35	18	3	15	0	4	0	x
0	85	29	53	72	6	56	x
37	21	39	0	40	9	34	x
61	0	20	43	53	72	43	x

The optimal assignment

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

1	78	61	71	90	0	3
28	50	9	11	0	30	17
5	0	0	45	13	49	75
35	18	3	15	0	4	0
0	85	29	53	72	6	56
37	21	39	0	40	9	34
61	0	20	43	53	72	43

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

3	80	94	73	92	2	8
77	99	89	60	49	79	69
11	6	37	51	19	55	84
70	53	69	50	35	39	38
7	92	67	60	79	13	66
48	32	81	11	51	20	48
82	21	72	64	74	93	67

The optimal value equals 165.

3	80	94	73	92	2	8
77	99	89	60	49	79	69
11	6	37	51	19	55	84
70	53	69	50	35	39	38
7	92	67	60	79	13	66
48	32	81	11	51	20	48
82	21	72	64	74	93	67

1	78	61	71	90	0	3	x
28	50	9	11	0	30	17	x
5	0	0	45	13	49	75	x
35	18	3	15	0	4	0	x
0	85	29	53	72	6	56	x
37	21	39	0	40	9	34	x
61	0	20	43	53	72	43	x

1	78	61	71	90	0	3
28	50	9	11	0	30	17
5	0	0	45	13	49	75
35	18	3	15	0	4	0
0	85	29	53	72	6	56
37	21	39	0	40	9	34
61	0	20	43	53	72	43

3	80	94	73	92	2	8
77	99	89	60	49	79	69
11	6	37	51	19	55	84
70	53	69	50	35	39	38
7	92	67	60	79	13	66
48	32	81	11	51	20	48
82	21	72	64	74	93	67

3	80	94	73	92	2	8
77	99	89	60	49	79	69
11	6	37	51	19	55	84
70	53	69	50	35	39	38
7	92	67	60	79	13	66
48	32	81	11	51	20	48
82	21	72	64	74	93	67

1	78	61	71	90	0	3	x
28	50	9	11	0	30	17	x
5	0	0	45	13	49	75	x
35	18	3	15	0	4	0	x
0	85	29	53	72	6	56	x
37	21	39	0	40	9	34	x
61	0	20	43	53	72	43	x

1	78	61	71	90	0	3
28	50	9	11	0	30	17
5	0	0	45	13	49	75
35	18	3	15	0	4	0
0	85	29	53	72	6	56
37	21	39	0	40	9	34
61	0	20	43	53	72	43

3	80	94	73	92	2	8
77	99	89	60	49	79	69
11	6	37	51	19	55	84
70	53	69	50	35	39	38
7	92	67	60	79	13	66
48	32	81	11	51	20	48
82	21	72	64	74	93	67

3	80	94	73	92	2	8
77	99	89	60	49	79	69
11	6	37	51	19	55	84
70	53	69	50	35	39	38
7	92	67	60	79	13	66
48	32	81	11	51	20	48
82	21	72	64	74	93	67

1	78	61	71	90	0	3	x
28	50	9	11	0	30	17	x
5	0	0	45	13	49	75	x
35	18	3	15	0	4	0	x
0	85	29	53	72	6	56	x
37	21	39	0	40	9	34	x
61	0	20	43	53	72	43	x

1	78	61	71	90	0	3
28	50	9	11	0	30	17
5	0	0	45	13	49	75
35	18	3	15	0	4	0
0	85	29	53	72	6	56
37	21	39	0	40	9	34
61	0	20	43	53	72	43

3	80	94	73	92	2	8
77	99	89	60	49	79	69
11	6	37	51	19	55	84
70	53	69	50	35	39	38
7	92	67	60	79	13	66
48	32	81	11	51	20	48
82	21	72	64	74	93	67