# 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?

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).
• I know that was the operation used. So you're saying that although $x_4$ is in the basis with a nonzero coefficient, you can still perform the simplex method? It looks more like a row operation. I would consider a simplex method iteration as being a new variable entering the basis and an old one leaving. Here, you're just doing a row operation to make $x_4$ "correct" – KennyB Mar 24 '18 at 14:29
• @KennyB Since this is a maximasation problem, the objective function value should not decrease after one iteration. With the initial solution $(x_3,x_4) = (15, 20)$, you reach tableau (b) "after zero iteration". Observe that it's the unique optimal BFS to the problem in (b), and that the objective values in other tableaux (a), (c) and (d) are smaller than the one in (b). – GNUSupporter 8964民主女神 地下教會 Mar 24 '18 at 15:39