# Five different machines can do any of the five required jobs, with different profits resulting from each assignment as shown below:Find the optimal assignment schedule. - Mathematics and Statistics

Sum

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.

Concept: Assignment Problem
Is there an error in this question or solution?

#### APPEARS IN

Balbharati Mathematics and Statistics 2 (Commerce) 12th Standard HSC Maharashtra State Board
Chapter 7 Assignment Problem and Sequencing
Exercise 7.1 | Q 3 | Page 118