책 이미지
책 정보
· 분류 : 외국도서 > 과학/수학/생태 > 수학 > 응용수학
· ISBN : 9781439887462
· 쪽수 : 555쪽
· 출판일 : 2020-12-16
목차
Introduction
Notation
What Is Linear Programming?
Visualizing LP
Presolving LP
Problems
Formulating and Solving Linear Programs
Three Classic Primal/Dual Formulation Pairs
LP Modeling Methods
More Examples of LP Formulation
Using Software to Solve LPs
Dual Variables as Shadow Prices
Problems
Polyhedra
Separation
Fourier-Motzkin Elimination
Theorems of the Alternative
Extreme Points and Optimal Solutions
Two Ways to Represent Polyhedra
Problems
The Simplex Method and Its Variants
The Simplex Method
Complications
Variants
High Level Computational Issues
The Geography of Mount Duality
Variants of Farkas’s Lemma and of Strong Duality
To and From Helly’s Theorem
Other Walking Trails on the TV Mountain
Sensitivity Analysis and Other Predictions
The Mathematical Justification of Shadow Prices
Sensitivity Analysis
Column Generation
Degeneracy
Parametric Programming
Networks
Network Models
Network Simplex Method
Dijkstra’s Algorithm for Shortest Paths
Max Flow Min Cut Algorithms
Hungarian Algorithm for Assignment as Primal-Dual Method
Integrality and Duality
Logarithmic Barrier and Other Interior-Point Methods
Column Geometry of Simplex and Affine Scaling Algorithms
Logarithmic Barrier and the Central Path
Sparseness and Factorization
Degeneracy, Crossover, and Other Considerations
Advanced Topics on Polyhedra
Polarity Separation Characterization of Convexity
Polyhedral Cones
Facets of Polyhedra
Formulating and Solving Integer Programs
Examples of IP Formulation
Tighter Formulations
Solving IPs
Computational Complexity
Introduction
Complexity, and NP-Hardness
The Straight Dope: Theory and Practice
YES/NO Form
The Nuts and Bolts of NP-Hardness Proofs
Spotting Complexity
Illustrations of Common Pitfalls
Examples of NP-Hardness Proofs
Dealing with NP-Hard Problems
Other Complexity Classifications
Conclusions and Recommended Reading
Answers to Questions
