• формат pdf
  • размер 2.29 МБ
  • добавлен 01 ноября 2011 г.
Vanderbei R.J. Linear Programming. Foundations and Extensions
Princeton University, 2001, -466 pp.

This book is about constrained optimization. It begins with a thorough treatment 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 (practical) 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 17.1.
The homogeneous self-dual method as shown in Figure 21.1.
The long-step homogeneous self-dual method as described in Exercise 21.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.
There are two ways to run these programs. The first is to prepare the input in a standard computer-file format, called MPS format, and to run the program using such a file as input. The advantage of this input format is that there is an archive of problems stored in this format, called the NETLIB suite, that one can download and use immediately (a link to the NETLIB suite can be found at the web site mentioned below). But, this format is somewhat archaic and, in particular, it is not easy to create these files by hand. Therefore, the programs can also be run from within a problem modeling system called AMPL. AMPL allows one to describe mathematical programming problems using an easy to read, yet concise, algebraic notation. To run the programs within AMPL, one simply tells AMPL the name of the solver-program before asking that a problem be solved. The text that describes AMPL, (Fourer et al. 1993), makes an excellent companion to this book. It includes a discussion of many practical linear programming problems. It also has lots of exercises to hone the modeling skills of the student.


Part
1. Basic Theory—The Simplex Method and Duality
Introduction
The Simplex Method
Degeneracy
Efficiency of the Simplex Method
Duality Theory
The Simplex Method in Matrix Notation
Sensitivity and Parametric Analyses
Implementation Issues
Problems in General Form
Convex Analysis
Game Theory
Regression
Part
2. Network-Type Problems
Network Flow Problems
Applications
Structural Optimization
Part
3. Interior-Point Methods
The Central Path
A Path-Following Method
The KKT System
Implementation Issues
The Affine-Scaling Method
The Homogeneous Self-Dual Method
Part
4. Extensions
Integer Programming
Quadratic Programming
Convex Programming
A. Source Listings
Смотрите также

Dantzig G., Thapa M. Linear programming. Vol.1. Introduction

  • формат pdf
  • размер 2.13 МБ
  • добавлен 15 декабря 2011 г.
Springer – 1997, 474 pages Linear programming and its generalization, mathematical programming, can be viewed as part of a great revolutionary development that has given mankind the ability to state general goals and lay out a path of detailed decisions to be taken in order to best achieve these goals when faced with practical situations of great complexity. The tools for accomplishing this are the models that formulate real-world problems in det...

Dantzig G., Thapa M. Linear Programming. Vol.2. Theory and extensions

  • формат pdf
  • размер 2.36 МБ
  • добавлен 15 декабря 2011 г.
Springer – 2003, 474 pages Linear Programming 2 continues where Linear Programming 1 left o?. We assume that the reader has an introductory knowledge of linear programming, for example has read Linear Programming 1: Introduction (or its equivalent) and has knowledge of linear algebra (reviewed in the appendices in Linear Programming 1). In this volume, we prove all theorems stated and those that were sketched but not proved in Linear Programming...

Ferris M.C. Linear Programming with MATLAB

  • формат pdf
  • размер 4.4 МБ
  • добавлен 08 января 2012 г.
Publisher: Society for Industrial Mathematics | 2008 | ISBN10: 0898716438 | 280 pages MPS-SIAM Series on Optimization This textbook provides a self-contained introduction to linear programming using MATLAB® software to elucidate the development of algorithms and theory. Early chapters cover linear algebra basics, the simplex method, duality, the solving of large linear problems, sensitivity analysis, and parametric linear programming. In later ch...

Kolman B., Beck R.E. Elementary Linear Programming with Applications

  • формат pdf
  • размер 15.98 МБ
  • добавлен 31 марта 2011 г.
Academic Press, 1995. - 449 Pages. Linear programming finds the least expensive way to meet given needs with available resources. Its results are used in every area of engineering and commerce: agriculture, oil refining, banking, and air transport. Authors Kolman and Beck present the basic notions of linear programming and illustrate how they are used to solve important common problems. The software on the included disk leads students step-by-st...

Matou?ek J., Gartner B. Understanding and Using Linear Programming

  • формат pdf
  • размер 2.19 МБ
  • добавлен 19 января 2011 г.
Springer-Verlag Berlin Heidelberg, 2007. 226 p. What Is It, and What For? A Linear Program. What Can Be Found in This Book. Linear Programming and Linear Algebra. Significance and History of Linear Programming. Examples. Optimized Diet: Wholesome and Cheap? Flow in a Network. ce Cream All Year Round. Fitting a Line. Separation of Points. Largest Disk in a Convex Polygon. Cutting Paper Rolls. nteger Programming and LP Relaxation. nteger Programmin...

Rao S.S. Engineering optimization: theory and practice

  • формат pdf
  • размер 12.42 МБ
  • добавлен 05 марта 2011 г.
John Wiley & Sons, 2009. 813 p. 4th ed. ISBN 978-0-470-18352-6. Contents. Preface. Introduction to Optimization. Classical Optimization Techniques. Linear Programming I: Simplex Method. Linear Programming II: Additional Topics and Extensions. Nonlinear Programming I: One-Dimensional Minimization Methods. Nonlinear Programming II: Unconstrained Optimization Techniques. Nonlinear Programming III: Constrained Optimization Techniques. Geometric P...

Sniedovich M. Dynamic Programming: Foundations and Principles

  • формат pdf
  • размер 2.91 МБ
  • добавлен 04 июня 2011 г.
CRC, 2010. - 624 p. (Second Edition) Incorporating a number of the author’s recent ideas and examples, Dynamic Programming: Foundations and Principles, Second Edition presents a comprehensive and rigorous treatment of dynamic programming. The author emphasizes the crucial role that modeling plays in understanding this area. He also shows how Dijkstra’s algorithm is an excellent example of a dynamic programming algorithm, despite the impression g...

Sultan A. Linear Programming: An Introduction with Applications

  • формат djvu
  • размер 3.51 МБ
  • добавлен 04 января 2012 г.
Acаdemic Prеss, 1993. - 568 pages. This book gives a complete, concise introduction to the theory and applications of linear programming. It emphasizes the practical applications of mathematics, and makes the subject more accessible to individuals with varying mathematical abilities. It is one of the first rigorous linear programming texts that does not require linear algebra as a prerequisite. In addition, this text contains a floppy disk cont...

Thie P.R., Keough G.E. An Introduction to Linear Programming and Game Theory

  • формат pdf
  • размер 14.61 МБ
  • добавлен 23 октября 2011 г.
Wiley, 2008. - 480 pages. 3 edition An Introduction to Linear Programming and Game Theory, Third Edition presents a rigorous, yet accessible, introduction to the theoretical concepts and computational techniques of linear programming and game theory. Now with more extensive modeling exercises and detailed integer programming examples, this book uniquely illustrates how mathematics can be used in real-world applications in the social, life, and...

Vanderbei R.J. Linear Programming: Foundations and Extensions

  • формат pdf
  • размер 2.6 МБ
  • добавлен 15 декабря 2011 г.
Publisher: Springer; 3rd ed. Edition | 2007 | ISBN10: 0387743871 | 464 pages Linear Programming: Foundations and Extensions is an introduction to the field of optimization. The book emphasizes constrained optimization, beginning with a substantial treatment of linear programming, and proceeding to convex analysis, network flows, integer programming, quadratic programming, and convex optimization. The book is carefully written. Specific examples...