# General question about new objective function W using the simplex method

In regards to the two-phase simplex method; When creating a new objective function that consists the sum of the constraint(s) with artificial variables, I am told that if the Min value of (wmin) w is >0 it is infeasible and when w(min)=0 we can discard w and move onto phase 2. However what if w(min)<0? I found this to be the case when trying to solve

Maximise: z=x1+x2
Subject to: x2<=8
-x1+x2>=-4
x1+x2<=12

• Then show the steps till your case came up. – callculus Oct 8 '15 at 6:56

In the first phase of the two-phase method, we add non-negative artificial variables, so $w_{min} < 0$ is impossible. Your example can't illustrate the problem that you raised.

I'll modify your sample LPP so that I can answer your question about the two-phase method by giving you the motivation to add $w$. You may skip the next section to my modified problem.

To find a basic feasible solution to your problem, we transform it into the standard form.

\begin{array}{ccccc} \max &z=&x_1&+x_2 & \\ \text{s.t.}& & & \phantom{+}x_2 &\le 8 \\ & & -x_1&+x_2&\ge-4 \\ & & x_1&+x_2&\le12 \\ \end{array}

Note that the slack/surplus variables $s_1,s_2,s_3$ are non-negative.

\begin{array}{ccclc} \max &z=&x_1&+x_2 & \\ \text{s.t.}& & & \phantom{+}x_2 + s_1 &= 8 \\ & & -x_1&+x_2 - s_2&=-4 \\ & & x_1&+x_2+s_3&= 12 \\ & & & s_1,s_2,s_3 &\ge 0 \end{array}

We'll have no difficulty in writing the simplex tableau of this problem.

\begin{array}{ccclc} \max &z=&x_1&+x_2 & \\ \text{s.t.}& & & \phantom{+}x_2 + s_1 &= 8 \\ & & x_1&-x_2 + s_2&=4 \\ & & x_1&+x_2+s_3&= 12 \\ & & & s_1,s_2,s_3 &\ge 0 \end{array}

\begin{array}{rrrrrr|l} & x_1 & x_2 & s_1 & s_2 & s_3 & \\ \hline s_1 & 0 & 1 & 1 & 0 & 0 & 8 \\ s_2 & 1 & -1 & 0 & 1 & 0 & 4 \\ s_3 & 1 & 1 & 0 & 0 & 1 & 12 \\ \hline & -1 & -1 & 0 & 0 & 0 & 0 \\ \end{array}

We see that $(s_1,s_2,s_3)=(8,4,12)$ is a basic feasible solution, so the two-phase method is not needed. That why callculus asks you to show the steps.

## Modified LPP

To let you see that why $w_{min}<0$ is impossible, I changed the '$\ge$' sign in the second constraint to '$\le$'.

\begin{array}{ccccc} \max &z=&x_1&+x_2 & \\ \text{s.t.}& & & \phantom{+}x_2 &\le 8 \\ & & -x_1&+x_2&\color{red}{\le}-4 \\ & & x_1&+x_2&\le12 \\ \label{LPP} \tag{*} \end{array}

To apply the simplex algorithm, we first need a basic feasible solution, which is difficult to guess especially for LPP having lots of decision variables and constraints. Thus, we add slack/surplus variables and transform all inequalities into equalities to make it easier.

\begin{array}{cccll} \color{grey}{\max} &\color{grey}{z=}&\color{grey}{x_1}&\color{grey}{+x_2} & \text{we don't care about this}\\ \text{s.t.}& & & \phantom{+}x_2 + s_1 &= 8 \\ & & -x_1&+x_2 + s_2&=-4 \\ & & x_1&+x_2+s_3&= 12 \\ & & & s_1,s_2,s_3 &\ge 0 \end{array}

### Why add $w$, and why $w$ need to be non-negative?

Since in the first phase, we aim at finding a feasible solution to the LPP, we don't care about the optimality. If we dropped the last constraint $s_1,s_2,s_3\ge0$, the most obvious solution would be $x_1=x_2=0$, $s_1=8$, $\color{red}{s_2=-4}$, $s_3=12$. (I used past sentence here like "If I were you, ..." to indicate the impossibility of the condition.)

(For a computer,) a possible way to get a feasible solution is to add an (non-negative) artificial variable $w(=4)$ to the second constraint, then use pivot operations (something that a machine can do) to reduced it to $w=0$ (so that $w$ vanishes).

\begin{array}{cccll} \color{grey}{\max} &\color{grey}{z=}&\color{grey}{x_1}&\color{grey}{+x_2} & \text{we don't care about this}\\ \text{s.t.}& & & \phantom{+}x_2 + s_1 &= 8 \\ & & x_1&-x_2 - s_2 \color{red}{+w}&=4 \\ & & x_1&+x_2+s_3&= 12 \\ & & & s_1,s_2,s_3 \color{red}{,w} &\ge 0 \end{array}

Initially, $w=4$, and we try to make $w=0$. (i.e. "minimize" $w$).

\begin{array}{cccll} \min &z=&\color{red}w& & \text{we do care this}\\ \text{s.t.}& & & \phantom{+}x_2 + s_1 &= 8 \\ & & x_1&-x_2 - s_2 \color{red}{+w}&=4 \\ & & x_1&+x_2+s_3&= 12 \\ & & & s_1,s_2,s_3 \color{red}{,w} &\ge 0 \end{array}

To let others understand that how the $w$ can be discarded when it equals zero, I'll do the pivot operations here.

\begin{equation*} \begin{array}{rrrrrrr|l} & x_1 & x_2 & s_1 & s_2 & s_3 & w & \\ \hline s_1 & 0 & 1 & 1 & 0 & 0 & 0 & 8 \\ w & 1 & -1 & 0 & -1 & 0 & 1 & 4 \\ s_3 & 1 & 1 & 0 & 0 & 1 & 0 & 12 \\ \hline & 0 & 0 & 0 & 0 & 0 & -1 & 0 \\ \end{array} \end{equation*}

Make it a simplex tableau.

\begin{equation*} \begin{array}{rrrrrrr|l} & x_1 & x_2 & s_1 & s_2 & s_3 & w & \\ \hline s_1 & 0 & 1 & 1 & 0 & 0 & 0 & 8 \\ w & 1^* & -1 & 0 & -1 & 0 & 1 & 4 \\ s_3 & 1 & 1 & 0 & 0 & 1 & 0 & 12 \\ \hline & 1 & -1 & 0 & -1 & 0 & 0 & 4 \\ \end{array} \end{equation*}

\begin{equation*} \begin{array}{rrrrrrr|l} & x_1 & x_2 & s_1 & s_2 & s_3 & w & \\ \hline s_1 & 0 & 1 & 1 & 0 & 0 & 0 & 8 \\ x_1 & 1 & -1 & 0 & -1 & 0 & 1 & 4 \\ s_3 & 0 & 2 & 0 & 2 & 1 & -1 & 8 \\ \hline & 0 & 0 & 0 & 0 & 0 & -1 & 0 \\ \end{array} \end{equation*}

Therefore, $(x_1,x_2,s_1,s_2,s_3)=(4,0,8,0,8)$ is a basic feasible solution to the original LPP $\eqref{LPP}$. Here, $w=0$ can be discarded. In fact, in the last simplex tableau, the column $w$ can be omitted since it will never enter the basis again.

Now, it is clear why $w_{min} > 0$ implies that the feasible region is empty.