1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Then show the steps till your case came up. $\endgroup$ – callculus Oct 8 '15 at 6:56
0
$\begingroup$

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.

Your LPP

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.

$\endgroup$

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.