Question

Four new machines M₁, M₂, M₃ and M₄ 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 M₂ cannot be placed at C and M₃ 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

Answer 1

Step 1:

Here, number of rows and columns are not equal.

∴ The problem is unbalanced.

∴ It is balanced by introducing dummy machine M₅ with zero cost.

Also, M₂ cannot be placed at C and M₃ 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 the 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
M3	E	2
M4	D	2
M5	C	0

∴ The total minimum cost = 4 + 4 + 2 + 2 + 0

= ₹ 12

Note that no machine will be installed at location C, since it gets dummy machine M₅