DYNAMIC PROGRAMMING, SUCCESSIVE APPROXIMATIONS AND VARIATIONAL PROBLEMS OF COMBINATORIAL NATURE

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 13, 1957
Accession Number
AD0606537

Entities

People

  • Richard E. Bellman

Organizations

  • RAND Corporation

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Computer Programming
  • Computers
  • Convergence
  • Digital Computers
  • Dynamic Programming
  • Equations
  • Guarantees
  • Mathematics
  • Network Science
  • Scheduling (Production)
  • Sequences
  • Transportation

Readers

  • Operations Research

Technology Areas

  • Space