Optimization Techniques: An Introduction

ISBN-13: 9781461394600 / Angielski / Miękka / 2011 / 502 str.

L. R. Foulds

Opis

Optimization is the process by which the optimal solution to a problem, or optimum, is produced. The word optimum has come from the Latin word optimus, meaning best. And since the beginning of his existence Man has strived for that which is best. There has been a host of contributions, from Archimedes to the present day, scattered across many disciplines. Many of the earlier ideas, although interesting from a theoretical point of view, were originally of little practical use, as they involved a daunting amount of com- putational effort. Now modern computers perform calculations, whose time was once estimated in man-years, in the figurative blink of an eye. Thus it has been worthwhile to resurrect many of these earlier methods. The advent of the computer has helped bring about the unification of optimization theory into a rapidly growing branch of applied mathematics. The major objective of this book is to provide an introduction to the main optimization tech- niques which are at present in use. It has been written for final year undergrad- uates or first year graduates studying mathematics, engineering, business, or the physical or social sciences. The book does not assume much mathemati- cal knowledge. It has an appendix containing the necessary linear algebra and basic calculus, making it virtually self-contained. This text evolved out of the experience of teaching the material to finishing undergraduates and beginning graduates.

Spis treści

1 Introduction.- 1.1 Motivation for Studying Optimization,.- 1.2 The Scope of Optimization,.- 1.3 Optimization as a Branch of Mathematics.- 1.4 The History of Optimization.- 1.5 Basic Concepts of Optimization.- 2 Linear Programming.- 2.1 Introduction.- 2.2 A Simple L.P. Problem.- 2.3 The General L.P. Problem.- 2.4 The Basic Concepts of Linear Programming.- 2.5 The Simplex Algorithm.- 2.6 Duality and Postoptimal Analysis.- 2.7 Special Linear Program.- 2.8 Exercises.- 3 Advanced Linear Programming Topics.- 3.1 Efficient Computational Techniques for Large L.P. Problems.- 3.2 The Revised Simplex Method.- 3.3 The Dual Simplex Method.- 3.4 The Primal-Dual Algorithm.- 3.5 Dantzig-Wolfe Decomposition.- 3.6 Parametric Programming.- 3.7 Exercises.- 4 Integer Programming.- 4.1 A Simple Integer Programming Problem.- 4.2 Combinatorial Optimization.- 4.3 Enumerative Techniques.- 4.4 Cutting Plane Methods.- 4.5 Applications of Integer Programming.- 4.6 Exercises.- 5 Network Analysis.- 5.1 The Importance of Network Models.- 5.2 An Introduction to Graph Theory.- 5.3 The Shortest Path Problem.- 5.4 The Minimal Spanning Tree Problem.- 5.5 Flow Networks.- 5.6 Critical Path Scheduling.- 5.7 Exercises.- 6 Dynamic Programming.- 6.1 Introduction.- 6.2 A Simple D.P. Problem.- 6.3 Basic D.P. Structure.- 6.4 Multiplicative and More General Recursive Relationships.- 6.5 Continuous State Problems.- 6.6 The Direction of Computations.- 6.7 Tabular Form.- 6.8 Multi-state Variable Problems and the Limitations of D.P..- 6.9 Exercises.- 7 Classical Optimization.- 7.1 Introduction.- 7.2 Optimization of Functions of One Variable.- 7.3 Optimization of Unconstrained Functions of Several Variables,.- 7.4 Optimization of Constrained Functions of Several Variables.- 7.5 The Calculus of Variations, 7.6 Exercises.- 8 Nonlinear Programming.- 8.1 Introduction.- 8.2 Unconstrained Optimization.- 8.3 Constrained Optimization.- 8.4 Exercises.- 9 Appendix.- 9.1 Linear Algebra.- 9.2 Basic Calculus.- 9.3 Further Reading.- References.- Solutions to Selected Exercises.