2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ An artificial variable is necessary for the second constraint! Why not? $\endgroup$ – callculus Feb 24 '18 at 18:28
  • $\begingroup$ @callculus I thought you added artificial variables to create your initial feasible solution? $\endgroup$ – Todd Sewell Feb 24 '18 at 18:30
  • $\begingroup$ You always introduce artificial variables for equalities and $\geq$-constraints. $\endgroup$ – callculus Feb 24 '18 at 18:31
  • $\begingroup$ @callculus Ah, that solved my problem, thanks! Is there an enumeration of the full rules somewhere? $\endgroup$ – Todd Sewell Feb 24 '18 at 18:39
  • $\begingroup$ 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. $\endgroup$ – callculus Feb 24 '18 at 18:59
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Todd Sewell Feb 26 '18 at 13:07
  • $\begingroup$ @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. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 26 '18 at 13:49
  • $\begingroup$ I see. So your genaral solution is to always multiply rows with a $RHS = 0$ by $-1$? $\endgroup$ – Todd Sewell Feb 26 '18 at 14:33
  • $\begingroup$ @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. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 26 '18 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.