Simplex: LP with equality constraints : do I need slack variables?

Question

I am confused about simplex method : I have read from various resources that I need my LP to be in standard form. Then when we have the standard form, we introduce slack variables to turn inequality constraints into equations.
But what if my initial maximisation problem has only equality constraints and I am given this order : "initially start with base $(x_3, x_4)$ " In my objective function there is no $x_3, x_4$ (so these are 0's in the row corresponding to objective function).
My question is why bother turn equations (constraints) into inequalities when I will turn inequalities back to equalities by using slacks?

Answer 1

We bother with adding slack variables into the constraints of a model to ensure there exists a basic variable in that constraint for Simplex to use.

If we are given a model that either has $\ge$ or $=$ initial constraints, we must use artificial variables to solve it. We bother with this artificial variable approach so that we have a starting, feasible solution for us to use the Simplex algorithm.

For $\ge$ constraints, like this one:

$$x_1+x_2+x_3\ge293$$

We would standardize it as such:

$$x_1+x_2+x_3-e_1+a_1=293$$

Where $e_1$ is the “excess” variables that shaves off the extra amount on the left-hand-side, and the artificial variable $a_1$ ensures we have a basic variable for that row.

For $=$ constraints, like this one:

$$x_1+x_2+x_3=9875$$

We would standardize it as such:

$$x_1+x_2+x_3+a_2=9875$$

to ensure we have a basic variable for the row for the Simplex method.

---

It is often easier to learn from an example. Suppose we have the following model:

$$min\quad z=-x_1+x_2-x_3+x_4$$ $$\text{Subject to: }\qquad\qquad\qquad\qquad\qquad\qquad$$ $$-x_1+x_2+x_3-x_4=4$$ $$2x_1-x_2+x_3=3$$ $$x_2+x_4=8$$ $$x_1,x_2,x_3\ge0$$

We’ll standardize our model using the Big-M method as such:

$$\min\quad z+x_1-x_2+x_3-x_4-M(a_1+a_2+a_3)=0$$ $$\text{Subject to: }\qquad\qquad\qquad\qquad\qquad\qquad$$ $$-x_1+x_2+x_3-x_4+a_1=4$$ $$2x_1-x_2+x_3+a_2=3$$ $$x_2+x_4+a_3=8$$ $$x_1,x_2,x_3, a_1,a_2,a_3\ge0$$

With $M$ being the “largest” number in $\Bbb R$. We choose $M$ to have this property to ensure that Simplex will attempt to remove the artificial variables from the basis. Thus, for Maximization problems we subtract $M$ from the objective function to “harm” the model into a bad solution if it keeps an artificial variable, and in a Minimization problem we add $M$ to the objective function to do the exact same thing. If at any point Simplex terminates, and the there exists a $M$ in the objective function output, then the model is deemed infeasible.

This model will look like the following in our initial tableau: \begin{array} {|c|c|} \hline BV & z & x_1 & x_2 & x_3 & x_4 & a_1 & a_2 & a_3 & RHS & \text{Ratio Test} \\ \hline z & 1 & 1 & -1 & 1 & -1 & -M & -M & -M & 0 & - \\ ? & 0 & -1 & 1 & 1 & -1 & 1 & 0 & 0 & 4 & - \\ ? & 0 & 2 & -1 & 1 & 0 & 0 & 1 & 0 & 3 & - \\ ? & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 8 & - \\ \hline \end{array}

Of course, we’ll need to solve for our initial basic variables ($a_1, a_2$ and $a_3$) as such:

\begin{array} {|c|c|} \hline BV & z & x_1 & x_2 & x_3 & x_4 & a_1 & a_2 & a_3 & RHS & \text{Ratio Test} \\ \hline z & 1 & M+1 & M-1 & 2M+1 & -1 & 0 & 0 & 0 & 15M & - \\ a_1 & 0 & -1 & 1 & 1 & -1 & 1 & 0 & 0 & 4 & 4 \\ a_2 & 0 & 2 & -1 & 1 & 0 & 0 & 1 & 0 & 3 & 3 \\ a_3 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 8 & \infty \\ \hline \end{array}

Our first pivot will be the $x_3$ column with the $a_2$ row. However, we’ll leave this as an exercise for the reader such that they will get a better understanding, and appreciation, on artificial variables with the Simplex Method.

To double check the final answer:

$$z^*=2$$ $$x_1^*=0$$ $$x^*_2=3$$ $$x_3^*=6$$ $$x_4^*=5$$

In addition, there exists multiple solutions of which all will have $z^*=2$.