# Stuck on two phase simplex where RHS $= 0$

I'm stuck on the following linear program, it's a minimal example of the problem I'm having:

Minimize $Z = y$ where $x \ge 1$ and $-2x+y \ge 0$

We start by rewriting this as a system of linear equalities, introducing slack and artificial variables:

$\left\{ \begin{array}{c} x - s_1 + a_1=1\\ -2x +y - s_2=0 \end{array} \right.$

We shouldn't need an artificial variable for the second one: $a_1 = 1,s_2=0$ is already feasible.

For phase 1 maximize $p = -a_1 = x-s_1-1$. This gives us the starting tableau

$$\begin{array}{c|ccccc|c} &x&y&s_1&s_2&a_1&A\\ \hline a_1&1&0&-1&0&1&1\\ s_2&-2&1&0&-1&0&0\\ \hline -p&1&0&-1&0&0&1 \end{array}$$ With solution $a_1=1/1=1,s_1=0/(-1)=0$

The only positive element in in column 1, so $x$ is the entering variable. The only positive element in this column is in row 1, so $a_1$ is the leaving variable. Pivoting around (1,1) results in the tableau:

$$\begin{array}{c|ccccc|c} &x&y&s_1&s_2&a_1&A\\ \hline x&1&0&-1&0&1&1\\ s_2&0&1&-2&-1&2&2\\ \hline -p&0&0&0&0&-1&0 \end{array}$$

With solution $x=1/1=1,s_2=2/(-1) = -2$.

Wait what? How did $s_2$ suddenly become negative? What did I do wrong?

• An artificial variable is necessary for the second constraint! Why not? – callculus Feb 24 '18 at 18:28
• @callculus I thought you added artificial variables to create your initial feasible solution? – Todd Sewell Feb 24 '18 at 18:30
• You always introduce artificial variables for equalities and $\geq$-constraints. – callculus Feb 24 '18 at 18:31
• @callculus Ah, that solved my problem, thanks! Is there an enumeration of the full rules somewhere? – Todd Sewell Feb 24 '18 at 18:39
• My comment has been deleted. Argh. \\ You´re welcome. It would make more sense if you search by yourself. Good keywords might be linear programming artificial two phase -big (without big). But with the given information I think you are able to solve the most standard linear programming problems. I´m confident about that. – callculus Feb 24 '18 at 18:59

How did $s_2$ suddenly become negative? What did I do wrong?

You've chosen the wrong entering variable. This give rise to an unfeasible solution.

To set up the initial tableau, multiply the second equation of the system $$\left\{ \begin{array}{c} x - s_1 + a_1=1\\ -2x +y - s_2=0, \end{array} \right.$$ by $-1$, so that the coefficient of the current basic variable $s_2$ becomes $1$. This makes the tableau proper. \begin{array}{c|ccccc|cc} &x&y&s_1&s_2&a_1&A&\text{ratio}\\ \hline a_1&1&0&-1&0&1&1 & 1/1 = 1\\ s_2&\fbox{2}&-1&0&1&0&0 & \fbox{0/2 = 0}\\ \hline p&-1&0&1&0&0&-1 \end{array} For feasibility reason, one has to pivot around $(1,2)$. \begin{array}{c|ccccc|c} &x&y&s_1&s_2&a_1&A\\ \hline a_1&0&\fbox{1/2}&-1&-1/2&1&\fbox1\\ x&1&-1/2&0&1/2&0&0\\ \hline p&0&-1/2&1&1/2&0&-1 \end{array}

\begin{array}{c|ccccc|c} &x&y&s_1&s_2&a_1&A\\ \hline y&0&1&-2&-1&2&2\\ x&1&0&-1&0&1&1\\ \hline p&0&0&0&0&1&0 \end{array} This gives us a feasible nondegenerate solution $(x,y) = (1,2)$.

To start phase II, we discard the column representing artificial variable $a_1$, calculate the objective function row, and reuse the rest of the above tableau.

$$\min Z = y \iff \max z = -y$$

\begin{array}{c|cccc|c} &x&y&s_1&s_2&A\\ \hline y&0&1&-2&-1&2\\ x&1&0&-1&0&1\\ \hline z&0&1&0&0&0 \end{array}

To make it a simplex tableau, make the entries representing the current basis zero at the objective function row.

\begin{array}{c|cccc|c} &x&y&s_1&s_2&A\\ \hline y&0&1&-2&-1&2\\ x&1&0&-1&0&1\\ \hline z&0&0&2&1&-2 \end{array}

Therefore, the solution is $(x,y) = (1,2)$ with $Z = -(-2) = 2$. Note that it is nondegenerate and unique because we have strictly positive entries on the RHS and entries representing nonbasic variables at the objective function row.

A quicker solution using dual simplex method.

Observe that that $\max z = -y$ has nonpositve coefficients. This gives rise to a nonnegative objective function row, so optimality is satisfied. This allows us to use dual simplex method.

Rewrite the LPP as

$\max z = -y$ where $-x \le -1$ and $2x-y \le 0, x,y \ge 0$.

Note that $y \ge 2x \ge 2(1) \ge 1 > 0$, so adding $x,y \ge 0$ doesn't change the problem.

\begin{array}{c|cccc|c} &x&y&s_1&s_2&A\\ \hline s_1&\fbox{-1}&0&1&0&\fbox{-1}\\ s_2&2&-1&0&1&0\\ \hline z&0&1&0&0&0 \\ \text{ratio} & \fbox0 & - \end{array}

\begin{array}{c|cccc|c} &x&y&s_1&s_2&A\\ \hline x&1&0&-1&0&1\\ s_2&0 & -1 & 2 & 1 & \fbox{-2}\\ \hline z&0&1&0&0&0 \\ \text{ratio} & & \fbox{-1} & - \end{array}

\begin{array}{c|cccc|c} &x&y&s_1&s_2&A\\ \hline x&1&0&-1&0&1\\ y&0 & 1 & -2 & -1 & 2 \\ \hline z&0&0&2&1&-2 \end{array}

Observe that we arrived at the same tableau much quicker than the usual two phase method.

• Is there a difference between this approach (multiplying the row with $-1$) and @callculus' approach of adding an artificial variable? I.e. will one approach work in some cases where the other doesn't? – Todd Sewell Feb 26 '18 at 13:07
• @ToddSewell Both approach won't affect the feasibility and optimality of the solution, and they should work without problem as long as you aren't trapped by a cycle. As you can see from my answer, adding one artificial variable add additional steps. As a result, adding two artificial variables (callculus's way) is slower than adding one (first part of my answer). Adding none is even better. – GNUSupporter 8964民主女神 地下教會 Feb 26 '18 at 13:49
• I see. So your genaral solution is to always multiply rows with a $RHS = 0$ by $-1$? – Todd Sewell Feb 26 '18 at 14:33
• @ToddSewell My "general" solution for two phase simplex is to create a slack variable (of coefficient one) with $\text{RHS} \ge 0$. That's the starting point of a simplex method. – GNUSupporter 8964民主女神 地下教會 Feb 26 '18 at 14:37