Advertisement Remove all ads

Four new machines M1, M2, M3 and M4 are to be installed in a machine shop. There are five vacant places A, B, C, D and E available. Because of limited space, machine M2 cannot be placed at C and M3 c - Mathematics and Statistics

Sum

Four new machines M1, M2, M3 and M4 are to be installed in a machine shop. There are five vacant places A, B, C, D and E available. Because of limited space, machine M2 cannot be placed at C and M3 cannot be placed at A. The cost matrix is given below.

Machines Places
  A B C D E
M1 4 6 10 5 6
M2 7 4 5 4
M3 6 9 6 2
M4 9 3 7 2 3

Find the optimal assignment schedule.

Advertisement Remove all ads

Solution

Step 1:
Here, number of rows and columns are not equal.
∴ The problem is unbalanced.
∴ It is balanced by introducing dummy machine M5 with zero cost.
Also, M2 cannot be placed at C and M3 cannot be placed at A.
Let a very high cost (`oo`) be assigned to corresponding elements.
∴ Matrix obtained is as follows:

Machines Places
  A B C D E
M1 4 6 10 5 6
M2 7 4 `oo` 5 4
M3 `oo` 6 9 6 2
M4 9 3 7 2 3
M5 0 0 0 0 0

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

Machines Places
  A B C D E
M1 0 2 6 1 2
M2 3 0 `oo` 1 0
M3 `oo` 4 7 4 0
M4 7 1 5 0 1
M5 0 0 0 0 0

Step 3:
Column minimum
Here, each column contains element zero.
∴ Matrix obtained by column minimum is same as above matrix.

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.

Machines Places
  A B C D E
M1 0 2 6 1 2
M2 3 0 `oo` 1 0
M3 `oo` 4 7 4 0
M4 7 1 5 0 1
M5 0 0 0 0 0

Step 5:
From step 4, 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:

Machines Places
  A B C D E
M1 0 2 6 1 2
M2 3 0 `oo` 1 0
M3 `oo` 4 7 4 0
M4 7 1 5 0 1
M5 0 0 0 0 0

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

Machines Place Cost
M1 A 4
M2 B 4
4M3 E 2
M4 D 2
M5 C 0

∴ The total minimum cost = 4 + 4 + 2 + 2 + 0 = ₹ 12.

  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 4 | Page 119
Advertisement Remove all ads
Advertisement Remove all ads
Share
Notifications

View all notifications


      Forgot password?
View in app×