| |
| |
| Foreword | |
| |
| |
| Preface | |
| |
| |
| |
| Linear Programs | |
| |
| |
| Introduction | |
| |
| |
| |
| Sample Linear Programs | |
| |
| |
| |
| A Production Problem | |
| |
| |
| |
| A Diet Problem | |
| |
| |
| |
| A Transportation Problem | |
| |
| |
| |
| An Informal Algorithm | |
| |
| |
| |
| Graphical Representation | |
| |
| |
| |
| Tableau Algebra | |
| |
| |
| |
| Tableaux and the Duality Equation | |
| |
| |
| |
| Pivot Exchange, Row Equations | |
| |
| |
| |
| Pivot Exchange, Column Equations | |
| |
| |
| |
| Equivalent Tableaux | |
| |
| |
| |
| Basic Solutions | |
| |
| |
| |
| Inversion | |
| |
| |
| |
| Block Pivots | |
| |
| |
| |
| Expanded Tableaux | |
| |
| |
| |
| Canonical Duality | |
| |
| |
| |
| Canonical Dual Linear Programs | |
| |
| |
| |
| Sufficient Conditions for Optimality | |
| |
| |
| |
| Economic Interpretation of Duality | |
| |
| |
| |
| Heuristic Pivoting | |
| |
| |
| |
| Optimal Solutions - Unique, Multiple, None | |
| |
| |
| |
| The Geometric Picture | |
| |
| |
| |
| Feasibility Algorithm | |
| |
| |
| |
| Priority Pivoting | |
| |
| |
| |
| The Simplex Algorithm | |
| |
| |
| |
| The Simplex Algorithm | |
| |
| |
| |
| Degeneracy and Cycling | |
| |
| |
| |
| Bland's Anticycling Rule | |
| |
| |
| |
| Theorems of the Two Alternatives | |
| |
| |
| |
| The Dual Simplex Algorithm | |
| |
| |
| |
| The Theorem of the Four Alternatives | |
| |
| |
| |
| The Existence-Duality Theorem | |
| |
| |
| |
| General Linear Programs | |
| |
| |
| |
| General Dual Linear Programs | |
| |
| |
| |
| Reduction to Canonical Form | |
| |
| |
| |
| The Two-Phase Simplex Method | |
| |
| |
| |
| Systems of Linear Inequalities | |
| |
| |
| |
| Complementary Slackness | |
| |
| |
| |
| Numerical Considerations | |
| |
| |
| |
| Numerical Considerations | |
| |
| |
| |
| The Revised Simplex Method | |
| |
| |
| |
| Gaussian Elimination | |
| |
| |
| |
| Numerical Accuracy | |
| |
| |
| |
| The Ellipsoidal Algorithm | |
| |
| |
| |
| The Karmarkar Algorithm | |
| |
| |
| |
| Related Problems | |
| |
| |
| |
| Matrix Games | |
| |
| |
| |
| Matching Games | |
| |
| |
| |
| Optimal Strategies | |
| |
| |
| |
| Matrix Games and Linear Programs | |
| |
| |
| |
| Linear Programs and Symmetric Games | |
| |
| |
| |
| Assignment and Matching Problems | |
| |
| |
| |
| The Assignment Problem | |
| |
| |
| |
| Kuhn's Hungarian Algorithm | |
| |
| |
| |
| Konig's Theorem | |
| |
| |
| |
| Matching and Hall's Theorem | |
| |
| |
| |
| Assignments and Linear Programs | |
| |
| |
| |
| Egervary's Theorem | |
| |
| |
| |
| Von Neumann's Hide-and-Seek Game | |
| |
| |
| |
| Doubly Stochastic Matrices | |
| |
| |
| |
| The Transportation Problem | |
| |
| |
| |
| The Transportation Problem | |
| |
| |
| |
| Phase One of Dantzig's Method | |
| |
| |
| |
| The Dual of the Transportation Problem | |
| |
| |
| |
| Dantzig's Method | |
| |
| |
| |
| Economic Interpretation of the Dual Program | |
| |
| |
| |
| Graphs and Trees | |
| |
| |
| |
| Structure of Network Problems | |
| |
| |
| |
| Pivoting in Graphs | |
| |
| |
| |
| Network Flow Problems | |
| |
| |
| |
| Network Flow Problems | |
| |
| |
| |
| The Ford-Fulkerson Algorithm | |
| |
| |
| |
| The Max-Flow, Min-Cut Theorem | |
| |
| |
| |
| The Transshipment Problem | |
| |
| |
| |
| The Transshipment Problem | |
| |
| |
| |
| Shortest Path Problems | |
| |
| |
| |
| A Transshipment Algorithm | |
| |
| |
| |
| Nonlinear Programs | |
| |
| |
| |
| Karush-Kuhn-Tucker Theorem | |
| |
| |
| |
| The Constraint Qualification | |
| |
| |
| |
| Least Squares | |
| |
| |
| |
| Least Distance | |
| |
| |
| |
| Hybrid Problems | |
| |
| |
| |
| Empirical Principal Pivoting | |
| |
| |
| |
| Quadratic Programs | |
| |
| |
| |
| Semidefinite Quadratic Programs | |
| |
| |
| |
| An Algorithm for Quadratic Programs | |
| |
| |
| |
| Noncanonical Quadratic Programs | |
| |
| |
| A Answers | |
| |
| |
| Selected Bibliography | |
| |
| |
| Index | |