2.
The following table gives the unit transportation costs, the supply at each origin and the demand of each destination for a transportation problem.
| Origin / Destination | D1 | D2 | D3 | D4 | Supply |
| O1 | 3 | 4 | 8 | 7 | 60 |
| O2 | 7 | 3 | 7 | 6 | 80 |
| O3 | 3 | 9 | 3 | 4 | 100 |
| Demand | 40 | 70 | 50 | 80 |
Let \(x_{ij}\) denote the number of units to be transported from origin \(i\) to destination \(j\). If the u-v method is applied to improve the basic feasible solution given by \(x_{12} = 60,\ x_{22} = 10,\ x_{23} = 50,\ x_{24} = 20,\ x_{31} = 40\) and \(x_{34} = 60\), then the variables entering and leaving the basis, respectively, are
Exam Year(s)
GATE Mathematics - 2012,
Answer: A
The entering variable is \(x_{11}\) and the leaving variable is \(x_{24}\): \(x_{11}\) and \(x_{24}\).
Find \(u_{i}, v_{j}\) from \(u_{i} + v_{j} = c_{ij}\) on the basic cells, with \(u_{1} = 0\): \(v_{2} = 4\), \(u_{2} = -1\), \(v_{3} = 8\), \(v_{4} = 7\), \(u_{3} = -3\), \(v_{1} = 6\).
Reduced costs \(c_{ij} - u_{i} - v_{j}\) on the non-basic cells:
\[ \begin{aligned} x_{11} &: 3 - 0 - 6 = -3 \\ x_{33} &: 3 + 3 - 8 = -2 \\ x_{13}, x_{14} &: 0 \\ x_{21} &: 2,\quad x_{32}: 8 \end{aligned} \]
The most negative is \(x_{11}\), so it enters. Its loop is \(x_{11}(+), x_{12}(-), x_{22}(+), x_{24}(-), x_{34}(+), x_{31}(-)\). The minus cells hold 60, 20 and 40, so \(\theta = 20\) and \(x_{24}\) leaves.
The options entering \(x_{13}\) or \(x_{14}\) are wrong because those cells have zero reduced cost and would not lower the cost, and \(x_{33}\), at -2, is less negative than \(x_{11}\), at -3.
