Mokhtar S. Bazaraa

Indeholder "Preface", "1. Introduction", " 1.1 The Linear Programming Problem", " 1.2 Linear Programming Modelling and Examples", " 1.3 Geometric Solution", " 1.4 The Requirement Space", " 1.5 Notation", " Exercises", " Notes and References", "2. Linear Algebra, Convex Analysis, and Polyhedral Sets", " 2.1 Vectors", " 2.2 Matrices", " 2.3 Simultaneous Linear Equations", " 2.4 Convex Sets and Convex Functions", " 2.5 Polyhedral Sets and Polyhedral Cones", " 2.6 Extreme Points, Faces, Directions, and Extreme Directions of Polyhedral Sets. Geometric Insights", " 2.7 Representation of Polyhedral Sets", " Exercises", " Notes and References", "3. The Simplex Method", " 3.1 Extreme Points and Optimality", " 3.2 Basic Feasible Solutions", " 3.3 Key to the Simplex Method", " 3.4 Geometric Motivation of the Simplex Method", " 3.5 Algebra of the Simplex Method", " 3.6 Termination: Optimality and Unboundedness", " 3.7 The Simplex Method", " 3.8 The Simplex Method in Tableau Format", " 3.9 Block Pivoting", " Exercises", " Notes and References", "4. Starting Solution and Convergence", " 4.1 The Initial Basic Feasible Solution", " 4.2 The Two-Phase Method", " 4.3 The Big-M Method", " 4.4 Comparison of the Two-Phase and the Big-M Methods: How Big Should Big-M Be?", " 4.5 The Single Artificial Variable Technique", " 4.6 Degeneracy, Cycling, and Stalling", " 4.7 Validation of the Two Cycling Prevention Rules", " Exercises", " Notes and References", "5. Special Simplex Implementations and Optimal Conditions", " 5.1 The Revised Simplex Method", " 5.2 The Simplex Method for Bounded Variables", " 5.3 Farkos' Lemma via the Simplex Method", " 5.4 The Karush - Kuhn - Tucker Optimality Conditions", " Exercises", " Notes and References", "6. Duality and Sensitivity Analysis", " 6.1 Formulation of the Dual Problem", " 6.2 Primal-Dual Relationships", " 6.3 Economic Interpretation of the Dual", " 6.4 The Dual Simplex Method", " 6.5 The Primal-Simplex Method", " 6.6 Finding an Initial Dual Feasible Solution: The Artificial Constraint Technique", " 6.7 Sensitivity Analysis", " 6.8 Parametric Analysis", " Exercises", " Notes and References", "7. The Decomposition Principle", " 7.1 The Decomposition Principle", " 7.2 Numerical Example", " 7.3 Getting Started", " 7.4 The Case of Unbounded Region X", " 7.5 Block Diagonal or Angular Structure", " 7.6 Dualy and Relationships with Other Decomposition Procedures", " Exercises", " Notes and References", "8. Complexity of the Simplex Algorithm and Polynomial Algorithms", " 8.1 Polyomial Complexity Issues", " 8.2 Computational Complexity of the Simplex Algorithm", " 8.3 Khachians's Ellipsoid Algorithm", " 8.4 Karmarkar's Projective Algorithm", " 8.5 Analysis of Karmarkar's Algorithm: Convergence, Complexity, Sliding Objective Method, and Basic Optimal Solutions", " Exercises", " Notes and References", "9. Minimal Cost Network Flows", " 9.1 The Minimal Cost Network Flow Problem", " 9.2 Some Basic Definitions and Terminology from Graph Theory", " 9.3 Properties of the A Matrix", " 9.4 Representation of a Nonbasic Vector in Terms of the Basic Vectors", " 9.5 The Simplex Method for Network Flow Problems", " 9.6 An Example of the Network Simplex Method", " 9.7 Finding an Initial Besic Feasible Solution", " 9.8 Network Flows with Lower and Upper Bounds", " 9.9 The Simplex Tableau Associated with a Network Flow Problem", " 9.10 List Structures for Implementing the Network Simplex Algorithm", " 9.11 Degeneracy, Cycling and Stalling", " 9.12 Generalized Network Problems", " Exercises", " Notes and References", "10. The Transportation and Assignment Problems", " 10.1 Definition of the Transportation Problem", " 10.2 Properties of the A Matrix", " 10.3 Representation of a Nonbasic Vector in Terms of the Basic Vectors", " 10.4 The Simplex Method for Transportation Problems", " 10.5 Illustrative Examples and a Note on Degeneracy", " 10.6 The Simplex Tableau Associated with a Transportation Tableau", " 10.7 The Assignment Problem: (Kuhn's) Hungarian Algorithm", " 10.8 Alternating Basis Algorithm for Assignment Problems", " 10.9 A Polynomial Successive Shortest Path Approach for Assignment Problems", " 10.10 The Transshipment Problem", " Exercises", " Notes and References", "11. The Out-of-Kilter Algorithm", " 11.1 The Out-of-Kilter Formulation of a Minimal Cost Network Flow Problem", " 11.2 Strategy of the Out-of-Kilter Algorithm", " 11.3 Summary of the Out-of-Kilter Algorithm", " 11.4 An Example of the Out-of-Kilter Algorithm", " 11.5 A Labeling Procedure for the Out-of-Kilter Algorithm", " 11.6 Insight into Changes in Primal and Dual Function Values", " Exercises", " Notes and References", "12. Maximal Flow, Shortest Path, Multicommodity Flow, and Network Synthesis Problems", " 12.1 The Maximal Flow Problem", " 12.2 The Shortest Path Problem", " 12.3 Polynomial Shortest Path Algorithms for Networks with Arbitrary Costs", " 12.4 Multicommodity Flows", " 12.5 Characterization of a Basis for the Multicommodity Minimal Cost Flow Problem", " 12.6 Synthesis of Multiterminal Flow Networks", " Exercises", " Notes and References", "Bibliography", "Index".

Lineær programmering og Simplex metoden i ret stor detalje.… (plus d'informations)