Linear Programming"This comprehensive treatment of the fundamental ideas and principles of linear programming covers basic theory, selected applications, network flow problems, and advanced techniques. Using specific examples to illuminate practical and theoretical aspects of the subject, the author clearly reveals the structures of fully detailed proofs. The presentation is geared toward modern efficient implementations of the simplex method and appropriate data structures for network flow problems. Completely self-contained, it develops even elementary facts on linear equations and matrices from the beginning."--Back cover. |
Contents
Introduction | 3 |
How the Simplex Method Works | 13 |
Pitfalls and How to Avoid Them | 27 |
How Fast Is the Simplex Method? | 45 |
The Duality Theorem | 54 |
Gaussian Elimination and Matrices | 71 |
The Revised Simplex Method | 97 |
Solutions by the Simplex Method | 118 |
Approximating Data by Linear Functions | 213 |
Matrix Games | 228 |
Systems of Linear Inequalities | 240 |
Finding All Vertices of a Polyhedron | 271 |
The Network Simplex Method | 291 |
Applications of the Network Simplex Method | 320 |
UpperBounded Transshipment Problems | 353 |
Maximum Flows Through Networks | 367 |
Theorems on Duality and Infeasibility | 137 |
Sensitivity Analysis | 148 |
Selected Applications | 169 |
Efficient Allocation of Scarce Resources | 171 |
Scheduling Production and Inventory | 188 |
The CuttingStock Problem | 195 |
The PrimalDual Method | 390 |
Updating a Triangular Factorization of the Basis | 405 |
The DantzigWolfe Decomposition Principle | 425 |
The Ellipsoid Method | 443 |
Solutions to Selected Problems | 465 |
Other editions - View all
Common terms and phrases
algorithm arcs ij augmenting path auxiliary problem b₁ basic feasible solution basic variables bipartite graph c₁ Chapter Cjxj coefficients components computing constraints convex convex hull convex sets corresponding defined entering arc entering column entering the basis entering variable eta column example feasible tree solution finals of width finite Gaussian elimination Hence identity matrix infeasible integer leaving variable linear inequalities linear programming linear programming problem LP problems matrix maximize cx subject maximize subject maximum-flow problem mixed strategy network simplex method node nonbasic variables nonzero number of iterations objective function obtain optimal solution original problem path permutation permutation matrices pivot polyhedron problem maximize cx procedure Prove pure strategies replace resulting revised simplex method right-hand side satisfies slack variables solvable Solving the system Step subject to Ax system Ax systems of linear Theorem transshipment problem triangular factorization update upper bound x₁ y₁ zero