An artificial-free simplex-type algorithm for general LP models

The simplex algorithm requires additional variables (artificial variables) for solving linear programs which lack feasibility at the origin point. Some students, however, particularly non mathematics majors, have difficulty understanding the intuitive notion of artificial variables. A new general purpose solution algorithm obviates the use of artificial variables. The algorithm consists of two phases. Phase 1 searches for a feasible segment of the boundary hyper-plane (a face of feasible region or an intersection of several faces) by using rules similar to the ordinary simplex. Each successive iteration augments the basic variable set, BVS, by including another hyper- plane, until the BVS is full, which specifies a feasible vertex. In this phase, movements are on faces of the feasible region rather than from a vertex to a vertex. This phase terminates successfully (or indicates the infeasibility of the problem) with a finite number of iterations, which is at most equal to the number of constraints. The second phase uses exactly the ordinary simplex rules (if needed) to achieve optimality. This unification with the simplex method is achieved by augmenting the feasible BVS, which is always initially considered empty at the beginning of Phase 1. The algorithm working space is the space of the original (decision, slack and surplus) variables in the primal problem. It also provides a solution to the dual problem with useful information. Geometric interpretation of the strategic process and some illustrative numerical examples are also presented.