Question

A mine workshop needs to assign 4 jobs to 4 service engineers. The cost for performing a job by an individual service engineer is given. A typical job can be assigned to only one service engineer. If the service engineer S1 cannot perform the job J3, and S3 cannot perform the job J4, the optimal cost for completion of jobs is . (answer in integer)

Service Engineer	J1	J2	J3	J4
S1	50	50	---	20
S2	70	40	20	70
S3	90	30	50	---
S4	70	20	60	30

Hint:

Use the Hungarian assignment method, blocking S1-J3 and S3-J4 with a very high cost so they never get picked.

Answer 1

Correct Answer: 130

Step 1: Set up the cost matrix and block the forbidden pairs.
This is a standard assignment problem: 4 engineers, 4 jobs, one job per engineer, minimize total cost. Since S1 cannot do J3 and S3 cannot do J4, replace those two cells with a very large cost M so the algorithm never picks them.
\[ \begin{array}{c|cccc} & J1 & J2 & J3 & J4 \\ \hline S1 & 50 & 50 & M & 20 \\ S2 & 70 & 40 & 20 & 70 \\ S3 & 90 & 30 & 50 & M \\ S4 & 70 & 20 & 60 & 30 \end{array} \]

Step 2: Reduce rows and columns (Hungarian method).
Subtract each row's smallest entry from that row. Row minimums are 20, 20, 30 and 20 for S1 to S4.
\[ \begin{array}{c|cccc} & J1 & J2 & J3 & J4 \\ \hline S1 & 30 & 30 & M & 0 \\ S2 & 50 & 20 & 0 & 50 \\ S3 & 60 & 0 & 20 & M \\ S4 & 50 & 0 & 40 & 10 \end{array} \]
Now subtract each column's smallest remaining entry. Only column J1 still has a nonzero minimum (30), so subtract 30 from column J1. Columns J2, J3 and J4 already contain a zero each.
\[ \begin{array}{c|cccc} & J1 & J2 & J3 & J4 \\ \hline S1 & 0 & 30 & M & 0 \\ S2 & 20 & 20 & 0 & 50 \\ S3 & 30 & 0 & 20 & M \\ S4 & 20 & 0 & 40 & 10 \end{array} \]

Step 3: Try a complete zero assignment, adjust if it is blocked.
S2's only zero is J3, so S2 must take J3. S3 and S4 both only show a zero at J2, so they compete for it, while S1's zeros sit at J1 and J4. Covering every zero needs only 3 lines (row S1, column J2, column J3), which is fewer than the matrix size of 4, so the matrix is not yet optimal. By the Hungarian rule, subtract the smallest uncovered value (10, at S4-J4) from every uncovered cell and add it to cells covered twice.
This reshuffles the zeros so S1 keeps J1 and J4 as zeros, S2 keeps J3, S3's only zero becomes J2, and a fresh zero opens up at S4-J4, giving a complete assignment: S1-J1, S2-J3, S3-J2, S4-J4.

Step 4: Add up the actual costs for this assignment.
\[ \text{Cost} = 50\ (S1\text{-}J1) + 20\ (S2\text{-}J3) + 30\ (S3\text{-}J2) + 30\ (S4\text{-}J4) = 130 \]

Final Answer:
The optimal (minimum) cost for completing all four jobs is 130. \[ \boxed{130} \]