×

zbMATH — the first resource for mathematics

Linear programming duality: an introduction to oriented matroids. (English) Zbl 0757.90050
Universitext. Berlin: Springer-Verlag. 216 p. (1992).
In the same sense as matroids describe abstractly the combinatorial background of linear independence, oriented matroids reveal the combinatorial structure underlying linear programming duality. This textbook develops the theory of oriented matroids from the viewpoint of linear programming and polyhedra.
The authors start with a discussion of various versions of the Farkas Lemma, both in the framework of linear algebra and for directed graphs. This discussion leads to the notion of oriented matroids. It is shown what orthogonality, the elimination property and the Farkas lemma mean in this abstract combinatorial setting. Then the authors elaborate that linear programming duality is essential a matter of oriented matroids. As a second application of oriented matroids various properties of polyhedra are studied in this general framework. A further chapter of the book discusses the relations between oriented matroids and partially ordered sets. Finally topological realizations of oriented matroids are discussed, in particular examples for nonlinear oriented matroids are provided.
Reviewer: R.E.Burkard (Graz)

MSC:
90C05 Linear programming
90C27 Combinatorial optimization
05B35 Combinatorial aspects of matroids and geometric lattices
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
PDF BibTeX XML Cite