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?
Best Answer
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
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.