Having negative value for non basic variable gives a infeasible solution in simplex method?

Question

I try to solve the following linear program with the simplex method:

$$ \begin{alignedat}{4} \max & \quad & x_1 & {}-{} & 2x_2\\ \text{subject to} & & & & x_2 & \le & ~5 \\ & & x_1 & {}-{} & x_2 & \ge & 2 \\ & & x_1 & & & \ge & 0 \\ & & & & x_2 & \ge & 0 \\ \end{alignedat} $$

Convert to standard form:

$$ \begin{alignedat}{4} \max & \quad & x_1 & {}-{} & 2x_2\\ \text{subject to} & & & & x_2 & \le & 5 \\ & {}-{} & x_1 & {}+{} & x_2 & \le & ~-2 \\ & & x_1 & & & \ge & 0 \\ & & & & x_2 & \ge & 0 \\ \end{alignedat} $$

Convert to slack form:

$$ \begin{alignedat}{4} z & = & 0 & {}+{} & x_1 & {}-{} & 2x_2\\ x_3 & = & 5 & & & {}-{} & x_2\\ x_4 & = & ~-2 & {}+{} & x_1 & {}-{} & x_2\\ \end{alignedat} $$

The basic solution is $(x_1,x_2,x_3,x_4) = (0,0,5,-2)$.

Can I find an optimal solution here? If not, why not?

Answer 1

From the slack form we can observe two things about your starting point $(x_1,x_2) = (0,0)$.

1. The starting point is not primal feasible. This follows from the fact that not all variables $x_1$, $x_2$, $x_3$, $x_4$ are non-negative ($x_4 < 0$).
2. The starting point is not dual feasible. This follows from the fact that not all variable coefficients in the $z$-row are non-positive ($x_1$ has coefficient $1 > 0$).

This means that before you can use primal or dual simplex, you first have to find a primal or dual feasible solution. You can do this with the Big M method or with the two phase simplex method.

You can use the following very helpful site to see all the simplex steps for your problem:

• Link for dual simplex method.
• Link for primal simplex with Big M method.
• Link for primal simplex with two phase method.

The first link will tell you that the initial solution is indeed dual infeasible. The other links will show that the problem is actually unbounded, and does not have a solution.