The Artificial Variable Algorithm

With knowledge of the primal simplex and the dual simplex algorithms, it is possible to solve two large classes of linear programming problems. The first class contains those problems whose constraints are all inequalities and admit an easy primal feasible basis (the identity matrix I). An equivalent way to regard these problems is to say that the origin of the space (the zero point in the Cartesian coordinate system of the output space) belongs to the feasible region. For such problems, a primal basic feasible solution can be established simply by inspection and, therefore, we can find their optimal solution by immediately applying the primal simplex algorithm. The second class contains those problems whose constraints are inequalities and satisfy the primal optimality criterion (equivalently, the dual feasibility criterion). These problems can be solved by an application of the dual simplex algorithm. It is important to notice that the use of either simplex algorithm requires the availability of an explicit basic feasible solution to either problem. Let us recall that primal feasibility means a nonnegative vector x that satisfies all the primal constraints. Analogously, dual feasibility means that the dual solution is nonnegative in all its components (z _j − c _j ). If neither of these conditions are satisfied, neither simplex algorithm can be applied directly to the LP problem.