An Alternative to the Simplex Method for Solving Linear Programming Problems: A Managerial Perspective
Lev, Benjamin, Kowalski, Krzysztof, International Journal of Management
The objective of this paper is to develop a simpler alternative to the widely-used Simplex Method for solving linear programming problems, from the perspective of practicing managers. It allows bounded variables where the lower and upper bounds could be negative or positive, therefore eliminating the need for introducing additional variables for the purpose of preserving non-negativity. The variables upper bounds do not require additional constraints. The inequality constraints are handled through slack/surplus variables. In contrast to the Simplex Method there is no need for substituting variables and all operations are performed only on the original equations. This method can not only form the basis for more efficient computer programs, but can also enable linear programming problems to be more easily taught to a larger audience than at present, that includes practicing managers.
Linear Programming (LP) problems are the most commonly formulated problems in Operations Research and Management Science (OR/MS). Their wide application makes them a subject of an extensive research resulting in a development of very efficient computer programs designed to find the optimal solution. Most of those codes are based on the Simplex Method developed over the last 50 years. LP is usually introduced at the university undergraduate level and in some cases graduate level mostly due to the fact that the Simplex Method is complex and may require matrix algebra. The main goal of the authors is to attract practitioners outside OR/MS and to simplify the solution technique. The Simplex theory, while excellent for commercial use is very awkward for class room demonstration especially when solving the problem manually. It requires a formulation of non-negative variables at a cost of adding constraints and variables (slack, surplus, artificial) which eventually increase the size of the problem. The Simplex requires updating the coefficient matrix and often requires inverting the matrix. An error is carried further into subsequent iterations. Such is not the case in the proposed method. All iterations are performed on the original set of equations and any error corrects itself in the next iteration.
2. The LP Problem
LP is an optimization problem with a linear objective function and a set of linear constraints. The theory behind LP can be found in many OR/MS text books; see for example Hillier and Lieberman [1, 3, 4, and 5].
Equation (2) can also represent relaxed constraints. In such case the equality sign is replaced with ≤ or ≥ inequality symbol.
Notice that there is no restriction on the x^sup min^^sub j^ and x^sup max^^sub j^ values, both can be negative, zero or positive.
Definitions: A loose variable is at value not equal to its bounds, i.e. to x^sup min^^sub j^ or to x^sup max^^sub j^ while a tight variable is equal to its bounds, i.e. to x^sup min^^sub j^ or to x^sup max^^sub j^. x^sub j^ is loose if x^sup min^^sub j^ < x^sub j^ < x^sup max^^sub j^ and x^sub j^ is tight if x^sub j^ = x^sup min^^sub j^ or if x^sub j^ = x^sup max^^sub j^.
3. Description of the new procedure
The proposed method is based on the principle of linearity, including an ?-m degree of freedom for ? variables, m constraints in an m ? ? set of linear equations. First step is finding an initial feasible solution, not necessarily basic. This can be done using any of the many available methods in OR/MS basic textbooks. In the next step m+1 loose variables are selected for analysis. Of those one variable will be changed (increased or decreased) by one unit from the originally assigned value and the remaining m variables are adjusted/computed accordingly to comply with the constraints; and a new Z value is computed. Simultaneously all the rates of change for the m variables are recorded. Tracking the Z value in the improved direction we analyze the changes in all variables to identify the one which reaches its bound first. …