Skip to Main Content
Linear Programming and Resource Allocation Modeling
book

Linear Programming and Resource Allocation Modeling

by Michael J. Panik
November 2018
Intermediate to advanced content levelIntermediate to advanced
448 pages
12h 24m
English
Wiley
Content preview from 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 images 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

images

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 XB) 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, ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Model Building in Mathematical Programming, 5th Edition

Model Building in Mathematical Programming, 5th Edition

H. Paul Williams
Fundamentals of Deep Learning, 2nd Edition

Fundamentals of Deep Learning, 2nd Edition

Nithin Buduma, Nikhil Buduma, Joe Papa

Publisher Resources

ISBN: 9781119509448Purchase book