When applying the simplex algorithm to a linear program with constraints of the form $Ax \le b$, as a first step, one converts it to a so called slack form $Ax = b$ by introducing slack variables to each constraint. After that transformation has been applied the slack variables become the initial set of basic variables and the initial non-basic variables are the original variables $x$.
If, on the other hand, the original linear program already has constraints of the form $Ax = b$, one could convert them to constraints of the form $Ax \le b$ by simply joining $Ax \le b$ with $-A \le -b$, which doubles the number of constraints. Then when applying the simplex algorithm you could return to $Ax = b$ constraints (with twice as many slack variables and constraints).
My question is, is there a way to apply the simplex algorithm directly to a linear program of the form $Ax = b$, without taking that indirect route via $Ax \le b$ and $-A \le -b$? If so, how do you initially parition the variables into basic and non-basic variables, and get to the initial basic feasible solution?
Best Answer
The approach prescribed for original equality constraints in the linear program in CLRS (https://en.wikipedia.org/wiki/Introduction_to_Algorithms) Chapter 29 is indeed to introduce opposing inequality constraints (ie $\vec\alpha_i \cdot \vec x = b_i$ becomes the two opposing constraints $\vec\alpha_i \cdot \vec x \le b_i$ and $-\vec\alpha_i \cdot \vec x \le -b_i$)
The alternative approach of artificial variables (not mentioned in CLRS) is essentially to augment a new variable $k_i \ge 0$ on each equality constraint $\vec\alpha_i \cdot \vec x = b$ changing it to an inequality constraint $\vec\alpha_i \cdot \vec x +k_i \le b$, then make a first pass of the simplex algorithm to maximize $\sum - k_i$. If the resulting solution has all $k_i = 0$ (nonbasic) then they can be eliminated from the linear program, and the resulting solution is then the initial solution for a second pass (without the artificial variables) of the simplex algorithm maximizing the original cost function $\sum c_i x_i$. Otherwise, if the first pass fails (a $k_i > 0$) then the linear program is infeasible.
I was actually searching for a third alternative that is simpler and more computationally efficient than either of the above, but I have failed to find any. Given no such solution is mentioned in CLRS I assume it either doesn't exist or is not known.