Linear Programming

Paperback

Vanderbei, Robert J. 저자(글)

Kluwer · 2001년 05월 01일

책 소개

작가정보

저자(글) Vanderbei, Robert J.

목차

• Preface	p. xiii
  Preface to 2nd Edition	p. xvii
  Basic Theory--The Simplex Method and Duality	p. 1
  Introduction	p. 3
  Managing a Production Facility	p. 3
  The Linear Programming Problem	p. 6
  Exercises	p. 8
  Notes	p. 10
  The Simplex Method	p. 13
  An Example	p. 13
  The Simplex Method	p. 16
  Initialization	p. 19
  Unboundedness	p. 22
  Geometry	p. 22
  Exercises	p. 24
  Notes	p. 27
  Degeneracy	p. 29
  Definition of Degeneracy	p. 29
  Two Examples of Degenerate Problems	p. 29
  The Perturbation/Lexicographic Method	p. 32
  Bland's Rule	p. 36
  Fundamental Theorem of Linear Programming	p. 38
  Geometry	p. 39
  Exercises	p. 42
  Notes	p. 43
  Efficiency of the Simplex Method	p. 45
  Performance Measures	p. 45
  Measuring the Size of a Problem	p. 45
  Measuring the Effort to Solve a Problem	p. 46
  Worst-Case Analysis of the Simplex Method	p. 47
  Exercises	p. 52
  Notes	p. 53
  Duality Theory	p. 55
  Motivation--Finding Upper Bounds	p. 55
  The Dual Problem	p. 57
  The Weak Duality Theorem	p. 58
  The Strong Duality Theorem	p. 60
  Complementary Slackness	p. 66
  The Dual Simplex Method	p. 68
  A Dual-Based Phase I Algorithm	p. 71
  The Dual of a Problem in General Form	p. 73
  Resource Allocation Problems	p. 74
  Lagrangian Duality	p. 78
  Exercises	p. 79
  Notes	p. 87
  The Simplex Method in Matrix Notation	p. 89
  Matrix Notation	p. 89
  The Primal Simplex Method	p. 91
  An Example	p. 96
  The Dual Simplex Method	p. 101
  Two-Phase Methods	p. 104
  Negative Transpose Property	p. 105
  Exercises	p. 108
  Notes	p. 109
  Sensitivity and Parametric Analyses	p. 111
  Sensitivity Analysis	p. 111
  Parametric Analysis and the Homotopy Method	p. 115
  The Parametric Self-Dual Simplex Method	p. 119
  Exercises	p. 120
  Notes	p. 124
  Implementation Issues	p. 125
  Solving Systems of Equations: LU-Factorization	p. 126
  Exploiting Sparsity	p. 130
  Reusing a Factorization	p. 136
  Performance Tradeoffs	p. 140
  Updating a Factorization	p. 141
  Shrinking the Bump	p. 145
  Partial Pricing	p. 146
  Steepest Edge	p. 147
  Exercises	p. 149
  Notes	p. 150
  Problems in General Form	p. 151
  The Primal Simplex Method	p. 151
  The Dual Simplex Method	p. 153
  Exercises	p. 159
  Notes	p. 160
  Convex Analysis	p. 161
  Convex Sets	p. 161
  Caratheodory's Theorem	p. 163
  The Separation Theorem	p. 165
  Farkas' Lemma	p. 167
  Strict Complementarity	p. 168
  Exercises	p. 170
  Notes	p. 171
  Game Theory	p. 173
  Matrix Games	p. 173
  Optimal Strategies	p. 175
  The Minimax Theorem	p. 177
  Poker	p. 181
  Exercises	p. 184
  Notes	p. 187
  Regression	p. 189
  Measures of Mediocrity	p. 189
  Multidimensional Measures: Regression Analysis	p. 191
  L[superscript 2]-Regression	p. 193
  L[superscript 1]-Regression	p. 195
  Iteratively Reweighted Least Squares	p. 196
  An Example: How Fast is the Simplex Method?	p. 198
  Which Variant of the Simplex Method is Best?	p. 202
  Exercises	p. 203
  Notes	p. 208
  Network-Type Problems	p. 211
  Network Flow Problems	p. 213
  Networks	p. 213
  Spanning Trees and Bases	p. 216
  The Primal Network Simplex Method	p. 221
  The Dual Network Simplex Method	p. 225
  Putting It All Together	p. 228
  The Integrality Theorem	p. 231
  Exercises	p. 232
  Notes	p. 240
  Applications	p. 241
  The Transportation Problem	p. 241
  The Assignment Problem	p. 243
  The Shortest-Path Problem	p. 244
  Upper-Bounded Network Flow Problems	p. 247
  The Maximum-Flow Problem	p. 250
  Exercises	p. 252
  Notes	p. 257
  Structural Optimization	p. 259
  An Example	p. 259
  Incidence Matrices	p. 261
  Stability	p. 262
  Conservation Laws	p. 264
  Minimum-Weight Structural Design	p. 267
  Anchors Away	p. 269
  Exercises	p. 272
  Notes	p. 272
  Interior-Point Methods	p. 275
  The Central Path	p. 277
  Warning: Nonstandard Notation Ahead	p. 277
  The Barrier Problem	p. 277
  Lagrange Multipliers	p. 280
  Lagrange Multipliers Applied to the Barrier Problem	p. 283
  Second-Order Information	p. 285
  Existence	p. 285
  Exercises	p. 287
  Notes	p. 289
  A Path-Following Method	p. 291
  Computing Step Directions	p. 291
  Newton's Method	p. 293
  Estimating an Appropriate Value for the Barrier Parameter	p. 294
  Choosing the Step Length Parameter	p. 295
  Convergence Analysis	p. 296
  Exercises	p. 302
  Notes	p. 306
  The KKT System	p. 307
  The Reduced KKT System	p. 307
  The Normal Equations	p. 308
  Step Direction Decomposition	p. 310
  Exercises	p. 313
  Notes	p. 313
  Implementation Issues	p. 315
  Factoring Positive Definite Matrices	p. 315
  Quasidefinite Matrices	p. 319
  Problems in General Form	p. 325
  Exercises	p. 331
  Notes	p. 331
  The Affine-Scaling Method	p. 333
  The Steepest Ascent Direction	p. 333
  The Projected Gradient Direction	p. 335
  The Projected Gradient Direction with Scaling	p. 337
  Convergence	p. 341
  Feasibility Direction	p. 343
  Problems in Standard Form	p. 344
  Exercises	p. 345
  Notes	p. 346
  The Homogeneous Self-Dual Method	p. 349
  From Standard Form to Self-Dual Form	p. 349
  Homogeneous Self-Dual Problems	p. 350
  Back to Standard Form	p. 360
  Simplex Method vs Interior-Point Methods	p. 363
  Exercises	p. 367
  Notes	p. 368
  Extensions	p. 371
  Integer Programming	p. 373
  Scheduling Problems	p. 373
  The Traveling Salesman Problem	p. 375
  Fixed Costs	p. 378
  Nonlinear Objective Functions	p. 378
  Branch-and-Bound	p. 380
  Exercises	p. 392
  Notes	p. 393
  Quadratic Programming	p. 395
  The Markowitz Model	p. 395
  The Dual	p. 399
  Convexity and Complexity	p. 402
  Solution Via Interior-Point Methods	p. 404
  Practical Considerations	p. 406
  Exercises	p. 409
  Notes	p. 411
  Convex Programming	p. 413
  Differentiable Functions and Taylor Approximations	p. 413
  Convex and Concave Functions	p. 414
  Problem Formulation	p. 414
  Solution Via Interior-Point Methods	p. 415
  Successive Quadratic Approximations	p. 417
  Merit Functions	p. 417
  Parting Words	p. 421
  Exercises	p. 421
  Notes	p. 423
  Source Listings	p. 425
  The Self-Dual Simplex Method	p. 426
  The Homogeneous Self-Dual Method	p. 429
  Answers to Selected Exercises	p. 433
  Bibliography	p. 435
  Index	p. 443
  Table of Contents provided by Syndetics. All Rights Reserved.

기본정보

ISBN	9780792373421 ( 0792373421 )
발행(출시)일자	2001년 05월 01일
쪽수	준비중