Linear Programming

Linear programming is a relatively modern branch of Mathe­ matics, which is a result of the more scientific approach to management and planning of the post-war era. The purpose of this book is to present a mathematical theory of the subject, whilst emphasising the applications and the techniques of solution. An introduction to the theory of games is given in chapter five and the relationship between matrix games and linear programmes is established. The book assumes that the reader is familiar with matrix algebra and the background knowledge required is covered in the book, Linear Equations by P.M. Cohn, of this series. In fact the notation used in this text conforms with that intro­ duced by Cohn. The book is based on a course of about 18 lectures given to Mathematics and Physics undergraduates. Several examples are worked out in the text and each chapter is followed by a set of examples. I am grateful to my husband for many valuable suggestions and advice, and also to Professor W. Ledermann, for encourag­ ing me to write this book.

One: Convex Sets.- 1. Convex hulls, polytopes and vertices.- 2. Basic solutions of equations.- 3. Theorem of the separating hyperplane.- 4. Alternative solutions of linear inequalities 10 Exercises.- Two: The Theory of Linear Programming.- 1. Examples and classes of linear programmes.- 2. Fundamental duality theorem.- 3. Equilibrium theorems.- 4. Basic optimal vectors.- 5. Graphical method of solution.- Exercises.- Three: The Transportation Problem.- 1. Formulation of problem and dual.- 2. Theorems concerning optimal solutions.- 3. Method of solution with modifications for degeneracy.- 4. Other problems of transportation type.- Exercises.- Four: The Simplex Method.- 1. Preliminary discussion and rules.- 2. Theory of the simplex method.- 3. Further techniques and extensions.- Exercises.- Five: Game Theory.- 1. Two-person zero-sum games.- 2. Solution of games: saddle points.- 3. Solution of games: mixed strategies.- 4. Dominated and essential strategies.- 5. Minimax theorem.- 6. Solution of matrix games by simplex method.- Exercises.- Suggestions for Further Reading.- Solutions to Exercises.