Dynamic Programming

a branch of mathematics devoted to the theory and methods of solving multistage optional control problems.

Dynamic programming attempts to find for a control process, that control from among all possible controls which provides the extreme (largest or smallest) value of a criterion function representing a certain numerical characteristic of the process. The term “multistage” refers either to the multistage structure of a process or to the breakdown of a control into a number of sequential stages (steps) corresponding, as a rule, to various moments in time. Thus, in so-called “dynamic programming,” the word “programming” is understood to mean “decision-making,” or “planning,” and the word “dynamic” indicates the essential role of time and the sequential performance of operations in the processes and methods under investigation.

The methods of dynamic programming are an integral part of the methods used in studying operations (operations re-search) and are used both in problems of optimal planning and in solving various engineering problems (for example, in determining optimal dimensions of multistage rockets, in routing roads optimally, and so on).

Suppose, for example, that the control process of a certain system consists of m steps (stages) and that at step i the control y_i transforms the system from state x_i - 1 to a new state x_i, which depends onx_i 1 and y_i.

x_i = x_i(y_i, x_i - 1)

Thus, the control sequence y₁, y₂, … , y_m transforms the system from an initial state x₀ into a final state x_m. It is necessary to select x₀ and y₁ … , y_m such that the function

attains its maximum value F*. The basic method of dynamic programming is to reduce this general problem to a sequence of simpler extremal problems. By using the so-called principle of optimality formulated by the American mathematician R. Bellman, it is easy to obtain the basic recurrence equation:

Thus, the method of dynamic programming makes it necessary to solve this recurrence relation. In the solution process, the sequence of stages is gone through twice: the first time from the end to the beginning (optimal values are found for F* and x₀*) and the second time, from the beginning to the end (the optional control sequence y₁*, … , y_m* is found).

The methods of dynamic programming are used not only in discrete but also in continuous control processes, for example, in processes where decisions must be made at every moment of a certain interval of time. Thus dynamic programming has offered a new approach to problems in the calculus of variations.

Although the method of dynamic programming allows a radical initial simplification of many important problems, its direct application still entails cumbersome computations. Approximate methods of dynamic programming are being worked out to overcome these difficulties.