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

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

Advertisements

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.

  Is there an error in this question or solution?
Chapter 7: Assignment Problem and Sequencing - Exercise 7.1 [Page 118]

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

Video TutorialsVIEW ALL [1]

Share
Notifications



      Forgot password?
Use app×