<s>[INST] Simplex Method Solution 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?
 [/INST] 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}
</s>