Many optimization problems that arise naturally in applications involve scenarios where a sequence of interrelated decisions are to be made. Typically, these decisions are to be made over time. As examples, in a production-planning problem, one has to schedule a production level for every period in a given planning horizon (possibly infinite); and in an investment problem, one may need to assemble a new portfolio at the beginning of each day. In general, however, the required decisions may have nothing to do with time. This would be the case, for example, in deciding whether to include particular individuals in the formation of a committee; that is, the inclusion or exclusion of each individual in a pool of candidates is a decision.

In the first part of this course, we learned that many of these problems can be formulated and solved using linear programming. However, we have also learned that a critical limitation of a linear-programming formulation is that the objective function and the constraints are required to be linear. It is therefore desirable to study solution methods for optimization problems where the linearity assumption is either inappropriate or unreasonable.

Dynamic programming (DP) is a widely-used mathematical method for solving linear and nonlinear optimization problems. The term "dynamic" originates from the fact that in most applications, the method is used to derive a sequence of optimal decisions that are adapted to scenario changes that occur dynamically over time.

Loosely put, the idea behind the method is to obtain the solution to a problem by working backward from the end of the problem (where only one last decision is to be made) toward the beginning of the problem (where no decision has been made). In other words, the method is "recursive" in nature, in that the solution of a large problem is broken into the solution of a sequence of interrelated smaller, more tractable problems.

In contrast to linear programming, a dynamic programming formulation does not require any linearity assumptions. Consequently, the method is applicable to a wider range of problems. This versatility is certainly quite welcome. It is, however, not without a price, in that the formulation of an optimization problem as a dynamic program is highly problem specific. For this reason, dynamic-programming formulations are often considered art work.

In order to develop a sufficient level of understanding and insight regarding the structure of dynamic programs, we will describe a collection of representative examples. These examples are given in the ensuing sections. It is hoped that through a careful study of these examples, you will be able to acquire enough skill to formulate and solve optimization problems by dynamic programming.