2.
At the current basic feasible solution (bfs) \(\mathbf{v}_{0}\) (\(\mathbf{v}_{0} \in \mathbb{R}^{5}\)), the simplex method yields the following form of a linear programming problem in standard form.
minimize \(z = -x_{1} - 2x_{2}\)
s.t. \(x_{3} = 2 + 2x_{1} - x_{2}\)
\(x_{4} = 7 + x_{1} - 2x_{2}\)
\(x_{5} = 3 - x_{1}\)
\(x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \ge 0\)
Here the objective function is written as a function of the non-basic variables. If the simplex method moves to the adjacent bfs \(\mathbf{v}_{1}\) (\(\mathbf{v}_{1} \in \mathbb{R}^{5}\)) that best improves the objective function, which of the following represents the objective function at \(\mathbf{v}_{1}\), assuming that the objective function is written in the same manner as above?
Exam Year(s)
GATE ME - 2024,
Answer: A
The objective at \(\mathbf{v}_{1}\) is \(z = -4 - 5x_{1} + 2x_{3}\).
Both non-basic variables have negative coefficients in z, so increasing either one improves it. Find how far each can rise (ratio test) and the resulting z:
- Raising \(x_{2}\): \(x_{3} = 2 - x_{2} \ge 0\) gives \(x_{2} \le 2\), and \(x_{4} = 7 - 2x_{2}\) gives \(x_{2} \le 3.5\). So \(x_{2} = 2\), \(x_{3}\) leaves, and \(z = -4\).
- Raising \(x_{1}\): only \(x_{5} = 3 - x_{1}\) limits it, so \(x_{1} = 3\) and \(z = -3\).
The best improvement is to bring in \(x_{2}\). From the \(x_{3}\) row, \(x_{2} = 2 + 2x_{1} - x_{3}\), and substituting:
\[ \begin{aligned} z &= -x_{1} - 2(2 + 2x_{1} - x_{3}) \\ &= -4 - 5x_{1} + 2x_{3} \end{aligned} \]
Option B is the objective after bringing in \(x_{1}\), the lesser improvement. Option C has the wrong leaving variable (\(x_{4}\) is not the binding constraint), and D has the wrong constant.
