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

Instead of using the row and column reduction method, we can just list every possible way to assign the three agents to the three tasks and compare the total costs directly, since there are only a few of them.

1. Understanding the approach: With 3 agents and 3 tasks, there are $3! = 6$ possible one to one assignments. We calculate the total cost of each one directly from the matrix and compare them.
2. P-X, Q-Y, R-Z: cost $= 4+3+6=13$.
3. P-X, Q-Z, R-Y: cost $= 4+7+1=12$.
4. P-Y, Q-X, R-Z: cost $= 2+2+6=10$.
5. P-Y, Q-Z, R-X: cost $= 2+7+3=12$.
6. P-Z, Q-X, R-Y: cost $= 8+2+1=11$.
7. P-Z, Q-Y, R-X: cost $= 8+3+3=14$.

The smallest total among these six values is 10, coming from the single assignment P-Y, Q-X, R-Z. Since it is the only assignment with cost 10, it is the unique optimal assignment.

Let's summarize:

• Checking the statements against this optimal assignment: the cost is 10, not 9, so (A) is false.
• Agent P does go to Y, so (B) is true. Agent Q does go to X, so (C) is true. Agent R goes to Z, not Y, so (D) is false.

So the true statements are (B) and (C).

$$\boxed{(B) \text{ and } (C)}$$