SOME APPLICATIONS OF THE THEORY OF DYNAMIC PROGRAMMING - A REVIEW
RAND CORP SANTA MONICA CA
Pagination or Media Count:
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 gy from x-y a return of hx-y. In so doing, we expend a certain amount of the original quantity and are left with a new quantity, ay bx-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.
- Information Science