Richard Bellman - Applied Dynamic Programming

DYNAMIC PROGRAMMING

RICHARD BELLMAN

DOVER PUBLICATIONS, INC.

Mineola, New York

To Betty-Jo

whose decision processes defy analysis

Copyright

Introduction copyright 2003 by Eric V. Denardo

All rights reserved.

Bibliographical Note

This Dover edition, first published in 2003, is an unabridged reprint of the sixth (1972) printing of the work first published by Princeton University Press, Princeton, New Jersey, in 1957. A new Introduction has been written specially for this edition.

Library of Congress Cataloging-in-Publication Data

Bellman, Richard Ernest, 1920

Dynamic programming / Richard Bellman.

p. cm.

Originally published: Princeton, N.J. : Princeton, University Press, 1957.

Includes bibliographical references and indexes.

ISBN 0-486-42809-5 (pbk.)

1. Dynamic programming. I. Title.

QA402.5 .B438 2003

519.703dc21

2002072879

Manufactured in the United States of America
Dover Publications, Inc., 31 East 2nd Street, Mineola, N.Y. 11501

Introduction to the Dover Edition

IN THIS STUNNING BOOK, first published in 1957, Richard E. Bellman described, with grace and clarity, a potent method for solving optimization problems that entail sequences of decisions, and he applied this method to a wide range of subjects. The language he introduced to describe this methodfunctional equation, principle of optimality, multistage decision problem, states, embedding, dynamic programminghas now been adopted by computer science, control, economics, engineering, finance, operations research, mathematics, and statistics. This is surely one of the most influential mathematics books of the postwar era.

Typically, a good mathematics bookand this is a very good mathematics booksurveys a field whose fundamentals are deeply understood. By contrast, in this book Bellman described a research program that he was avidly pursuing. By writing it, he generously invited other researchers to jump in. Many did. It is no overstatement to say that Dynamic Programming launched a thousand professorships.

In the decades that followed its initial publication, the mathematics of dynamic programming has matured, its fields of application have evolved, and the subject has become better understood. A goodly number of introductory accounts of dynamic programming now exist, and beginning students may be better served by one of them.

Other than for its place in history, is there good reason to read this book? Yes! Much of it remains as fresh and vital to those of us who are familiar with the subject as Mozarts music is to those of us who listen to it repeatedly. Bellmans Preface is the best account Ive found of the scope of dynamic programming. The analysis within each chapter is a refreshingly honest and lucid foray into its central issues. The problem set at the end of each chapter is a rich lode of applications and research topics. In concert, they remind us of the power of the methods, of what has been accomplished, and of what remains to do.

Bellman chose his language extraordinary well, and yet functional equation is less descriptive than optimality equation. He might agree that we should switch to the latter. In retrospect, Bellman would also cite Rufus Isaacs for his tenet of transition (Isaacs, Games of Pursuit, P-257, The Rand Corporation, Santa Monica, 1951), which is quite like Bellmans principle of optimality.

ERIC V. DENARDO
Professor of Operations Research
Yale University

Preface

The purpose of this work is to provide an introduction to the mathematical theory of multi-stage decision processes. Since these constitute a somewhat formidable set of terms we have coined the term dynamic programming to describe the subject matter. Actually, as we shall see, the distinction involves more than nomenclature. Rather, it involves a certain conceptual framework which furnishes us a new and versatile mathematical tool for the treatment of many novel and interesting problems both in this new discipline and in various parts of classical analysis. Before expanding upon this theme, let us present a brief discussion of what is meant by a multi-stage decision process.

Let us suppose that we have a physical system S whose state at any time t is specified by a vector p. If we are in an optimistic frame of mind we can visualize the components of p to be quite definite quantities such as Cartesian coordinates, or position and momentum coordinates, or perhaps volume and temperature, or if we are considering an economic system, supply and demand, or stockpiles and production capacities. If our mood is pessimistic, the components of p may be supposed to be probability distributions for such quantities as position and momentum, or perhaps moments of a distribution.

In the course of time, this system is subject to changes of either deterministic or stochastic origin which, mathematically speaking, means that the variables describing the system undergo transformations. Assume now that in distinction to the above we have a process in which we have a choice of the transformations which may be applied to the system at any time. A process of this type we call a decision process, with a decision equivalent to a transformation. If we have to make a single decision, we call the process a single-stage process; if a sequence of decisions, than we use the term multi-stage decision process.

The distinction, of course, is not hard and fast. The choice of a point in three-dimensional space may be considered to be a single-stage process wherein we choose (x, y, z), or a multi-stage process where we choose first x, then y, and then z.

There are a number of multi-stage processes which are quite familiar to us. Perhaps the most common are those occurring in card games, such as the bidding system in contract bridge, or the raise-counter-raise system of poker with its delicate overtones of bluffing. On a larger scale, we continually in our economic life engage in multi-stage decision processes in connection with investment programs and insurance policies. In the scientific world, control processes and the design of experiments furnish other examples.

The point we wish to make is that in modern life, in economic, industrial, scientific and even political spheres, we are continually surrounded by multi-stage decision processes. Some of these we treat on the basis of experience, some we resolve by rule-of-thumb, and some are too complex for anything but an educated guess and a prayer.

Unfortunately for the peace of mind of the economist, industrialist, and engineer, the problems that have arisen in recent years in the economic, industrial, and engineering fields are too vast in portent and extent to be treated in the haphazard fashion that was permissible in a more leisurely bygone era. The price of tremendous expansion has become extreme precision.

These problems, although arising in a multitude of diverse fields, share a common propertythey are exceedingly difficult. Whether they arise in the study of optimal inventory or stock control, or in an input-output analysis of a complex of interdependent industries, in the scheduling of patients through a medical clinic or the servicing of aircraft at an airfield, the study of logistics or investment policies, in the control of servo-mechanisms, or in sequential testing, they possess certain common thorny features which stretch the confines of conventional mathematical theory.

It follows that new methods must be devised to meet the challenge of these new problems, and to a mathematician nothing could be more pleasant. It is a characteristic of this species that its members are never so happy as when confronted by problems which cannot be solvedimmediately. Although the day is long past when anyone seriously worried about the well of mathematical invention running dry, it is still nonetheless a source o great delight to see a vast untamed jungle of difficult and significant problems, such as those furnished by the theory of multi-stage decision processes, suddenly appear before us.