| |

| |

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 | |