Let's say we are working on a LPP in the following form:
\begin{equation*} \begin{split} \min \quad &z = f(x) \\[.15cm] s.a. \quad &Ax \leqslant b \\[.15cm] &x \geqslant 0 \end{split} \end{equation*} Is there any kind of restriction if we are working with a vector $b$ that has negative components? I mean, is it okay to proceed as usual when we are working with a negative $b$ vector? If not, how would we proceed in this scenario?
Thanks for any help in advance.
The simplex method does become more complicated when $b$ has negative components.
In general, the logic of the method is: start at a basic feasible solution (bfs), then move to an adjacent but better bfs, until the optimal solution is found. The key problem with this is: where do you start?
If $b \ge 0$, then the answer is easy. You start at the point $x=0$. (This is always a bfs; in the tableau, it corresponds to making all the slack variables basic variables.)
If $b$ has some negative components, then $x=0$ is no longer feasible. In that case, we don't even know if the system of inequalities $Ax \le b \land x \ge 0$ has any solutions! Finding a starting point for the simplex method is a problem just as hard as finding an optimal solution afterwards.
The usual solution is one of several two-phase simplex methods. Here, we start by creating an auxiliary linear program from the original one. The auxiliary LP is guaranteed to have a starting bfs. When solved to optimality, the result will either give us a bfs for the original LP (and then we proceed from there), or show that the original LP is infeasible.