Question

Five different machines can do any of the five required jobs, with different profits resulting from each assignment as shown below:

Job	Machines (Profit in ₹)
	A	B	C	D	E
1	30	37	40	28	40
2	40	24	27	21	36
3	40	32	33	30	35
4	25	38	40	36	36
5	29	62	41	34	39

Find the optimal assignment schedule.

Answer 1

Step 1:
Since it is a maximization problem, subtract each of the elements in the table from the largest element, i.e., 62

Jobs	Machines (Profit in ₹)
	A	B	C	D	E
1	32	25	22	34	22
2	22	38	35	41	26
3	22	30	29	32	27
4	37	24	22	26	26
5	33	0	21	28	23

Step 2:
Row minimum Subtract the smallest element in each row from every element in its row.
The matrix obtained is given below:

Jobs	Machines (Profit in ₹)
	A	B	C	D	E
1	10	3	0	12	0
2	0	16	13	19	4
3	0	8	7	10	5
4	15	2	0	4	4
5	33	0	21	28	23

Step 3:
Column minimum Subtract the smallest element in each column of assignment matrix obtained in step 2 from every element in its column.

Jobs	Machines (Profit in ₹)
	A	B	C	D	E
1	10	3	0	8	0
2	0	16	13	15	4
3	0	8	7	6	5
4	15	2	0	0	4
5	33	0	21	24	23

Step 4:
Draw minimum number of vertical and horizontal lines to cover all zeros.
First cover all rows and columns which have maximum number of zeros.

Jobs	Machines (Profit in ₹)
	A	B	C	D	E
1	10	3	0	8	0
2	0	16	13	15	4
3	0	8	7	6	5
4	15	2	0	0	4
5	33	0	21	24	23

Step 5:
From step 4, minimum number of lines covering all the zeros are 4, which is less than order of matrix, i.e., 5.
∴ Select smallest element from all the uncovered elements, i.e., 4 and subtract it from all the uncovered elements and add it to the elements which lie at the intersection of two lines.

Jobs	Machines (Profit in ₹)
	A	B	C	D	E
1	14	3	0	8	0
2	0	12	9	11	0
3	0	4	3	2	1
4	19	2	0	0	4
5	37	0	21	24	23

Step 6:
Draw minimum number of vertical and horizontal lines to cover all zeros.

Jobs	Machines (Profit in ₹)
	A	B	C	D	E
1	14	3	0	8	0
2	0	12	9	11	0
3	0	4	3	2	1
4	19	2	0	0	4
5	37	0	21	24	23

Step 7:
From step 6, minimum number of lines covering all the zeros are 5, which is equal to order of the matrix, i.e., 5.
∴  Select a row with exactly one zero, enclose that zero in () and cross out all zeros in its respective column.
Similarly, examine each row and column and mark the assignment ().
∴ The matrix obtained is as follows:

Jobs	Machines (Profit in ₹)
	A	B	C	D	E
1	14	3	0	8	0
2	0	12	9	11	0
3	0	4	3	2	1
4	19	2	0	0	4
5	37	0	21	24	23

Step 8:
The matrix obtained in step 7 contains exactly one assignment for each row and column.
∴ Optimal assignment schedule is as follows:

Jobs	Machines	Profit (in ₹)
1	C	40
2	E	36
3	A	40
4	D	36
5	B	62

∴ Total maximum profit = 40 + 36 + 40 + 36 + 62 = ₹ 214.