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.
Solution
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.