Linear Programming and Extensions

CONTENTS
PREFACE
CHAPTER 1. THE LINEAR PROGRAMMING CONCEPT
	1-1. Introduction
	1-2. The Programming Problem
	1-3. Linear Programming Defined
	1-4. Classification of Programming Problems
	1-5. Mathematical Programming and Automation
CHAPTER 2. ORIGINS AND INFLUENCES
	2-1. World War II Influences
	2-2. Economic Models and Linear Programming
	2-3. Mathematical Origins and Developments
	2-4. Industrial Applications of Linear Programming
CHAPTER 3. FORMULATING A LINEAR PROGRAMMING MODEL
	3-1. Basic Concepts
	3-2. Building the Model
	3-3. A Transportation Problem
	3-4. Examples of Blending
	3-5. A Product Mix Problem
	3-6. A Simple Warehouse Problem
	3-7. On-the-job Training
	3-8. The Central Mathematical Problem
	3-9. Problems
CHAPTER 4. LINEAR EQUATION AND INEQUALITY SYSTEMS
	4-1. Systems of Equations with the Same Solution Set
	4-2. Canonical Systems
	4-3. Linear Inequalities
	4-4. Fourier-Motzkin Elimination Method
	4-5. Linear Programs in Inequality Form
	4-6. Problems
CHAPTER 5. THE SIMPLEX METHOD
	5-1. Simplex Algorithm
	5-2. The Two Phases of the Simplex Method
	5-3. Problems
CHAPTER 6. PROOF OF THE SIMPLEX ALGORITHM AND THE DUALITY THEOREM
	6-1. Inductive Proof of the Simplex Algorithm
	6-2. Equivalent Dual Forms
	6-3. Proof of the Duality Theorem
	6-4. Basic Theorems on Duality
	6-5. Lagrange Multipliers
	6-6. Problems
CHAPTER 7. THE GEOMETRY OF LINEAR PROGRAMS
	7-1. Convex Regions
	7-2. The Simplex Method Viewed as the Steepest Descent Along Edges
	7-3. The Simplex Interpretation of the Simplex Method
	7-4. Problems
CHAPTER 8. PIVOTING, VECTOR SPACES, MATRICES, AND INVERSES
	8-1. Pivot Theory
	8-2. Vector Spaces
	8-3. Matrices
	8-4. Inverse of a Matrix
	8-5. The Simplex Algorithm in Matrix Form
	8-6. Problems
CHAPTER 9. THE SIMPLEX METHOD USING MULTIPLIERS
	9-1. An Illustration Using Multipliers
	9-2. The General Method Using Multipliers
	9-3. Computational Rules Using Multipliers
	9-4. Problems
CHAPTER 10. FINITENESS OF THE SIMPLEX METHOD UNDER PERTURBATION
	10-1. The Possibility of Circling in the Simplex Algorithm
	10-2. Perturbing Constants To Avoid Degeneracy
	10-3. Problems
CHAPTER 11. VARIANTS OF THE SIMPLEX ALGORITHM
	11-1. Complementary Primal and Dual Bases
	11-2. The Dual Simplex Method
	11-3. A Self-Dual Parametric Algorithm
	11-4. The Primal-Dual Algorithm
	11-5. An Alternative Criterion for Phase I
	11-6. Problems
CHAPTER 12. THE PRICE CONCEPT IN LINEAR PROGRAMMING
	12-1. The Price Mechanism of the Simplex Method
	12-2. Examples of Dual Problems
	12-3. The Sign Convention on Prices
	12-4. Sensitivity Analysis Illustrated
	12-5. Problems
CHAPTER 13. GAMES AND LINEAR PROGRAMS
	13-1. Matrix Games
	13-2. Equivalence of Matrix Games and Linear Programs; The Minimax Theorem
	13-3. Constructive Solution to a Matrix Game (Alternative Proof of Minimax Theorem)
	13-4. Problems
CHAPTER 14. THE CLASSICAL TRANSPORTATION PROBLEM
	14-1. Historical Summary
	14-2. Elementary Transportation Theory
	14-3. Computational Algorithm for the Transportation Problem
	14-4. Problems
CHAPTER 15. OPTIMAL ASSIGNMENT AND OTHER DISTRIBUTION PROBLEMS
	15-1. The Optimal Assignment Problem
	15-2. Allocation with Surplus and Deficit
	15-3. Fixed Values and Inadmissible Squares
	15-4. Problems
CHAPTER 16. THE TRANSSHIPMENT PROBLEM
	16-1. Equivalent Formulations of the Model
	16-2. The Equivalence of Transportation and Transshipment Problems
	16-3. Solving a Transshipment Problem by the Simplex Method
	16-4. Problems
CHAPTER 17. NETWORKS AND THE TRANSSHIPMENT PROBLEM
	17-1. Graphs and Trees
	17-2. Interpreting the Simplex Method on the Network
	17-3. The Shortest Route Problem
	17-4. Problems
CHAPTER 18. VARIABLES WITH UPPER BOUNDS
	18-1. The General Case
	18-2. The Bounded Variable Transportation Problem and Generalizations
	18-3. Problems
CHAPTER 19. MAXIMAL FLOWS IN NETWORKS
	19-1. Ford-Fulkerson Theory
	19-2. The Tree Method for Solving Maximal Flow Problems
	19-3. Problems
CHAPTER 20. THE PRIMAL-DUAL METHOD FOR TRANSPORTATION PROBLEMS
	20-1. Introduction
	20-2. The Ford-Fulkerson Algorithm
	20-3. Problems
CHAPTER 21. THE WEIGHTED DISTRIBUTION PROBLEM
	21-1. The Near-Triangularity of the Basis
	21-2. Linear Graph Structure of the Basis
	21-3. A Subclass with Triangular Optimum Bases
	21-4. Problems
CHAPTER 22. PROGRAMS WITH VARIABLE COEFFICIENTS
	22-1. Wolfe’s Generalized Program
	22-2. Notes on Special Cases
	22-3. Problems
CHAPTER 23. A DECOMPOSITION PRINCIPLE FOR LINEAR PROGRAMS
	23-1. The General Principle
	23-2. Decomposition Principle, Animated
	23-3. Central Planning without Complete Information at the Center
	23-4. Decomposing Multi-stage Programs
	23-5. Problems
CHAPTER 24. CONVEX PROGRAMMING
	24-1. General Theory
	24-2. Homogeneous Objectives and the Chemical Equilibrium Problem
	24-3. Separable Convex Objectives
	24-4. Quadratic Programming
	24-5. Problems
CHAPTER 25. UNCERTAINTY
	25-1. Scheduling To Meet Variable Cost
	25-2. Scheduling To Meet an Uncertain Demand
	25-3. On Multi-stage Problems
	25-4. Problems
CHAPTER 26. DISCRETE VARIABLE EXTREMUM PROBLEMS
	26-1. Survey of Methods
	26-2. Gomory’s Method of Integer Forms
	26-3. On the Significance of Solving Linear Programming Problems with Some Integer Variables
CHAPTER 27. STIGLER'S NUTRITION MODEL: AN EXAMPLE OF FORMULATION AND SOLUTION
	27-1. Problems in Formulating a Model
	27-2. Numerical Solution of the Nutrition Problem
	27-3. Problems
CHAPTER 28. THE ALLOCATION OF AIRCRAFT TO ROUTES UNDER UNCERTAIN DEMAND
	28-1. Statement and Formulation
	28-2. Numerical Solution of the Routing Problem
BIBLIOGRAPHY
INDEX