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

#### 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?

#### 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