Linear Programming and Resource Allocation Modeling

4Computational Aspects of Linear Programming

4.1 The Simplex Method

We noted in the previous chapter that the region of feasible solutions has a finite number of extreme points. Since each such point has associated with it a basic feasible solution (unique or otherwise), it follows that there exists a finite number of basic feasible solutions. Hence, an optimum solution to the linear programming problem will be contained within the set of basic feasible solutions to How many elements does this set possess? Since a basic feasible solution has at most m of n variables different from zero, an upper bound to the number of basic feasible solutions is

i.e. we are interested in the total number of ways in which m basic variables can be selected (without regard to their order within the vector of basic variables X_B) from a group of n variables. Clearly for large n and m it becomes an exceedingly tedious task to examine each and every basic feasible solution. What is needed is a computational scheme that examines, in a selective fashion, only some small subset of the set of basic feasible solutions. Such a scheme is the simplex method (Dantzig 1951). Starting from an initial basic feasible solution, this technique systematically proceeds to alternative basic feasible solutions and, ...