Question

Consider the following assignment problem where \(X, Y, Z\) are tasks, \(P, Q, R\) are agents and the cost matrix is given by:

	X	Y	Z
P	4	2	8
Q	2	3	7
R	3	1	6

Which of the following statements is/are TRUE for an optimal assignment?

• A. The cost is 9.
• B. Agent P is assigned to task Y.
• C. Agent Q is assigned to task X.
• D. Agent R is assigned to task Y.

Hint:

Try every one to one assignment of agents to tasks and pick the one with the smallest total cost.

Answer 1

The Correct Option is B, C

Step 1: Write down the cost matrix.
We are given agents P, Q, R and tasks X, Y, Z with the cost matrix:
P: X = 4, Y = 2, Z = 8.
Q: X = 2, Y = 3, Z = 7.
R: X = 3, Y = 1, Z = 6.
We need to find the assignment of one task to each agent that gives the minimum total cost.

Step 2: Do a row reduction.
Subtract the smallest entry in each row from every entry in that row.
Row P has minimum 2, so the new row is 2, 0, 6.
Row Q has minimum 2, so the new row is 0, 1, 5.
Row R has minimum 1, so the new row is 2, 0, 5.

Step 3: Do a column reduction.
Now look at each column of the row-reduced matrix.
Column X has entries 2, 0, 2, so its minimum is 0 (no change needed).
Column Y has entries 0, 1, 0, so its minimum is 0 (no change needed).
Column Z has entries 6, 5, 5, so its minimum is 5. Subtract 5 from column Z.
The matrix becomes: P: 2, 0, 1; Q: 0, 1, 0; R: 2, 0, 0.

Step 4: Pick an assignment using only the zero entries.
We need one zero in each row and each column, with no two zeros sharing a row or column.
P has a zero only at column Y, so P must go to Y.
Since Y is now used, Q must use its other zero, at column X.
Since X and Y are now used, R must go to the remaining column Z (which is also a zero for R).
This gives the assignment P to Y, Q to X, R to Z, and since we found a complete zero assignment, this is optimal.

Step 5: Compute the real cost and check each option.
Using the original cost matrix: cost = (P to Y) 2 + (Q to X) 2 + (R to Z) 6 = 10.
Option (A) says the cost is 9, but we found 10, so (A) is false.
Option (B) says agent P is assigned to task Y, which matches our optimal assignment, so (B) is true.
Option (C) says agent Q is assigned to task X, which also matches, so (C) is true.
Option (D) says agent R is assigned to task Y, but R is assigned to Z, so (D) is false.

Final Answer:
The optimal assignment is P to Y, Q to X, R to Z with total cost 10, so statements (B) and (C) are true. \[ \boxed{\text{(B) and (C)}} \]