Simplex algorithm with initial negative slack variables

Question

I have the following LP problem:

$$\begin{equation*} \begin{aligned} min. & & z = 2x+3y\\ \text{s.t. } & & x & \le 3\\ & & x & \ge 3\\ & & -x + 2y & \le -1\\ & & x, y & \ge 0 \end{aligned} \end{equation*}$$

I know this that the 2 first constraints are equivalent to $x = 3$, but I got some kind of theorotical question... If I add slack variables, I get the following:

$$\begin{equation*} \begin{aligned} min. & & z = 2x+3y\\ \text{s.t. } & & x + s_1 & = 3\\ & & -x + s_2 & = -3\\ & & -x + 2y + s_3 & = -1\\ & & x, y, s_1, s_2, s_3 & \ge 0 \end{aligned} \end{equation*}$$

Which gives me the following augmented matrix: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 0 & 3\\ 0 & -1 & 0 & 0 & 1 & 0 & -3\\ 0 & -1 & 2 & 0 & 0 & 1 & -1\\ \hline 1 & -2 & -3 & 0 & 0 & 0 & 0 \end{bmatrix}

From there, I have the following situation (which causes me some troubles... ):

1. There are no positive values in the objective row, so I should get the optimal solution.
2. The optimal solution includes only slack variables ($x=y=0$), but $s_2$ and $s_3$ are negative, actually this is not a feasible solution!

Here's my « question »: What should I do when facing this case?

As far as I know, I have a unfeasible solution if, when I pick a pivot column, I got only negative coefficients on it. Since I cannot pick one here, I don't know what to do...

Answer 1

I assume the variables are implicitly non-negative.

You initial basis is not primal feasible nor dual feasible. You need a 2 step simplex algorithm to get a feasible initial basis. See for example section 2 of http://math.jacobs-university.de/oliver/teaching/iub/spring2007/cps102/handouts/linear-programming.pdf

Answer 2

First of all you can combine the first two constraints to one constraint.

$\texttt{first and second constraint}$

$x\leq 3 $

$x\geq 3$

Combining the two constraints:

$x=3$

$\Rightarrow x^*=3$

Therefore the objective function is

$\texttt{min} \ \ z = 2\cdot 3+3y=6+3y$

$\texttt{third constraint}$

$-3 + 2y \leq -1 \quad \quad |+3$

$2y\leq 2$

$y\leq 1$

Since the objective function has to be minimized and the coefficient of the y variable is positive, y has to be as small as possible. Therfore $y^*=0$, because $y\geq 0$.

And $z^*=6+0=6$