Part of the book series:Texts in Computer Science ((TCS))
3651Accesses
Abstract
Linear programming (LP) problems occur in a diverse range of real-life applications in economic analysis and planning, operations research, computer science, medicine, and engineering. In such problems, it is known that any minima occur at the vertices of the feasible region and can be determined through a ‘brute-force’ or exhaustive approach by evaluating the objective function at all the vertices of the feasible region. However, the number of variables involved in a practical LP problem is often very large and an exhaustive approach would entail a considerable amount of computation.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Starting from 10 chapters or articles per month
- Access and download chapters and articles from more than 300k books and 2,500 journals
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 10295
- Price includes VAT (Japan)
- Hardcover Book
- JPY 12869
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Explore related subjects
Discover the latest articles, books and news in related subjects, suggested using machine learning.Notes
- 1.
A matrix is said to be sparse if only a relatively small number of its elements are nonzero.
References
G. B. Dantzig, “Programming in a linear structure,” inComptroller. Washington, DC: USAF, 1948.
G. B. Dantzig,Linear Programming and Extensions. Princeton, NJ: Princeton University Press, 1963.
P. E. Gill, W. Murray, and M. H. Wright,Numerical Linear Algebra and Optimization, Vol. I. Reading: Addison-Wesley, 1991.
R. Saigal,Linear Programming — A Modern Integrated Analysis. Norwell, MA: Kluwer Academic, 1995.
G. H. Golub and C. F. Van Loan,Matrix Computations, 4th ed. Baltimore, MD: Johns Hopkins University Press, 2013.
R. G. Bland, “New finite pivoting rules for the simplex method,”Math. Operations Research, vol. 2, pp. 103–108, 1977.
J. E. Dennis, Jr. and R. B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Philadelphia, PA: SIAM, 1996.
W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery,Numerical Recipes in C, 2nd ed. Cambridge, UK: Cambridge University Press, 1992.
V. Klee and G. Minty, “How good is the simplex method?” inInequalities, O. Shisha, Ed. New York: Academic Press, 1972, pp. 159–175.
M. H. Wright, “Interior methods for constrained optimization,”Acta Numerica, Cambridge University Press, vol. 1, pp. 341–407, 1992.
Author information
Authors and Affiliations
Department of Electrical and Computer Engineering, University of Victoria, Victoria, BC, Canada
Andreas Antoniou & Wu-Sheng Lu
- Andreas Antoniou
Search author on:PubMed Google Scholar
- Wu-Sheng Lu
Search author on:PubMed Google Scholar
Corresponding author
Correspondence toAndreas Antoniou.
Rights and permissions
Copyright information
© 2021 Springer Science+Business Media, LLC, part of Springer Nature
About this chapter
Cite this chapter
Antoniou, A., Lu, WS. (2021). Linear Programming Part I: The Simplex Method. In: Practical Optimization. Texts in Computer Science. Springer, New York, NY. https://doi.org/10.1007/978-1-0716-0843-2_11
Download citation
Published:
Publisher Name:Springer, New York, NY
Print ISBN:978-1-0716-0841-8
Online ISBN:978-1-0716-0843-2
eBook Packages:Computer ScienceComputer Science (R0)
Share this chapter
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative