Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben

2020 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Linear Programming

Foundations and Extensions

verfasst von: Robert J. Vanderbei

Verlag: Springer International Publishing

Buchreihe : International Series in Operations Research & Management Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

The book provides a broad introduction to both the theory and the application of optimization with a special emphasis on the elegance, importance, and usefulness of the parametric self-dual simplex method. The book assumes that a problem in “standard form,” is a problem with inequality constraints and nonnegative variables. The main new innovation to the book is the use of clickable links to the (newly updated) online app to help students do the trivial but tedious arithmetic when solving optimization problems.

The latest edition now includes: a discussion of modern Machine Learning applications, as motivational material; a section explaining Gomory Cuts and an application of integer programming to solve Sudoku problems. Readers will discover a host of practical business applications as well as non-business applications. Topics are clearly developed with many numerical examples worked out in detail. Specific examples and concrete algorithms precede more abstract topics.

With its focus on solving practical problems, the book features free C programs to implement the major algorithms covered, including the two-phase simplex method, the primal-dual simplex method, the path-following interior-point method, and and the homogeneous self-dual method. In addition, the author provides online tools that illustrate various pivot rules and variants of the simplex method, both for linear programming and for network flows. These C programs and online pivot tools can be found on the book's website. The website also includes new online instructional tools and exercises.

Inhaltsverzeichnis

Frontmatter

Part I

Frontmatter
Chapter 1. Introduction
Abstract
This book is mostly about a subject called linear programming. Before defining what we mean, in general, by a linear programming problem, let us describe a few practical real-world problems that serve to motivate and at least vaguely to define this subject.
Robert J. Vanderbei
Chapter 2. The Simplex Method
Abstract
In this chapter we present the simplex method as it applies to linear programming problems in standard form.
Robert J. Vanderbei
Chapter 3. Degeneracy
Abstract
In the previous chapter, we discussed what it means when the ratios computed to calculate the leaving variable are all nonpositive (the problem is unbounded). In this chapter, we take up the more delicate issue of what happens when some of the ratios are infinite (i.e., their denominators vanish).
Robert J. Vanderbei
Chapter 4. Efficiency of the Simplex Method
Abstract
In the previous chapter, we saw that the simplex method (with appropriate pivoting rules to guarantee no cycling) will solve any linear programming problem for which an optimal solution exists. In this chapter, we investigate just how fast it will solve a problem of a given size.
Robert J. Vanderbei
Chapter 5. Duality Theory
Abstract
Associated with every linear program is another called its dual. The dual of this dual linear program is the original linear program (which is then referred to as the primal linear program). Hence, linear programs come in primal/dual pairs. It turns out that every feasible solution for one of these two linear programs gives a bound on the optimal objective function value for the other. These ideas are important and form a subject called duality theory, which is the topic of this chapter.
Robert J. Vanderbei
Chapter 6. The Simplex Method in Matrix Notation
Abstract
So far, we have avoided using matrix notation to present linear programming problems and the simplex method. In this chapter, we shall recast everything into matrix notation. At the same time, we will emphasize the close relations between the primal and the dual problems.
Robert J. Vanderbei
Chapter 7. Sensitivity and Parametric Analyses
Abstract
In this chapter, we consider two related subjects. The first, called sensitivity analysis (or postoptimality analysis) addresses the following question: having found an optimal solution to a given linear programming problem, how much can we change the data and have the current partition into basic and nonbasic variables remain optimal? The second subject addresses situations in which one wishes to solve not just one linear program, but a whole family of problems parametrized by a single real variable.
Robert J. Vanderbei
Chapter 8. Implementation Issues
Abstract
In the previous chapter, we rewrote the simplex method using matrix notation. This is the first step toward our aim of describing the simplex method as one would implement it as a computer program. In this chapter, we shall continue in this direction by addressing some important implementation issues.
Robert J. Vanderbei
Chapter 9. Problems in General Form
Abstract
Up until now, we have always considered our problems to be given in standard form. However, for real-world problems it is often convenient to formulate problems in the following form:
Robert J. Vanderbei
Chapter 10. Convex Analysis
Abstract
This book is mostly about linear programming. However, this subject, important as it is, is just a subset of a larger subject called convex analysis. In this chapter, we shall give a brief introduction to this broader subject. In particular, we shall prove a few of the fundamental results of convex analysis and see that their proofs depend on some of the theory of linear programming that we have already developed.
Robert J. Vanderbei
Chapter 11. Game Theory
Abstract
In this chapter, we shall study if not the most practical then certainly an elegant application of linear programming. The subject is called game theory, and we shall focus on the simplest type of game, called the finite two-person zero-sum game, or just matrix game for short.
Robert J. Vanderbei
Chapter 12. Data Science Applications
Abstract
In this chapter, we shall study a few applications of linear programming to an area of statistics called regression and to an area of machine learning called support vector machines. As a specific example for our study of regression, we shall use size and iteration-count data collected from a standard suite of linear programming problems to derive a regression estimate of the number of iterations needed to solve problems of a given size.
Robert J. Vanderbei
Chapter 13. Financial Applications
Abstract
In this chapter, we shall study some applications of linear programming to problems in quantitative finance.
Robert J. Vanderbei

Part II

Frontmatter
Chapter 14. Network Flow Problems
Abstract
Many linear programming problems can be viewed as a problem of minimizing the “transportation” cost of moving materials through a network to meet demands for material at various locations given sources of material at other locations. Such problems are called network flow problems. They form the most important special class of linear programming problems. Transportation, electric, and communication networks provide obvious examples of application areas. Less obvious, but just as important, are applications in facilities location, resource management, financial planning, and others.
Robert J. Vanderbei
Chapter 15. Applications
Abstract
In this chapter, we discuss briefly the most important applications of network flow problems.
Robert J. Vanderbei
Chapter 16. Structural Optimization
Abstract
This final chapter on network-type problems deals with finding the best design of a structure to support a specified load at a fixed set of points.
Robert J. Vanderbei

Part III

Frontmatter
Chapter 17. The Central Path
Abstract
In this chapter, we begin our study of an alternative to the simplex method for solving linear programming problems. The algorithm we are going to introduce is called a path-following method . It belongs to a class of methods called interior-point methods . The path-following method seems to be the simplest and most natural of all the methods in this class, so in this book we focus primarily on it. Before we can introduce this method, we must define the path that appears in the name of the method.
Robert J. Vanderbei
Chapter 18. A Path-Following Method
Abstract
In this chapter, we define an interior-point method for linear programming that is called a path-following method. Recall that for the simplex method we required a two-phase solution procedure.
Robert J. Vanderbei
Chapter 19. The KKT System
Abstract
The most time-consuming aspect of each iteration of the path-following method is solving the system of equations that defines the step direction vectors Δx, Δy, Δw, and Δz:
Robert J. Vanderbei
Chapter 20. Implementation Issues
Abstract
In this chapter, we discuss implementation issues that arise in connection with the path-following method.
Robert J. Vanderbei
Chapter 21. The Affine-Scaling Method
Abstract
In the previous chapter, we showed that the step direction for the path-following method can be decomposed into a linear combination of three directions: a direction toward optimality, a direction toward feasibility, and a direction toward centrality. It turns out that these directions, or minor variants of them, arise in all interior-point methods.
Robert J. Vanderbei
Chapter 22. The Homogeneous Self-Dual Method
Abstract
In Chapter 18, we described and analyzed an interior-point method called the path-following algorithm. This algorithm is essentially what one implements in practice but as we saw in the section on convergence analysis, it is not easy (and perhaps not possible) to give a complete proof that the method converges to an optimal solution. If convergence were completely established, the question would still remain as to how fast is the convergence. In this chapter, we shall present a similar algorithm for which a complete convergence analysis can be given.
Robert J. Vanderbei

Part IV

Frontmatter
Chapter 23. Integer Programming
Abstract
Many real-world problems could be modeled as linear programs except that some or all of the variables are constrained to be integers. Such problems are called integer programming problems.
Robert J. Vanderbei
Chapter 24. Quadratic Programming
Abstract
In Chapter 23, we studied a generalization of the linear programming problem in which variables were constrained to take on integer values. In this chapter, we consider a generalization of a different kind. Namely, we shall study the class of problems that would be linear programs except that the objective function is permitted to include terms involving products of pairs of variables.
Robert J. Vanderbei
Chapter 25. Convex Programming
Abstract
In the last chapter, we saw that small modifications to the primal–dual interior-point algorithm allow it to be applied to quadratic programming problems as long as the quadratic objective function is convex. In this chapter, we shall go further and allow the objective function to be a general (smooth) convex function. In addition, we shall allow the feasible region to be any convex set given by a finite collection of convex inequalities.
Robert J. Vanderbei
Backmatter
Metadaten
Titel
Linear Programming
verfasst von
Robert J. Vanderbei
Copyright-Jahr
2020
Electronic ISBN
978-3-030-39415-8
Print ISBN
978-3-030-39414-1
DOI
https://doi.org/10.1007/978-3-030-39415-8

Premium Partner

    Bildnachweise