[Math] Simplex algorithm with initial negative slack variables

linear programmingsimplex

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…

Best Answer

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

Related Question