AN ARTIFICIAL-FREE SIMPLEX-TYPE ALGORITHM FOR GENERAL LP MODELS

The simplex algorithm requires additional variables (artificial variab les) for solving linear programs which lack feasibility at the origin point. Some students, however, particularly nonmathematics majors, hav e difficulty understanding the intuitive notion of artificial variable s. A new general purpose solution algorithm obviates the use of artifi cial variables. The algorithm consists of two phases. Phase 1 searches for a feasible segment of the boundary hyper-plane (a face of feasibl e region or an intersection of several faces) by using rules similar t o the ordinary simplex. Each successive iteration augments the basic v ariable set, BVS, by including another hyper-plane, until the BVS is f ull, which specifies a feasible vertex. In this phase, movements are o n 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 equa l to the number of constraints. The second phase uses exactly the ordi nary simplex rules (if needed) to achieve optimality. This unification with the simplex method is achieved by augmenting the feasible BVS, w hich is always initially considered empty at the beginning of Phase 1. The algorithm working space is the space of the original (decision, s lack and surplus) variables in the primal problem. It also provides a solution to the dual problem with useful information. Geometric interp retation of the strategic process with some illustrative numerical exa mples are also presented.