Initial basic feasible solution for LPP with 'greater than' constraints

Question

While solving a linear programming problem with n variables in m equations (n > m) using the simplex method, an initial feasible solution is found by setting n - m variables to zero. Mostly when this is done the decision variables are attributed the value of zero. I wonder how this works when the constraint is of greater than or equal to form. Because clearly 0 > a positive value doesn't make any sense. Please let me know how this method works and if my understanding is wrong.

Answer 1

The initial feasible basis obtained by setting all the decision variables to $0$ is a shortcut. It is one that we can take only when every constraint has a specific form:

• It can have the form $A_i x \le b_i$ where $b_i$ is nonnegative;
• Or the form $A_i x \ge b_i$ where $b_i$ is nonpositive;
• Or the form $A_i x = b_i$ where $b_i = 0$.

If none of those work out, then we have to use a general way of finding an initial feasible basis. These are collectively called "phase one methods", and there are multiple such methods, but the most common one uses artificial variables.

Here, we put our constraints in equational form: $Ax = b$ (with $x\ge 0$). What's more, if we have a constraint $A_i x = b_i$ with $b_i < 0$, we can change it to the constraint $-A_i x = -b_i$; after that's done, we can assume $b>0$.

Now, we change $Ax = b$ to $Ax + Ix^a = b$, where $x^a$ is a vector of nonnegative "artificial variables". We get a system in which we can take a different shortcut: we can set all the non-artificial variables to $0$, and set each $x^a_i$ to $b_i$ to get an initial feasible solution to this phase one problem. As long as the artificial variables are positive, we don't have a feasible solution to the original problem.

In the phase one problem, we minimize the sum of the artificial variables. If it hits $0$, then and only then is our feasible solution to $Ax + Ix_a = b$ also a feasible solution to $Ax = b$. If this happens, we can return to the original problem and have a feasible solution for it.

If the sum of the artificial variables never reaches $0$, that means the original problem is infeasible.