Linear Programming Duality: An Introduction to Oriented Matroids

✍ Scribed by Achim Bachem, Walter Kern

• Publisher: Springer
• Year: 1992
• Tongue: English
• Leaves: 219
• Series: Universitext
• Category: Library

✦ Synopsis

This book presents an elementary introduction to the theory of oriented matroids. The way oriented matroids are introduced emphasizes that they are the most general - and hence simplest - structures for which linear Programming Duality results can be stated and proved. The main theme of the book is duality. Using Farkas' Lemma as the basis the authors start with results on polyhedra in Rn and show how to restate the essence of the proofs in terms of sign patterns of oriented matroids. Most of the standard material in Linear Programming is presented in the setting of real space as well as in the more abstract theory of oriented matroids. This approach clarifies the theory behind Linear Programming and proofs become simpler. The last part of the book deals with the facial structure of polytopes respectively their oriented matroid counterparts. It is an introduction to more advanced topics in oriented matroid theory. Each chapter contains suggestions for further reading and the references provide an overview of the research in this field.

✦ Table of Contents

Cover......Page 1
Title......Page 2
Copyright......Page 3
Preface......Page 4
Contents......Page 6
Notation......Page 8
1 Prerequisites 7......Page 0
1.1 Sets and Relations......Page 10
1.2 Linear Algebra......Page 13
1.3 Topology......Page 17
1.4 Polyhedra......Page 18
2.1 Some Definitions......Page 22
2.2 FARKAS' Lemma for Graphs......Page 25
2.3 Subspaces Associated with Graphs......Page 27
2.4 Planar Graphs......Page 35
2.5 Further Reading......Page 38
3.1 Optimization Problems......Page 40
3.2 Recognizing Optimal Solutions......Page 43
3.3 Further Reading......Page 46
4.1 A first version......Page 48
4.2 Homogenization......Page 49
4.3 Linearization......Page 52
4.4 Delinearization......Page 54
4.5 Dehomogenization......Page 56
4.6 Further Reading......Page 57
5.1 Sign Vectors......Page 60
5.2 Minors......Page 64
5.3 Oriented Matroids......Page 66
5.4 Abstract Orthogonality......Page 69
5.5 Abstract Elimination Property......Page 70
5.6 Elementary vectors......Page 73
5.7 The Composition Theorem......Page 76
5.9 Approximation Axioms......Page 81
5.10 Proof of FARKAS' Lemma in OMs......Page 84
5.12 Further Reading......Page 86
6.1 The Dual Program......Page 92
6.2 The Combinatorial Problem......Page 97
6.3 Network Programming......Page 110
6.4 Further Reading......Page 113
7 Basic Facts in Polyhedral Theory......Page 116
7.1 MINKOWSKI's Theorem......Page 117
7.2 Polarity......Page 119
7.3 Faces of Polyhedral Cones......Page 122
7.4 Faces and Interior Points......Page 124
7.5 The Canonical Map......Page 127
7.6 Lattices......Page 130
7.7 Face Lattices of Polars......Page 132
7.8 General Polyhedra......Page 134
7.9 Further Reading......Page 145
8 The Poset (0, -<)......Page 146
8.1 Simplifications......Page 147
8.2 Basic Results......Page 152
8.3 Shellability of Topes......Page 159
8.4 Constructibility of 0......Page 167
8.5 Further Reading......Page 172
9.1 Linear Sphere Systems......Page 174
9.2 A Nonlinear OM......Page 177
9.3 Sphere Systems......Page 179
9.4 PL Ball Complexes......Page 186
9.5 Further Reading......Page 198
Bibliography......Page 200
Symbols and Expressions......Page 214
Index......Page 216

✦ Subjects

Математика;Методы оптимизации;Линейное программирование;