Dynamic Programming

Models and Applications

Eric V. Denardo

• Publisher: Dover Publications
• Year: 2012
• Print ISBN: 9780486428109
• eBook ISBN: 9780486150857
• Topic: Mathematics
• Subtopic: Discrete Mathematics
• Index: Mathematics

Designed both for those who seek an acquaintance with dynamic programming and for those wishing to become experts, this text is accessible to anyone who's taken a course in operations research. It starts with a basic introduction to sequential decision processes and proceeds to the use of dynamic programming in studying models of resource allocation. Subsequent topics include methods for approximating solutions of control problems in continuous time, production control, decision-making in the face of an uncertain future, and inventory control models. The final chapter introduces sequential decision processes that lack fixed planning horizons, and the supplementary chapters treat data structures and the basic properties of convex functions. 1982 edition. Preface to the Dover Edition.

1

INTRODUCTION TO SEQUENTIAL DECISION PROCESSES

DECISION MAKING
DYNAMIC PROGRAMMING
BEGINNINGS
SCOPE
ADVICE TO THE READER

DECISION MAKING

Nearly every facet of life entails a sequence of decisions. Managing one’s assets involves the evaluation of a never-ending stream of purchase, sales, and exchange opportunities. Managing a retail store involves a sequence of purchasing, pricing, and advertising decisions. Playing tennis entails a series of serves, returns, and volleys, all carefully interwoven. Driving to the store requires a sequence of accelerations, brakings, lane changes, and turns. Piloting a spaceship entails a sequence of maneuvers and course changes.

These sequential activities are ubiquitous, and they have some common features. Each has a purpose. An individual might drive with the intent of arriving quickly at his or her destination, without breaking the law. Many athletes compete for the satisfaction of winning. Business managers attempt to maximize profit.

In each of these activities there is interplay between constituent decisions. Making a purchase consumes capital and restricts future options. Igniting a spaceship’s rocket consumes fuel that cannot be used later.

In many cases, decisions must be made without knowing their outcomes. A driver cannot predict how others will react to his or her moves; if drivers could predict reactions, there would be no accidents. A tennis player does not know in advance whether a particular shot will be in bounds, or how it will be returned. Investors and gamblers make choices without knowing outcomes. Indeed, investing, gambling, and sporting events would lose their fascination if their outcomes could be foretold.

The term sequential decisions process is used to describe an activity that entails a sequence of actions taken toward some goal, often in the face of uncertainty. The activities just discussed are all sequential decision processes, as are so many facets of modern life.

DYNAMIC PROGRAMMING

Sequential decision processes as diverse as playing tennis and managing inventory seem to have little in common. Yet their mathematical representations share several important features. In fact, the subject known as dynamic programming was born of the realization that certain features recur again and again when sequential decision processes are analyzed. Dynamic programming is the collection of mathematical tools used to analyze sequential decision processes. This identifies dynamic programming as a branch of applied mathematics rather than as something more specific. The subject’s coherence results from the fact that it is pervaded by several themes. We shall see that these themes include the concept of states, the principle of optimality, and functional equations.

Dynamic programming can bear fruit in the form of insights or numbers. The insights usually come from theory, the numbers from computation. For instance, in an elementary inventory situation, one can determine that the optimal policy consists of drawing a line on a bin and refilling the bin each week to that line. This is the sort of insight that can be obtained by theory. It rules out more complex control policies. If one wishes to know where to draw the line, one must compute, usually on a digital computer.

We must note that some sequential decision processes lie beyond the reach of dynamic programming. Consider chess. This is a game of finitely many positions. A routine application of dynamic programming yields a system of one equation per position, and the solution to this equation system determines optimal play for both players. The trouble is that the number of equations (one per position) is astronomical, and there is virtually no hope that they will ever be solved on any computer.

BEGINNINGS

Dynamic programming is no exception to the rule that good ideas have deep roots. Ancestors to its functional equations can be traced through the history of mathematics. But the labors that give birth to the field of dynamic programming bear recent dates. They include Massé’s study (1946) of water resources; Wald’s study (1947) of sequential decision problems in statistics; a related study by Arrow, Blackwell, and Girshick (1949); studies of the control of inventories by Arrow, Harris, and Marshak (1951) and by Dvoretsky, Kiefer, and Wolfowitz (1952a, 1952b); and the study by Bellman (1952) of functional equations.

It was Bellman who seized upon the principle of optimality and, with remarkable ingenuity, used it to analyze hundreds of optimization problems in mathematics, engineering, economics, operations research, and other fields. Many of his contributions are compiled in his book on dynamic programming (1957a), others in his joint work with Dreyfus (Bellman and Dreyfus, 1962). Isaacs (1951), whose “tenet of transition” is another version of the principle of optimality, seems to merit a share of credit for recognizing the key role that this idea plays.

SCOPE

This volume is devoted to sequential decision processes that have definite “ends” at which decision making stops. These models are said to have definite planning horizons. They can be analyzed by induction, working backward from the end of the planning horizon to its beginning. Induction is the simplest mathematical tool, which might seem to connote that these models are low on intellectual fiber. Nothing of the sort — readers of this volume are offered plenty on which to chew.

A companion volume is devoted to sequential decision processes that have indefinite ends or, equivalently, indefinite planning horizons. That volume entails a higher level of mathematical sophistication, but no more ingenuity.

ADVICE TO THE READER

This volume is designed for both those who seek a passing acquaintance with dynamic programming and for those who wish to become expert. Elementary and advanced aspects of a subject are contained in the same chapter. The advanced material is confined to starred sections. It is recommended that most readers thumb through or skip the starred portions entirely, at least the first time through. Titles of starred sections are set in boldface type in each chapter’s contents page.

Supplements 1 and 2 concern data structures and convexity, respectively. These supplements are used extensively in the starred sections, but not in the unstarred ones.

Exercises are scattered throughout this volume, and they are placed where working them would do the most good, which is often in the middle of a development. Pause to try the exercises. If one troubles you, it may indicate that you have missed something on the preceding pages. Look back for clues.

2

THE PROTOTYPE SEQUENTIAL DECISION PROCESS

OVERVIEW
DIRECTED NETWORKS
SHORTEST AND LONGEST PATHS
SOME RECURRING FEATURES
REACHING
WHEN REACHING RUNS FASTER
SUMMARY
SHORTEST PATHS IN CYCLIC NETWORKS
BIBLIOGRAPHIC NOTES
PROBLEMS

Titles above in bold type concern advanced
or specialized subjects. These sections can
be omitted without loss of continuity.

OVERVIEW

Chapters 2 to 4 have two purposes. One is to study deterministic sequential decision processes, whose evolution is not affected by chance. The other is to acquaint you with the basic ideas that underlie and unify dynamic programming. Each of these ideas illuminates the others, but most beginners find all of them strange and alien.

The presentation reflects this state of affairs. Chapters 2 to 4 are more redundant than is usual in technical writing. This is intentional. It offers you multiple exposures to each basic idea. It allows you to think about each idea after having been exposed to the others.

The starred sections of each chapter contain more advanced topics that can be deferred or omitted.

DIRECTED NETWORKS

Sequential decision processes exist in many varieties, but all are elaborations of the simple prototype that is analyzed in this chapter. This prototype is an optimization problem in a directed network, a fact that obliges us to discuss networks first. However, the diversion pays dividends, as the notation, terminology, and pictographs of directed networks will prove useful time and again.

A directed network has an alluringly simple pictorial representation, but a slightly abstruse mathematical definition. Mathematically, a directed network consists of a nonempty set S of nodes and a subset T of the Cartesian product S x S. The elements of T are called directed arcs. This means that a directed arc is an ordered pair (i, j), where i and j are nodes. To see the picture, think of nodes i and j as circles with the symbols i and j inside, and think of directed arc (i, j) as a line connecting these circles, with an arrow pointing from i to j. Figure 2-1 depicts a network that has five nodes and six directed arcs. The nodes ...

Table of contents

• Title Page
• Copyright Page
• Dedication
• Table of Contents
• PREFACE TO THE DOVER EDITION
• PREFACE
• 1 - INTRODUCTION TO SEQUENTIAL DECISION PROCESSES
• 2 - THE PROTOTYPE SEQUENTIAL DECISION PROCESS
• 3 - ALLOCATION, MARGINAL ANALYSIS, AND LAGRANGE MULTIPLIERS
• 4 - STAGES, GRIDS, AND DISCRETIZING CONTROL PROBLEMS
• 5 - PRODUCTION CONTROL AND NETWORK FLOW
• 6 - A MARKOV DECISION MODEL
• 7 - INVENTORY CONTROL: (s, S)-POLICIES
• 8 - A DISCOUNTED MARKOV DECISION MODEL
• SUPPLEMENT 1 - DATA STRUCTURES
• SUPPLEMENT 2 - CONVEX FUNCTIONS
• BIBLIOGRAPHY
• INDEX
• DOVER BOOKS ON MATHEMATICS