Accession Number : AD0656612

Title :   SHORTEST ROUTE METHODS FOR FINITE STATE SPACE, DETERMINISTIC DYNAMIC PROGRAMMING PROBLEMS.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER

Personal Author(s) : Shapiro,Jeremy F.

Report Date : JUN 1967

Pagination or Media Count : 76

Abstract : A general finite state space, deterministic dynamic programming model with either a finite or infinite planning horizon is viewed as a network optimization problem. Optimal strategies for the model are characterized by optimal (minimal discounted or average cost) paths in the network. Shortest route type algorithms are constructed which find optimal paths of infinite length. Shortest route methods are also exploited in reducing the work of backward iteration in finding optimal paths of finite length. More important, however, is the fact that for finite planning horizons of sufficient length, any optimal immediate decision must also be an immediate decision that is optimal when faced with an infinite horizon. Thus, in the sense of selecting an optimal immediate decision, successive approximation of an optimal infinite horizon strategy by optimal finite horizon strategies exhibits finite convergence. Upper bounds on how long a time horizon is sufficiently long for the convergences to occur are developed. In addition, tests are given for detecting when this convergence of the backward iterative procedure has been effected. Finally, results on the form of optimal paths of any length are given. (Author)

Descriptors :   (*DYNAMIC PROGRAMMING, *OPERATIONS RESEARCH), (*MANAGEMENT PLANNING AND CONTROL, OPTIMIZATION), COSTS, ALGORITHMS, ITERATIONS, DECISION MAKING, CONVERGENCE, APPROXIMATION(MATHEMATICS), ITERATIONS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE