DYNAMIC PROGRAMMING, SUCCESSIVE APPROXIMATIONS AND VARIATIONAL PROBLEMS OF COMBINATORIAL NATURE
RAND CORP SANTA MONICA CA
Pagination or Media Count:
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.
- Operations Research