Accession Number:

AD0606537

Title:

DYNAMIC PROGRAMMING, SUCCESSIVE APPROXIMATIONS AND VARIATIONAL PROBLEMS OF COMBINATORIAL NATURE

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CA

Personal Author(s):

Report Date:

1957-09-13

Pagination or Media Count:

10.0

Abstract:

This paper shows that a combination of dynamic programming gng and the classical meththod of successive approximations permits a systemattic study of various classes of combinatorial problems arising in scheduling theory, communication theory and network theory. Although the method cannot guarantee convergence to the actual solution, it furnishes a monotonic sequence of approximations by means of approximation in policy space. An important feature of the method is the use of the solution of sub-problems of considerable magnitude as steps in the approximation procedure. With the aid of digital computers and the techniques of dynamic programming, this is a feasible method. The HitchcockKoopmans transportation problem, an allocation problem, and the travelling salesman problem are discussed.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE