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 belo…

Answer: M1 → A, M2 → B, M3 → E, M4 → D (place C left vacant); minimum cost = 12

The problem is unbalanced (4 machines, 5 places), so add a dummy machine M5 with zero costs. The prohibited placements (M2 at C, M3 at A) are given a very large cost M.

Row minimum subtraction (row minima 4, 4, 2, 2, 0). Every column then already has a zero, so column subtraction leaves the matrix unchanged. Making assignments (assigned zeros shown in brackets):

M1 has a single zero at A: assign M1 → A. M3 has a single zero at E: assign M3 → E (cross the zero of M2 at E). M4 has a single zero at D: assign M4 → D. M2 then has only B: assign M2 → B. The dummy M5 takes C.

Number of assignments = 5 = order of the matrix, so the solution is optimal.