Hilfe Warenkorb Konto Anmelden
 
 
   Schnellsuche   
     zur Expertensuche                      
Linear Programming - Foundations and Extensions  
Linear Programming - Foundations and Extensions
von: Robert J Vanderbei
Springer-Verlag, 2007
ISBN: 9780387743882
468 Seiten, Download: 6689 KB
 
Format:  PDF
geeignet für: Apple iPad, Android Tablet PC's Online-Lesen PC, MAC, Laptop

Typ: B (paralleler Zugriff)

 

 
eBook anfordern
Inhaltsverzeichnis

  Contents 7  
  Preface 13  
  Preface to 2nd Edition 17  
  Preface to 3rd Edition 19  
  Part 1. Basic Theory---The Simplex Method and Duality 20  
     Chapter 1. Introduction 22  
        1. Managing a Production Facility 22  
        2. The Linear Programming Problem 25  
        Exercises 27  
        Notes 29  
     Chapter 2. The Simplex Method 31  
        1. An Example 31  
        2. The Simplex Method 34  
        3. Initialization 37  
        4. Unboundedness 40  
        5. Geometry 40  
        Exercises 42  
        Notes 45  
     Chapter 3. Degeneracy 46  
        1. Definition of Degeneracy 46  
        2. Two Examples of Degenerate Problems 46  
        3. The Perturbation/Lexicographic Method 49  
        4. Bland's Rule 53  
        5. Fundamental Theorem of Linear Programming 55  
        6. Geometry 56  
        Exercises 59  
        Notes 60  
     Chapter 4. Efficiency of the Simplex Method 62  
        1. Performance Measures 62  
        2. Measuring the Size of a Problem 62  
        3. Measuring the Effort to Solve a Problem 63  
        4. Worst-Case Analysis of the Simplex Method 64  
        Exercises 69  
        Notes 70  
     Chapter 5. Duality Theory 72  
        1. Motivation---Finding Upper Bounds 72  
        2. The Dual Problem 74  
        3. The Weak Duality Theorem 75  
        4. The Strong Duality Theorem 77  
        5. Complementary Slackness 83  
        6. The Dual Simplex Method 85  
        7. A Dual-Based Phase I Algorithm 88  
        8. The Dual of a Problem in General Form 90  
        9. Resource Allocation Problems 91  
        10. Lagrangian Duality 95  
        Exercises 96  
        Notes 104  
     Chapter 6. The Simplex Method in Matrix Notation 105  
        1. Matrix Notation 105  
        2. The Primal Simplex Method 107  
        3. An Example 112  
        4. The Dual Simplex Method 117  
        5. Two-Phase Methods 120  
        6. Negative Transpose Property 121  
        Exercises 124  
        Notes 125  
     Chapter 7. Sensitivity and Parametric Analyses 126  
        1. Sensitivity Analysis 126  
        2. Parametric Analysis and the Homotopy Method 130  
        3. The Parametric Self-Dual Simplex Method 134  
        Exercises 135  
        Notes 139  
     Chapter 8. Implementation Issues 140  
        1. Solving Systems of Equations: LU-Factorization 141  
        2. Exploiting Sparsity 145  
        3. Reusing a Factorization 151  
        4. Performance Tradeoffs 155  
        5. Updating a Factorization 156  
        6. Shrinking the Bump 160  
        7. Partial Pricing 161  
        8. Steepest Edge 162  
        Exercises 164  
        Notes 165  
     Chapter 9. Problems in General Form 166  
        1. The Primal Simplex Method 166  
        2. The Dual Simplex Method 168  
        Exercises 174  
        Notes 175  
     Chapter 10. Convex Analysis 176  
        1. Convex Sets 176  
        2. Carathéodory's Theorem 178  
        3. The Separation Theorem 180  
        4. Farkas' Lemma 182  
        5. Strict Complementarity 183  
        Exercises 185  
        Notes 186  
     Chapter 11. Game Theory 187  
        1. Matrix Games 187  
        2. Optimal Strategies 189  
        3. The Minimax Theorem 191  
        4. Poker 195  
        Exercises 198  
        Notes 201  
     Chapter 12. Regression 202  
        1. Measures of Mediocrity 202  
        2. Multidimensional Measures: Regression Analysis 204  
        3. L2-Regression 206  
        4. L1-Regression 208  
        5. Iteratively Reweighted Least Squares 209  
        6. An Example: How Fast is the Simplex Method? 211  
        7. Which Variant of the Simplex Method is Best? 215  
        Exercises 216  
        Notes 221  
     Chapter 13. Financial Applications 223  
        1. Portfolio Selection 223  
        2. Option Pricing 228  
        Exercises 233  
        Notes 234  
  Part 2. Network-Type Problems 235  
     Chapter 14. Network Flow Problems 237  
        1. Networks 237  
        2. Spanning Trees and Bases 240  
        3. The Primal Network Simplex Method 245  
        4. The Dual Network Simplex Method 249  
        5. Putting It All Together 252  
        6. The Integrality Theorem 255  
        Exercises 256  
        Notes 264  
     Chapter 15. Applications 265  
        1. The Transportation Problem 265  
        2. The Assignment Problem 267  
        3. The Shortest-Path Problem 268  
        4. Upper-Bounded Network Flow Problems 271  
        5. The Maximum-Flow Problem 274  
        Exercises 276  
        Notes 281  
     Chapter 16. Structural Optimization 282  
        1. An Example 282  
        2. Incidence Matrices 284  
        3. Stability 285  
        4. Conservation Laws 287  
        5. Minimum-Weight Structural Design 290  
        6. Anchors Away 292  
        Exercises 295  
        Notes 295  
  Part 3. Interior-Point Methods 298  
     Chapter 17. The Central Path 300  
        Warning: Nonstandard Notation Ahead 300  
        1. The Barrier Problem 300  
        2. Lagrange Multipliers 303  
        3. Lagrange Multipliers Applied to the Barrier Problem 306  
        4. Second-Order Information 308  
        5. Existence 308  
        Exercises 310  
        Notes 312  
     Chapter 18. A Path-Following Method 313  
        1. Computing Step Directions 313  
        2. Newton's Method 315  
        3. Estimating an Appropriate Value for the Barrier Parameter 316  
        4. Choosing the Step Length Parameter 317  
        5. Convergence Analysis 318  
        Exercises 324  
        Notes 328  
     Chapter 19. The KKT System 329  
        1. The Reduced KKT System 329  
        2. The Normal Equations 330  
        3. Step Direction Decomposition 332  
        Exercises 335  
        Notes 335  
     Chapter 20. Implementation Issues 336  
        1. Factoring Positive Definite Matrices 336  
        2. Quasidefinite Matrices 340  
        3. Problems in General Form 346  
        Exercises 351  
        Notes 351  
     Chapter 21. The Affine-Scaling Method 354  
        1. The Steepest Ascent Direction 354  
        2. The Projected Gradient Direction 356  
        3. The Projected Gradient Direction with Scaling 358  
        4. Convergence 362  
        5. Feasibility Direction 364  
        6. Problems in Standard Form 365  
        Exercises 366  
        Notes 367  
     Chapter 22. The Homogeneous Self-Dual Method 369  
        1. From Standard Form to Self-Dual Form 369  
        2. Homogeneous Self-Dual Problems 370  
        3. Back to Standard Form 380  
        4. Simplex Method vs Interior-Point Methods 383  
        Exercises 387  
        Notes 388  
  Part 4. Extensions 390  
     Chapter 23. Integer Programming 392  
        1. Scheduling Problems 392  
        2. The Traveling Salesman Problem 394  
        3. Fixed Costs 397  
        4. Nonlinear Objective Functions 397  
        5. Branch-and-Bound 399  
        Exercises 411  
        Notes 412  
     Chapter 24. Quadratic Programming 413  
        1. The Markowitz Model 413  
        2. The Dual 418  
        3. Convexity and Complexity 420  
        4. Solution Via Interior-Point Methods 424  
        5. Practical Considerations 425  
        Exercises 428  
        Notes 429  
     Chapter 25. Convex Programming 430  
        1. Differentiable Functions and Taylor Approximations 430  
        2. Convex and Concave Functions 431  
        3. Problem Formulation 431  
        4. Solution Via Interior-Point Methods 432  
        5. Successive Quadratic Approximations 434  
        6. Merit Functions 434  
        7. Parting Words 438  
        Exercises 438  
        Notes 440  
     Appendix A. Source Listings 441  
        1. The Self-Dual Simplex Method 442  
        2. The Homogeneous Self-Dual Method 445  
  Answers to Selected Exercises 448  
  Bibliography 451  
  Index 459  


nach oben


  Mehr zum Inhalt
Kapitelübersicht
Kurzinformation
Inhaltsverzeichnis
Leseprobe
Blick ins Buch
Fragen zu eBooks?

  Navigation
Belletristik / Romane
Computer
Geschichte
Kultur
Medizin / Gesundheit
Philosophie / Religion
Politik
Psychologie / Pädagogik
Ratgeber
Recht
Reise / Hobbys
Technik / Wissen
Wirtschaft

  Info
Hier gelangen Sie wieder zum Online-Auftritt Ihrer Bibliothek
© 2008-2020 ciando GmbH | Impressum | Kontakt | F.A.Q. | Datenschutz