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… ):
- There are no positive values in the objective row, so I should get the optimal solution.
- 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