Maharashtra State BoardHSC Commerce 12th Board Exam
Advertisement Remove all ads

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

Advertisement Remove all ads
Advertisement Remove all ads
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.

Advertisement Remove all ads

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?
Advertisement Remove all ads

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]

Advertisement Remove all ads
Share
Notifications

View all notifications


      Forgot password?
View in app×