Linear Programming Duality: An Introduction to Oriented Matroids

This book presents an elementary introduction to the theoryof oriented matroids. The way oriented matroids are intro-duced emphasizes that they are the most general - and hencesimplest - structures for which linear Programming Dualityresults can be stated and proved. The main theme of the bookis duality. Using Farkas' Lemma as the basis the authors start withre-sults on polyhedra in Rn and show how to restate the essenceof the proofs in terms of sign patterns of oriented ma-troids. Most of the standard material in Linear Programmingis presented in the setting of real space as well as in themore abstract theory of oriented matroids. This approachclarifies the theory behind Linear Programming and proofsbecome simpler. The last part of the book deals with the facial structure ofpolytopes respectively their oriented matroid counterparts. It is an introduction to more advanced topics in orientedmatroid theory. Each chapter contains suggestions for furt-herreading and the references provide an overview of theresearch in this field.