logo资料库

Linear Programming.Foundations and Extensions.4Ed.pdf

发布时间：2022-06-12 发布人：admin 分类：说明书 资料大小：5.14M 资料格式：pdf 举报 版权申诉
第1页 / 共421页
第2页 / 共421页
第3页 / 共421页
第4页 / 共421页
第5页 / 共421页
第6页 / 共421页
第7页 / 共421页
第8页 / 共421页
资料共421页，剩余部分请下载后查看
    Cover
    Preface
    Preface to 2nd Edition
    Preface to 3rd Edition
    Preface to 4th Edition
    Contents
    Part 1. Basic Theory: The Simplex Method and Duality
    Chapter 1. Introduction
    1. Managing a Production Facility
    1.1. Production Manager as Optimist
    1.2. Comptroller as Pessimist
    2. The Linear Programming Problem
    Exercises
    Notes
    Chapter 2. The Simplex Method
    1. An Example
    1.1. Dictionaries, Bases, Etc.
    2. The Simplex Method
    3. Initialization
    4. Unboundedness
    5. Geometry
    Exercises
    Notes
    Chapter 3. Degeneracy
    1. Definition of Degeneracy
    2. Two Examples of Degenerate Problems
    3. The Perturbation/Lexicographic Method
    4. Bland's Rule
    5. Fundamental Theorem of Linear Programming
    6. Geometry
    Exercises
    Notes
    Chapter 4. Efficiency of the Simplex Method
    1. Performance Measures
    2. Measuring the Size of a Problem
    3. Measuring the Effort to Solve a Problem
    4. Worst-Case Analysis of the Simplex Method
    5. Empirical Average Performance of the Simplex Method
    Exercises
    Notes
    Chapter 5. Duality Theory
    1. Motivation: Finding Upper Bounds
    2. The Dual Problem
    3. The Weak Duality Theorem
    4. The Strong Duality Theorem
    5. Complementary Slackness
    6. The Dual Simplex Method
    7. A Dual-Based Phase I Algorithm
    8. The Dual of a Problem in General Form
    9. Resource Allocation Problems
    10. Lagrangian Duality
    Exercises
    Notes
    Chapter 6. The Simplex Method in Matrix Notation
    1. Matrix Notation
    2. The Primal Simplex Method
    3. An Example
    3.1. First Iteration
    3.2. Second Iteration
    3.3. Third Iteration
    3.4. Fourth Iteration
    4. The Dual Simplex Method
    5. Two-Phase Methods
    6. Negative Transpose Property
    Exercises
    Notes
    Chapter 7. Sensitivity and Parametric Analyses
    1. Sensitivity Analysis
    1.1. Ranging
    2. Parametric Analysis and the Homotopy Method
    3. The Parametric Self-Dual Simplex Method
    Exercises
    Notes
    Chapter 8. Implementation Issues
    1. Solving Systems of Equations: LU-Factorization
    2. Exploiting Sparsity
    3. Reusing a Factorization
    4. Performance Tradeoffs
    5. Updating a Factorization
    6. Shrinking the Bump
    7. Partial Pricing
    8. Steepest Edge
    Exercises
    Notes
    Chapter 9. Problems in General Form
    1. The Primal Simplex Method
    2. The Dual Simplex Method
    Exercises
    Notes
    Chapter 10. Convex Analysis
    1. Convex Sets
    2. Carathéodory's Theorem
    3. The Separation Theorem
    4. Farkas' Lemma
    5. Strict Complementarity
    Exercises
    Notes
    Chapter 11. Game Theory
    1. Matrix Games
    2. Optimal Strategies
    3. The Minimax Theorem
    4. Poker
    Exercises
    Notes
    Chapter 12. Regression
    1. Measures of Mediocrity
    2. Multidimensional Measures: Regression Analysis
    3. L2-Regression
    4. L1-Regression
    5. Iteratively Reweighted Least Squares
    6. An Example: How Fast Is the Simplex Method?
    6.1. Random Problems
    Exercises
    Notes
    Chapter 13. Financial Applications
    1. Portfolio Selection
    1.1. Reduction to a Linear Programming Problem
    1.2. Solution via Parametric Simplex Method
    2. Option Pricing
    Exercises
    Notes
    Part 2. Network-Type Problems
    Chapter 14. Network Flow Problems
    1. Networks
    2. Spanning Trees and Bases
    3. The Primal Network Simplex Method
    4. The Dual Network Simplex Method
    5. Putting It All Together
    6. The Integrality Theorem
    6.1. König's Theorem
    Exercises
    Notes
    Chapter 15. Applications
    1. The Transportation Problem
    2. The Assignment Problem
    3. The Shortest-Path Problem
    3.1. Network Flow Formulation
    3.2. A Label-Correcting Algorithm
    3.2.1. Method of Successive Approximation
    3.2.2. Efficiency
    3.3. A Label-Setting Algorithm
    4. Upper-Bounded Network Flow Problems
    5. The Maximum-Flow Problem
    Exercises
    Notes
    Chapter 16. Structural Optimization
    1. An Example
    2. Incidence Matrices
    3. Stability
    4. Conservation Laws
    5. Minimum-Weight Structural Design
    6. Anchors Away
    Exercises
    Notes
    Part 3. Interior-Point Methods
    Chapter 17. The Central Path
    Warning: Nonstandard Notation Ahead
    1. The Barrier Problem
    2. Lagrange Multipliers
    3. Lagrange Multipliers Applied to the Barrier Problem
    4. Second-Order Information
    5. Existence
    Exercises
    Notes
    Chapter 18. A Path-Following Method
    1. Computing Step Directions
    2. Newton's Method
    3. Estimating an Appropriate Value for the Barrier Parameter
    4. Choosing the Step Length Parameter
    5. Convergence Analysis
    5.1. Measures of Progress
    5.2. Progress in One Iteration
    5.3. Stopping Rule
    5.4. Progress Over Several Iterations
    Exercises
    Notes
    Chapter 19. The KKT System
    1. The Reduced KKT System
    2. The Normal Equations
    3. Step Direction Decomposition
    Exercises
    Notes
    Chapter 20. Implementation Issues for Interior-Point Methods
    1. Factoring Positive Definite Matrices
    1.1. Stability
    2. Quasidefinite Matrices
    2.1. Instability
    3. Problems in General Form
    Exercises
    Notes
    Chapter 21. The Affine-Scaling Method
    1. The Steepest Ascent Direction
    2. The Projected Gradient Direction
    3. The Projected Gradient Direction with Scaling
    4. Convergence
    5. Feasibility Direction
    6. Problems in Standard Form
    Exercises
    Notes
    Chapter 22. The Homogeneous Self-Dual Method
    1. From Standard Form to Self-Dual Form
    2. Homogeneous Self-Dual Problems
    2.1. Step Directions
    2.2. Predictor-Corrector Algorithm
    2.3. Convergence Analysis
    2.4. Complexity of the Predictor-Corrector Algorithm
    2.5. The KKT System
    3. Back to Standard Form
    3.1. The Reduced KKT System
    4. Simplex Method vs. Interior-Point Methods
    Exercises
    Notes
    Part 4. Extensions
    Chapter 23. Integer Programming
    1. Scheduling Problems
    2. The Traveling Salesman Problem
    3. Fixed Costs
    4. Nonlinear Objective Functions
    5. Branch-and-Bound
    Exercises
    Notes
    Chapter 24. Quadratic Programming
    1. The Markowitz Model
    2. The Dual
    3. Convexity and Complexity
    4. Solution via Interior-Point Methods
    5. Practical Considerations
    Exercises
    Notes
    Chapter 25. Convex Programming
    1. Differentiable Functions and Taylor Approximations
    2. Convex and Concave Functions
    3. Problem Formulation
    4. Solution via Interior-Point Methods
    5. Successive Quadratic Approximations
    6. Merit Functions
    7. Parting Words
    Exercises
    Notes
    Appendix A. Source Listings
    1. The Self-Dual Simplex Method
    2. The Homogeneous Self-Dual Method
    Answers to Selected Exercises
    Bibliography
    Index
    International Series in Operations Research & Management Science Volume 196 Series Editor Frederick S. Hillier Stanford University, CA, USA Special Editorial Consultant Camille C. Price Stephen F. Austin State University, TX, USA For further volumes: http://www.springer.com/series/6161
    Robert J. Vanderbei Linear Programming Foundations and Extensions Fourth Edition 123
    Robert J. Vanderbei Department of Operations Research and Financial Engineering Princeton University Princeton, New Jersey, USA ISSN 0884-8289 ISBN 978-1-4614-7629-0 DOI 10.1007/978-1-4614-7630-6 Springer New York Heidelberg Dordrecht London ISBN 978-1-4614-7630-6 (eBook) Library of Congress Control Number: 2013939593 © Springer Science+Business Media New York 2014 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the Copyright Clearance Center. Violations are liable to prosecution under the respective Copyright Law. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publica- tion does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. While the advice and information in this book are believed to be true and accurate at the date of pub- lication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
    To Krisadee, Marisa and Diana
    Preface This book is about constrained optimization. It begins with a thorough treat- ment of linear programming and proceeds to convex analysis, network flows, integer programming, quadratic programming, and convex optimization. Along the way, dynamic programming and the linear complementarity problem are touched on as well. The book aims to be a first introduction to the subject. Specific examples and concrete algorithms precede more abstract topics. Nevertheless, topics covered are developed in some depth, a large number of numerical examples are worked out in detail, and many recent topics are included, most notably interior-point methods. The exercises at the end of each chapter both illustrate the theory and, in some cases, extend it. Prerequisites. The book is divided into four parts. The first two parts assume a background only in linear algebra. For the last two parts, some knowledge of multivariate calculus is necessary. In particular, the student should know how to use Lagrange multipliers to solve simple calculus problems in 2 and 3 dimensions. Associated software. It is good to be able to solve small problems by hand, but the problems one encounters in practice are large, requiring a computer for their solution. Therefore, to fully appreciate the subject, one needs to solve large (prac- tical) problems on a computer. An important feature of this book is that it comes with software implementing the major algorithms described herein. At the time of writing, software for the following five algorithms is available: • The two-phase simplex method as shown in Figure 6.1. • The self-dual simplex method as shown in Figure 7.1. • The path-following method as shown in Figure 18.1. • The homogeneous self-dual method as shown in Figure 22.1. • The long-step homogeneous self-dual method as described in Exercise 22.4. The programs that implement these algorithms are written in C and can be easily compiled on most hardware platforms. Students/instructors are encouraged to install and compile these programs on their local hardware. Great pains have been taken to make the source code for these programs readable (see Appendix A). In particular, the names of the variables in the programs are consistent with the notation of this book. vii
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料