SHORTEST ROUTE METHODS FOR FINITE STATE SPACE, DETERMINISTIC DYNAMIC PROGRAMMING PROBLEMS.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1967
- Accession Number
- AD0656612
Entities
People
- Jeremy F. Shapiro
Organizations
- Massachusetts Institute of Technology