Linear Programming Duality

Inhaltsverzeichnis

• 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.