Question

For a transportation problem, let \(c_{ij}\) denote the unit cost of the cell \((i, j)\). The known unit costs are shown below (a dash marks a cell whose cost is not given).

	j = 1	j = 2	j = 3
i = 1	10	12	19
i = 2	11	13	-
i = 3	-	-	-

Let \(\alpha_i\) and \(\beta_j\), \(i, j = 1, 2, 3\), be the simplex multipliers associated with a basis corresponding to this unit cost table, so that \(\alpha_1 = x\), \(\alpha_2 = x + 1\), \(\beta_1 = y\) and \(\beta_2 = y + 2\). The relative cost coefficient \(d_{ij}\) is the difference between the current solution and the new improved solution.
If \(x = 4\), \(c_{13} = 19\) and \(\beta_3 = y + 5\), then which one of the following is TRUE?

• A. \(y = 6\) and \(d_{13} = 7\)
• B. \(y = 6\) and \(d_{13} = 4\)
• C. \(y = 5\) and \(d_{13} = 7\)
• D. \(y = 5\) and \(d_{13} = 4\)

Hint:

Use the basic-cell rule \(c_{ij} = \alpha_i + \beta_j\) to first pin down \(x+y\), then use \(x=4\) to get \(y\), and finally use \(d_{13}=c_{13}-(\alpha_1+\beta_3)\) for the non-basic cell \((1,3)\).

Answer 1

The Correct Option is B

Step 1: Understanding the Question.
In a transportation problem, the simplex multipliers (also called the u-v values) satisfy \(\alpha_i + \beta_j = c_{ij}\) for every basic (occupied) cell, and give the relative cost coefficient \(d_{ij} = c_{ij} - (\alpha_i + \beta_j)\) for every non-basic (empty) cell. The basic cells here are \((1,1), (1,2), (2,1), (2,2)\), since their costs \(c_{11}, c_{12}, c_{21}, c_{22}\) are given directly.

Step 2: Set up the multiplier equations.
Since \((1,1)\) is a basic cell, \(c_{11} = \alpha_1 + \beta_1\), so
\[ 10 = x + y \]
Check this against the other basic cells. For \((1,2)\): \(c_{12} = \alpha_1 + \beta_2\) gives \(12 = x + (y+2) = (x+y) + 2 = 10 + 2 = 12\), which matches. For \((2,1)\): \(c_{21} = \alpha_2 + \beta_1\) gives \(11 = (x+1) + y = (x+y) + 1 = 11\), which matches. For \((2,2)\): \(c_{22} = \alpha_2 + \beta_2\) gives \(13 = (x+1) + (y+2) = (x+y) + 3 = 13\), which also matches. So all four basic-cell equations reduce to the single relation \(x + y = 10\).

Step 3: Solve for y.
We are given \(x = 4\). Put this into \(x + y = 10\):
\[ y = 10 - x = 10 - 4 = 6 \]

Step 4: Find beta_3 and compute d13.
We are given \(\beta_3 = y + 5 = 6 + 5 = 11\). The cell \((1,3)\) is non-basic, so its relative cost coefficient is
\[ d_{13} = c_{13} - (\alpha_1 + \beta_3) = 19 - (4 + 11) = 19 - 15 = 4 \]

Final Answer:
We get \(y = 6\) and \(d_{13} = 4\), which is option (B). The other options change either the value of \(y\) or of \(d_{13}\): option (A) keeps \(y=6\) but wrongly has \(d_{13}=7\), and options (C), (D) both use \(y=5\), which contradicts \(x+y=10\) with \(x=4\).
\[ \boxed{y = 6,\ d_{13} = 4} \]