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

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?

• Welcome to OR.SE. I suggest that you use MathJax formatting (check here) for your formulation rather than coding style. Now about your problem: Are you trying to solve this problem with primal simplex or dual simplex? If primal, have you read around about 2-phase method? – EhsanK Jul 13 '19 at 5:38
• Thank you EhsanK . I will edit this post using MathJax formatting.I have used Dual simplex to solve this problem. – Kavishka Gamage Jul 13 '19 at 7:15
• @codekcg so, when you solved your problem, did you answer your own question? If so, you may retract the question or add an answer and edit the question so that others can learn from you – Marco Lübbecke Jul 13 '19 at 9:43
• @MarcoLübbecke above I have tried to answer but I get stucked after getting a negative value for non basic variable(x4).So I don't know how to solve this further. – Kavishka Gamage Jul 13 '19 at 16:36

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$$).