SOME APPLICATIONS OF THE THEORY OF DYNAMIC PROGRAMMING - A REVIEW
Abstract
An expository account of the theory of dynamic programming is provided. Two problems of rather simple form are considered: (1) (Optimal Allocation). We are given a resource, x, to divide into two parts, y and x-y. From y we obtain a return of g(y); from x-y a return of h(x-y). In so doing, we expend a certain amount of the original quantity and are left with a new quantity, ay + b(x-y), where 0 < a, b < 1. This process is now continued. The problem is to allocate at each stage so as to maximize the total return obtained over a finite or unbounded number of stages. (2) (Efficient Gold Mining). We are fortunate enough to possess two gold mines, Anaconda and Bonanza, the first of which contains an amount x of gold, while the second possesses an amount y. In addition, we have a rather delicate gold-mining machine which has the property that if used to mine gold in Anaconda, there is a probability p sub 1 that it will mine a fraction r sub 1 of the gold there and remain in working order, and a probability (1-p sub 1) that it will mine no gold and be damaged beyond repair. Similarly, Bonanza has associated the probabilities p sub 2 and (1-p sub 2) and the fraction r sub 2.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 14, 1954
- Accession Number
- AD0293679
Entities
People
- Richard E. Bellman
Organizations
- RAND Corporation