Introduction to Dynamic Programming

Introduction to Dynamic Programming

International Series in Modern Applied Mathematics and Computer Science, Volume 1

1st Edition - January 1, 1981

Write a review

  • Authors: Leon Cooper, Mary W. Cooper
  • eBook ISBN: 9781483136622

Purchase options

Purchase options
DRM-free (PDF)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order

Description

Introduction to Dynamic Programming introduces the reader to dynamic programming and presents the underlying mathematical ideas and results, as well as the application of these ideas to various problem areas. A large number of solved practical problems and computational examples are included to clarify the way dynamic programming is used to solve problems. A consistent notation is applied throughout the text for the expression of quantities such as state variables and decision variables. This monograph consists of 10 chapters and opens with an overview of dynamic programming as a particular approach to optimization, along with the basic components of any mathematical optimization model. The following chapters discuss the application of dynamic programming to variational problems; functional equations and the principle of optimality; reduction of state dimensionality and approximations; and stochastic processes and the calculus of variations. The final chapter looks at several actual applications of dynamic programming to practical problems, such as animal feedlot optimization and optimal scheduling of excess cash investment. This book should be suitable for self-study or for use as a text in a one-semester course on dynamic programming at the senior or first-year, graduate level for students of mathematics, statistics, operations research, economics, business, industrial engineering, or other engineering fields.

Table of Contents


  • Chapter 1. Introduction

    1.1. Optimization

    1.2. Separable Functions

    1.3. Convex and Concave Functions

    1.4. Optima of Convex and Concave Functions

    1.5. Dynamic Programming

    1.6. Dynamic Programming: Advantages and Limitations

    1.7. The Development of Dynamic Programming

    Exercises—Chapter 1

    Chapter 2. Some Simple Examples

    2.1. Introduction

    2.2. The Wandering Applied Mathematician

    2.3. The Wandering Applied Mathematician (Continued)

    2.4. A Problem in "Division"

    2.5. A Simple Equipment Replacement Problem

    2.6. Summary

    Exercises—Chapter 2

    Chapter 3. Functional Equations: Basic Theory

    3.1. Introduction

    3.2. Sequential Decision Processes

    3.3. Functional Equations and the Principle of Optimality

    3.4. The Principle of Optimality—Necessary and Sufficient Conditions

    Exercise—Chapter 3

    Chapter 4. One-dimensional Dynamic Programming: Analytic Solutions

    4.1. Introduction

    4.2. A Prototype Problem

    4.3. Some Variations of the Prototype Problem

    4.4. Some Generalizations of the Prototype Problem

    4.5. Some Generalizations

    4.6. A Problem in Renewable Resources

    4.7. Multiplicative Constraints and Functions

    4.8. Some Variations on State Functions

    4.9. A Minimax Objective Function

    Exercises—Chapter 4

    Chapter 5. One-dimensional Dynamic Programming: Computational Solutions

    5.1. Introduction

    5.2. A Prototype Problem

    5.3. An Example of the Computational Process

    5.4. The Computational Effectiveness of Dynamic Programming

    5.5. An Integer Nonlinear Programming Problem

    5.6. Computation with Continuous Variables

    5.7. Convex and Concave Φj(xj)

    5.8. Equipment Replacement Problems

    5.9. Some Integer Constrained Problems

    5.10. A Deterministic Inventory Problem—Forward and Backward Recursion

    Exercises—Chapter 5

    Chapter 6. Multidimensional Problems

    6.1. Introduction

    6.2. A Nonlinear Allocation Problem

    6.3. A Nonlinear Allocation Problem with Several Decision Variables

    6.4. An Equipment Replacement Problem

    6.5. Some Investment Problems

    6.6. A Stochastic Decision Problem

    6.7. The Traveling Salesman Problem

    6.8. A Multicomponent Reliability Problem

    6.9. A Problem in Product Development and Planning

    6.10. A Smoothing Problem

    6.11. Operation of a Chemical Reactor

    Exercises—Chapter 6

    Chapter 7. Reduction of State Dimensionality and Approximations

    7.1. Introduction

    7.2. Lagrange Multipliers and Reduction of State Variables

    7.3. Method of Successive Approximations

    7.4. Approximation in Policy and Function Space

    7.5. Polynomial Approximation in Dynamic Programming

    7.6. Reduction of Dimensionality and Expanding Grids

    7.7. A New Method for Reduction of Dimensionality

    Exercises—Chapter 7

    Chapter 8. Stochastic Processes and Dynamic Programming

    8.1. Introduction

    8.2. A Stochastic Allocation Problem—Discrete Case

    8.3. A Stochastic Allocation Problem—Continuous Case

    8.4. A General Stochastic Inventory Model

    8.5. A Stochastic Production Scheduling and Inventory Control Problem

    8.6. Markov Processes

    8.7. Markovian Sequential Decision Processes

    8.8. The Policy Iteration Method of Howard

    Exercises—Chapter 8

    Chapter 9. Dynamic Programming and the Calculus of Variations

    9.1. Introduction

    9.2. Necessary and Sufficient Conditions for Optimality

    9.3. Boundary Conditions and Constraints

    9.4. Practical Difficulties of the Calculus of Variations

    9.5. Dynamic Programming in Variational Problems

    9.6. Computational Solution of Variational Problems by Dynamic Programming

    9.7. A Computational Example

    9.8. Additional Variational Problems

    Exercises—Chapter 9

    Chapter 10. Applications of Dynamic Programming

    10.1. Introduction

    10.2. Municipal Bond Coupon Schedules

    10.3. Expansion of Electric Power Systems

    10.4. The Design of a Hospital Ward

    10.5. Optimal Scheduling of Excess Cash Investment

    10.6. Animal Feedlot Optimization

    10.7. Optimal Investment in Human Capital

    10.8. Optimal Crop Supply

    10.9. A Style Goods Inventory Model

    Appendix. Sets, Convexity, and ^-Dimensional Geometry

    A.1. Sets and Set Notation

    A.2. n-Dimensional Geometry and Sets

    A.3. Convex Sets

    References

    Index

Product details

  • No. of pages: 300
  • Language: English
  • Copyright: © Pergamon 1981
  • Published: January 1, 1981
  • Imprint: Pergamon
  • eBook ISBN: 9781483136622

About the Authors

Leon Cooper

Mary W. Cooper

About the Editor

E. Y. Rodin

Ratings and Reviews

Write a review

There are currently no reviews for "Introduction to Dynamic Programming"