| |
| |
| Preface | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| The Linear Programming Problem | |
| |
| |
| |
| Linear Programming Modeling and Examples | |
| |
| |
| |
| Geometric Solution | |
| |
| |
| |
| The Requirement Space | |
| |
| |
| |
| Notation | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Linear Algebra, Convex Analysis, and Polyhedral Sets | |
| |
| |
| |
| Vectors | |
| |
| |
| |
| Matrices | |
| |
| |
| |
| Simultaneous Linear Equations | |
| |
| |
| |
| Convex Sets and Convex Functions | |
| |
| |
| |
| Polyhedral Sets and Polyhedral Cones | |
| |
| |
| |
| Extreme Points, Faces, Directions, and Extreme Directions of Polyhedral Sets: Geometric Insights | |
| |
| |
| |
| Representation of Polyhedral Sets | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| The Simplex Method | |
| |
| |
| |
| Extreme Points and Optimality | |
| |
| |
| |
| Basic Feasible Solutions | |
| |
| |
| |
| Key to the Simplex Method | |
| |
| |
| |
| Geometric Motivation of the Simplex Method | |
| |
| |
| |
| Algebra of the Simplex Method | |
| |
| |
| |
| Termination: Optimality and Unboundedness | |
| |
| |
| |
| The Simplex Method | |
| |
| |
| |
| The Simplex Method in Tableau Format | |
| |
| |
| |
| Block Pivoting | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Starting Solution and Convergence | |
| |
| |
| |
| The Initial Basic Feasible Solution | |
| |
| |
| |
| The Two-Phase Method | |
| |
| |
| |
| The Big-M Method | |
| |
| |
| |
| How Big Should Big-M Be? | |
| |
| |
| |
| The Single Artificial Variable Technique | |
| |
| |
| |
| Degeneracy, Cycling, and Stalling | |
| |
| |
| |
| Validation of Cycling Prevention Rules | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Special Simplex Implementations and Optimality Conditions | |
| |
| |
| |
| The Revised Simplex Method | |
| |
| |
| |
| The Simplex Method for Bounded Variables | |
| |
| |
| |
| Farkas' Lemma via the Simplex Method | |
| |
| |
| |
| The Karush-Kuhn-Tucker Optimality Conditions | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Duality and Sensitivity Analysis | |
| |
| |
| |
| Formulation of the Dual Problem | |
| |
| |
| |
| Primal-Dual Relationships | |
| |
| |
| |
| Economic Interpretation of the Dual | |
| |
| |
| |
| The Dual Simplex Method | |
| |
| |
| |
| The Primal-Dual Method | |
| |
| |
| |
| Finding an Initial Dual Feasible Solution: The Artificial Constraint Technique | |
| |
| |
| |
| Sensitivity Analysis | |
| |
| |
| |
| Parametric Analysis | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| The Decomposition Principle | |
| |
| |
| |
| The Decomposition Algorithm | |
| |
| |
| |
| Numerical Example | |
| |
| |
| |
| Getting Started | |
| |
| |
| |
| The Case of an Unbounded Region X | |
| |
| |
| |
| Block Diagonal or Angular Structure | |
| |
| |
| |
| Duality and Relationships with other Decomposition Procedures | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Complexity of the Simplex Algorithm and Polynomial-Time Algorithms | |
| |
| |
| |
| Polynomial Complexity Issues | |
| |
| |
| |
| Computational Complexity of the Simplex Algorithm | |
| |
| |
| |
| Khachian's Ellipsoid Algorithm | |
| |
| |
| |
| Karmarkar's Projective Algorithm | |
| |
| |
| |
| Analysis of Karmarkar's Algorithm: Convergence, Complexity, Sliding Objective Method, and Basic Optimal Solutions | |
| |
| |
| |
| Affine Scaling, Primal-Dual Path Following, and Predictor-Corrector Variants of Interior Point Methods | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Minimal-Cost Network Flows | |
| |
| |
| |
| The Minimal Cost Network Flow Problem | |
| |
| |
| |
| Some Basic Definitions and Terminology from Graph Theory | |
| |
| |
| |
| Properties of the A Matrix | |
| |
| |
| |
| Representation of a Nonbasic Vector in Terms of the Basic Vectors | |
| |
| |
| |
| The Simplex Method for Network Flow Problems | |
| |
| |
| |
| An Example of the Network Simplex Method | |
| |
| |
| |
| Finding an Initial Basic Feasible Solution | |
| |
| |
| |
| Network Flows with Lower and Upper Bounds | |
| |
| |
| |
| The Simplex Tableau Associated with a Network Flow Problem | |
| |
| |
| |
| List Structures for Implementing the Network Simplex Algorithm | |
| |
| |
| |
| Degeneracy, Cycling, and Stalling | |
| |
| |
| |
| Generalized Network Problems | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| The Transportation and Assignment Problems | |
| |
| |
| |
| Definition of the Transportation Problem | |
| |
| |
| |
| Properties of the A Matrix | |
| |
| |
| |
| Representation of a Nonbasic Vector in Terms of the Basic Vectors | |
| |
| |
| |
| The Simplex Method for Transportation Problems | |
| |
| |
| |
| Illustrative Examples and a Note on Degeneracy | |
| |
| |
| |
| The Simplex Tableau Associated with a Transportation Tableau | |
| |
| |
| |
| The Assignment Problem: (Kuhn's) Hungarian Algorithm | |
| |
| |
| |
| Alternating Path Basis Algorithm for Assignment Problems | |
| |
| |
| |
| A Polynomial-Time Successive Shortest Path Approach for Assignment Problems | |
| |
| |
| |
| The Transshipment Problem | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| The Out-Of-Kilter Algorithm | |
| |
| |
| |
| The Out-of-Kilter Formulation of a Minimal Cost Network Flow Problem | |
| |
| |
| |
| Strategy of the Out-of-Kilter Algorithm | |
| |
| |
| |
| Summary of the Out-of-Kilter Algorithm | |
| |
| |
| |
| An Example of the Out-of-Kilter Algorithm | |
| |
| |
| |
| A Labeling Procedure for the Out-of-Kilter Algorithm | |
| |
| |
| |
| Insight into Changes in Primal and Dual Function Values | |
| |
| |
| |
| Relaxation Algorithms | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| |
| Maximal Flow, Shortest Path, Multicommodity Flow, And Network Synthesis Problems | |
| |
| |
| |
| The Maximal Flow Problem | |
| |
| |
| |
| The Shortest Path Problem | |
| |
| |
| |
| Polynomial-Time Shortest Path Algorithms for Networks Having Arbitrary Costs | |
| |
| |
| |
| Multicommodity Flows | |
| |
| |
| |
| Characterization of a Basis for the Multicommodity Minimal-Cost Flow Problem | |
| |
| |
| |
| Synthesis of Multiterminal Flow Networks | |
| |
| |
| Exercises | |
| |
| |
| Notes and References | |
| |
| |
| Bibliography | |
| |
| |
| Index | |