Answer to Question #85981 in Math for Umesh Patodi

Question

Solve the cost-minimising assignment problem whose cost matrix is given below:
Machines
M_1 M_2 M_3 M_4
J_1 10 12 9 11
Jobs J_2 5 10 7 8
J_3 12 14 13 11
J_4 8 15 11 9

Answer 1

The row on the top is the row of machines. The jobs are in the leftmost column. We will not write them below, only the values that we work with.

First, do the row reduction by subtracting the smallest value of job from the values of job in this row (for example, by subtracting 9 from every value in the first row):

$$\begin{matrix} 1 & 3 & 0 & 2 \\ 0 & 5 & 2 & 3 \\ 1 & 3 & 2 & 0 \\ 0 & 7 & 3 & 2 \end{matrix}$$

Then do the column reduction by subtracting 3 from every value in the second column, because we do not change columns with zeros:

$$\begin{matrix} 1 & 0 & 0 & 2 \\ 0 & 2 & 2 & 3 \\ 1 & 0 & 2 & 0 \\ 0 & 4 & 3 & 2 \end{matrix}$$

Thus we see that the jobs must be assigned the following way (assign one 0 from every column for one machine, only one job per one machine):

J1 - M3, J2 - M1, J3 - M2, J4 - M4.

The optimal value equals 37 (just add all the assigned jobs under the corresponding machines: 9+5+14+9)