So I and 2 colleagues are arguing over a solution to an exam question and would like some clarification. It's an MCQ
Q: Consider the following tableau for a maximisation LP Problem:
\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline x_3 & 1 & 1 & 1 & 0 & 15\\ x_4 & 1 & 2 & 0 & 1 & 20\\ \hline z & -3 & 0 & 0 & -6 & -75 \end{array}
Which of the following tableau will be reached after performing one step of the Simplex Method?
a)\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline x_1 & 1 & 1 & 1 & 0 & 15\\ x_4 & 0 & 1 & -1 & 1 & 5\\ \hline z & 0 & 3 & 3 & 0 & -30 \end{array}
b)\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline x_3 & 1 & 1 & 1 & 0 & 15\\ x_4 & 1 & 2 & 0 & 1 & 20\\ \hline z & 3 & 12 & 0 & 0 & 45 \end{array}
c)\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline x_3 & 0 & -1 & 1 & -1 & -5\\ x_1 & 1 & 2 & 0 & 1 & 20\\ \hline z & 0 & 6 & 0 & -3 & -15 \end{array}
d)\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline x_2 & -3 & 1 & 0 & 1 & 6\\ x_3 & -1 & 0 & 1 & -2 & 2\\ \hline z & -2 & 0 & 0 & 1 & 20 \end{array}
e) We cannot perform an update on this tableau.
My one colleague says the answer is b) As your Pivot column is $x_4$ as it has the largest negative element. Most texts state that the pivot column is determined by the largest negative value.
The other colleague says it's e) as $x_2$ is nonbasic yet has a coefficient of 0 in the z row.
Now, I think there is a mistake in the actual question, since $x_4$ is in the basis, but does not have a 0 coefficient in the z row... which means this tableau is already wrong and should actually be something like
\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline x_3 & 1 & 1 & 1 & 0 & 15\\ x_4 & 1 & 2 & 0 & 1 & 20\\ \hline z & -3 & -6 & 0 & 0 & -75 \end{array}
So which is it? Is the question wrong from the start like I suggested.. or is someone actually right.. or are we all wrong and the solution is one of the other options?
The first colleague's answer is right, but the argument is not. We have to observe the coefficients from a tableau with the $z$-row fixed. The $-6$ tells you nothing about the LP's optimality since it's in the $x_4$-column representing the current basis.
Since $x_4$ is in the basis, you have to clear the entry $-6$ at the $z$-row. To do so, multiply the $x_4$-row by $6$ and add the result to the $z$-row. This gives the tableau in (b).
\begin{array}{r|rrrr|r} & x_1 & x_2 & x_3 & x_4 & \text{b} \\ \hline z_0 & -3 & 0 & 0 & -6 & -75\\ +\; 6x_4 & 6 & 12 & 0 & 6 & 120\\ \hline z_1 & 3 & 12 & 0 & 0 & 45 \end{array}