Linear Programming / Edition 1

by James E. Calvert

Overview

This book has two fundamental objectives: (1) to carefully motivate and explain the basic ideas underlying linear programming and (2) to apply these ideas to a wide variety of mathematical models. In order to achieve these objectives, the authors provide more than the usual number of examples and offer clarity of presentation over abstraction. Students will be able to grasp readily the material presented and apply the material to a number of challenging problems.

Product Details

ISBN-13:	9780155510272
Publisher:	Cengage Learning
Publication date:	01/13/1989
Edition description:	New Edition
Pages:	655
Product dimensions:	7.12(w) x 9.58(h) x 1.22(d)

Table of Contents

1. LINEAR PROGRAMMING: AN OVERVIEW AND SAMPLE PROBLEMS. Product-mix Problems. Transportation and Assignment Problems. General Comments Regarding LP Models. Dynamic Planning. 2. GEOMETRIC AND ALGEBRAIC PRELIMINARIES. Half-spaces, Hyperplanes, and Convex Sets. Feasible Sets and Geometric Solutions of LP Problems. Proof of the Corner Point Theorem. Algebraic Preliminaries. Slack Variables and Constraints in Canonical Form. 3. THE SIMPLEX METHOD. Selection of Entering and Departing Basic Variables. Simplex Tableaus. Degeneracy, Cycling, and Convergence. The Two-Phase Method. The Two-Phase Method: Some Complications. The Big-M Method. LP Models. 4. THE SIMPLEX METHOD IN A MATRIX CONTEXT. Matrices. Elementary Matrices, Matrix Inverses, and Pivoting. Matrix Representation of the Simplex Method: Part I. Matrix Representation of the Simplex Method: Part II. LP Models. 5. THE REVISED SIMPLEX METHOD. A Faster Algorithm for Computer Solution. Preliminary Results for Use in Complexity Analysis. Space and Time Complexity of the Simplex Method. LP Models. 6. DUALITY. An Economic Interpretation of Duality. Primal and Dual Problems: A Special Case. Duality: The General Case. Duality Proofs. The Dual Simplex Model. LP Models. 7. SENSITIVITY ANALYSIS. What is Sensitivity Analysis? Changes in the Resource Column. Changes in Cost Coefficients. Using Duality in Sensitivity Analysis. Introduction of a New Variable. LP Models. 8. AN INTRODUCTION TO INTEGER PROGRAMMING. A Sampling of IP Problems. A Branch and Bound Method. Implicit Enumeration: Part I. Implicit Enumeration: Part II. Geometry Cutting Plane Method. LP Models. 9. THE TRANSPORTATION PROBLEM. Choosing the Entering Basic Variable. Choosing the Departing Basic Variable. Finding an Initial Basic Feasible Solution. 10. LARGE-SCALE PROBLEMS. LP Problems with Bounded Constraints. A Decomposition Procedure: The Master Problem. Solving the Master Problem. Final Words.