Linear Programming and Its Applications

ISBN-13: 9781461269823 / Angielski / Miękka / 2012 / 266 str.

James K. Strayer; James K. Strayer

Opis

The effectiveness of the algorithms of linear programming in solving problems is largely dependent upon the particular applications from which these problems arise. A first course in linear programming should not only allow one to solve many different types of problems in many different contexts but should provide deeper insights into the fields in which linear programming finds its utility. To this end, the emphasis throughtout Linear Programming and Its Applications is on the acquisition of linear programming skills via the algorithmic solution of small-scale problems both in the general sense and in the specific applications where these problems naturally occur. The first part of the book deals with methods to solve general linear programming problems and discusses the theory of duality which connects these problems. The second part of the book deals with linear programming in different applications including the fields of game theory and graph theory as well as the more traditional transportation and assignment problems. The book is versatile; in as much as Linear Programming and Its Applications is intended to be used as a first course in linear programming, it is suitable for students in such varying fields as mathematics, computer science, engineering, actuarial science, and economics.

Spis treści

0 Introduction.- I: Linear Programming.- 1 Geometric Linear Programming.- §0. Introduction.- §1. Two Examples: 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 Example: Profit Maximization.- §3. The Pivot Transformation.- §4. An Example: 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.- II: 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.