Linear Programming and Its Applications

by James K. Strayer

0 Introduction.- Linear Programming.- 1 Geometric Linear Programming.- §0. Introduction.- §1. Two Profit Maximization and Cost Minimization.- §2. Canonical Forms for Linear Programming Problems.- §3. Polyhedral Convex Sets.- §4. The Two Examples Revisited.- §5. A Geometric Method for Linear Programming.- §6. Concluding Remarks.- Exercises.- 2 The Simplex Algorithm.- §0. Introduction.- §1. Canonical Slack Forms for Linear Programming Problems; Tucker Tableaus.- §2. An Profit Maximization.- §3. The Pivot Transformation.- §4. An Cost Minimization.- §5. The Simplex Algorithm for Maximum Basic Feasible Tableaus.- §6. The Simplex Algorithm for Maximum Tableaus.- §7. Negative Transposition; The Simplex Algorithm for Minimum Tableaus.- §8. Cycling.- §9. Concluding Remarks.- Exercises.- 3 Noncanonical Linear Programming Problems.- §0. Introduction.- §1. Unconstrained Variables.- §2. Equations of Constraint.- §3. Concluding Remarks.- Exercises.- 4 Duality Theory.- §0. Introduction.- §1. Duality in Canonical Tableaus.- §2. The Dual Simplex Algorithm.- §3. Matrix Formulation of Canonical Tableaus.- §4. The Duality Equation.- §5. The Duality Theorem.- §6. Duality in Noncanonical Tableaus.- §7. Concluding Remarks.- Exercises.- Applications.- 5 Matrix Games.- §0. Introduction.- §1. An Example; Two-Person Zero-Sum Matrix Games.- §2. Linear Programming Formulation of Matrix Games.- §3. The Von Neumann Minimax Theorem.- §4. The Example Revisited.- §5. Two More Examples.- §6. Concluding Remarks.- Exercises.- 6 Transportation and Assignment Problems.- §0. Introduction.- §1. An Example; The Balanced Transportation Problem.- §2. The Vogel Advanced-Start Method (VAM).- §3. The Transportation Algorithm.- §4. Another Example.- §5. Unbalanced Transportation Problems.- §6. The Assignment Problem.- §7. Concluding Remarks.- Exercises.- 7 Network-Flow Problems.- §0. Introduction.- §1. Graph-Theoretic Preliminaries.- §2. The Maximal-Flow Network Problem.- §3. The Max-Flow Min-Cut Theorem; The Maximal-Flow Algorithm.- §4. The Shortest-Path Network Problem.- §5. The Minimal-Cost-Flow Network Problem.- §6. Transportation and Assignment Problems Revisited.- §7. Concluding Remarks.- Exercises.- APPENDIX A Matrix Algebra.- APPENDIX B Probability.- Answers to Selected Exercises.

Hardcover

First published July 25, 1989