Understanding Two-Stage Simplex

Two-Stage Simplex is an extension of the Simplex method to cope with linear programming problems that involve inequalities of both types – ‘greater than or equal to’ and ‘less than or equal to’.
It is necessary to convert these inequalities to equations, therefore, artificial variables are introduced with the understanding that their values will be set to zero when the optimal solution is achieved.

Steps in Two-Stage Simplex

Step One involves forming the initial Simplex tableau using the linear programming problem’s objective function and constraints, with the introduction of surplus, slack, and artificial variables.
In Step Two, artificial variables are aimed to be driven out of the basis. The artificial variables form the objective function of the first stage, their coefficient being 1, and the objective is to minimize this artificial-objective function.
After the first stage, if the minimum artificial-objective function value is zero, the original problem has a feasible solution and Step Two can proceed.
If the minimum is not zero, then the original problem doesn’t have a feasible solution and the process terminates.
In Step Three the original problem’s objective function, now only involving the original variables, is aimed to be optimized, assuming the simplex tableau from the end of the first stage is feasible.

The optimal solution (if one exists) to the linear programming problem is found at the end of the second stage and is given by the current basis for the optimal feasible solution.
If an optimal solution doesn’t exist, the Simplex algorithm will determine this by not being able to improve the solution from a given iteration and cycling.