Linear Programming Duality

Der Begriff der Dualität in der linearen Programmierung ist von zentraler Bedeutung in der kombinatorischen Optimierung. Beide Autoren haben viele Jahre auf diesem Gebiet gearbeitet. Sie geben eine elementare Einführung in die Theorie der orientierten Matroide. Dabei gelingt es ihnen, die theoretischen Grundlagen der linearen Programmierung besonders klar herauszuarbeiten und die Beweise häufig verwendeter Resultate zu vereinfachen. Das Buch enthält viele Abbildungen, und die Autoren haben alle Kapitel mit Hinweisen auf weiterführende Literatur versehen.

Linear Programming Duality is one of the cornerstones in combinatorial optimization. The book is written by two authors who have been working in the field of combinatorial optimization for many years. They give an elementary introduction to the theory of oriented matroids. Their approach clarifies the theoretical basis of Linear Programming and simplifies the proofs of standard results. The book contains numerous figures and the authors have included suggestions for further reading after each chapter.

Klappentext

The main theorem of Linear Programming Duality, relating a "pri mal" Linear Programming problem to its "dual" and vice versa, can be seen as a statement about sign patterns of vectors in complemen tary subspaces of Rn. This observation, first made by R.T. Rockafellar in the late six ties, led to the introduction of certain systems of sign vectors, called "oriented matroids". Indeed, when oriented matroids came into being in the early seventies, one of the main issues was to study the fun damental principles underlying Linear Progra.mrning Duality in this abstract setting. In the present book we tried to follow this approach, i.e., rather than starting out from ordinary (unoriented) matroid theory, we pre ferred to develop oriented matroids directly as appropriate abstrac tions of linear subspaces. Thus, the way we introduce oriented ma troids makes clear that these structures are the most general -and hence, the most simple -ones in which Linear Programming Duality results can be stated and proved. We hope that this helps to get a better understanding of LP-Duality for those who have learned about it before und a good introduction for those who have not.

Inhalt
1 Prerequisites.- 7.1 Sets and Relations.- 10.2 Linear Algebra.- 14.3 Topology.- 15.4 Polyhedra.- 2 Linear Duality in Graphs.- 2.1 Some Definitions.- 2.2 FARKAS' Lemma for Graphs.- 2.3 Subspaces Associated with Graphs.- 2.4 Planar Graphs.- 2.5 Further Reading.- 3 Linear Duality and Optimization.- 3.1 Optimization Problems.- 3.2 Recognizing Optimal Solutions.- 3.3 Further Reading.- 4 The FARKAS Lemma.- 4.1 A first version.- 4.2 Homogenization.- 4.3 Linearization.- 4.4 Delinearization.- 4.5 Dehomogenization.- 4.6 Further Reading.- 5 Oriented Matroids.- 5.1 Sign Vectors.- 5.2 Minors.- 5.3 Oriented Matroids.- 5.4 Abstract Orthogonality.- 5.5 Abstract Elimination Property.- 5.6 Elementary vectors.- 5.7 The Composition Theorem.- 5.8 Elimination Axioms.- 5.9 Approximation Axioms.- 5.10 Proof of FARKAS' Lemma in OMs.- 5.11 Duality.- 5.12 Further Reading.- 6 Linear Programming Duality.- 6.1 The Dual Program.- 6.2 The Combinatorial Problem.- 6.3 Network Programming.- 6.4 Further Reading.- 7 Basic Facts in Polyhedral Theory.- 7.1 MINKOWSKI'S Theorem.- 7.2 Polarity.- 7.3 Faces of Polyhedral Cones.- 7.4 Faces and Interior Points.- 7.5 The Canonical Map.- 7.6 Lattices.- 7.7 Face Lattices of Polars.- 7.8 General Polyhedra.- 7.9 Further Reading.- 8 The Poset (O, ?).- 8.1 Simplifications.- 8.2 Basic Results.- 8.3 Shellability of Topes.- 8.4 Constructibility of O.- 8.5 Further Reading.- 9 Topological Realizations.- 9.1 Linear Sphere Systems.- 9.2 A Nonlinear OM.- 9.3 Sphere Systems.- 9.4 PL Ball Complexes.- 9.5 Further Reading.