×

Dynamic programming. (English) Zbl 0917.90282

Avriel, M. (ed.) et al., Mathematical programming for industrial engineers. New York, NY: Marcel Dekker. 307-384 (1996).
Summary: This chapter surveys dynamic programming from the perspective of industrial and systems engineering. The writer has chosen an inductive style. Rather than presenting general ideas and then applying them to examples, the writer presents a series of examples and abstracts general ideas from them. These examples touch issues of interest to industrial engineers – project management, production planning, and capacity expansion, to name three. The aims of this chapter are to show what dynamic programming is, when it is useful, and how to make use of it.
The key to dynamic programming is an object with the odd name “functional equation”. A functional equation is a particular type of recursion. But what is a recursion? A section of this chapter is devoted to that question. Recursions are vital to dynamic programming, and their uses outside dynamic programming are legion.
Section 2 focuses on recursions. It sets the stage for what follows. Section 3 presents the simplest types of problem for which dynamic programming is appropriate. These are shortest- and longest-path problems in networks. Section 4 describes the basic ideas of dynamic programming, which are states, functional equations, and the principle of optimality. It uses the prior examples to illustrate these ideas.
Sections 2 through 4 prepare the reader for three different avenues of study. To develop the art of formulating optimization problems as dynamic programs, read Section 5. To see how dynamic programming is used in deterministic settings, read Sections 6 through 8. To see how dynamic programming is used in decision making under uncertainty, read Sections 9 through 11. Section 12 summarizes the chapter and discusses the limitations of dynamic programming. Section 13 provides a guide to the literature on which this chapter is based.
For the entire collection see [Zbl 0991.90500].

MSC:

90C39 Dynamic programming
90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
PDFBibTeX XMLCite