GATE 2024 ME – Question 39
At the current basic feasible solution (bfs) $\boldsymbol{v_0}$ ($\boldsymbol{v_0} \in \mathbb{R}^5$), the simplex method yields the following form of a linear programming problem in standard form.
$$\text{minimize } z = -x_1 - 2x_2$$
$$\text{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 $\boldsymbol{v_1}$ ($\boldsymbol{v_1} \in \mathbb{R}^5$) that best improves the objective function, which of the following represents the objective function at $\boldsymbol{v_1}$, assuming that the objective function is written in the same manner as above?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $z = -4 - 5x_1 + 2x_3$
Explanation
At $\boldsymbol{v_0}$, $x_1 = x_2 = 0$ and $z = 0$. If $x_1$ enters, the only limit is $x_5 = 3 - x_1 \ge 0$, so $x_1 = 3$ and $z = -3$. If $x_2$ enters, the limits are $x_3 = 2 - x_2 \ge 0$ and $x_4 = 7 - 2x_2 \ge 0$, so $x_2 = 2$ (with $x_3$ leaving) and $z = -4$. The better adjacent point is the second, with $x_2 = 2 + 2x_1 - x_3$. Substituting, $z = -x_1 - 2(2 + 2x_1 - x_3) = -4 - 5x_1 + 2x_3$.