
Dynamic Programming
I have a problem that I don't know how to start.
An oil company has 6 units of money available for exploration of three sites. If oil is present at a site, the probability of finding it is a function of the funds allocated for exploring the site, as shown in the table.
Units allocated
0 1 2 3 4 5 6

Site 1: 0 .1 .2 .3 .4 .5 .7
Site 2: 0 .1 .3 .5 .6 .7 .8
Site 3: 0 0 .2 .4 .6 .8 .9
The probably that oil exists at the sites 1, 2, and 3, are 0.2, 0.4, and 0.5, respectively. Using a dynamicprogramming approach, determine how much money should be allocated to exploration of each site to maximize the probability of discovering oil. Treat this as a threestage process, in which stage j is allocation of money to site j. Use the following definitions:
$\displaystyle x_{j}$ = number of units of money allocated to site j
$\displaystyle P_{j} (x_{j})$ = probability of finding oil at site j when $\displaystyle x_{j} $ is allocated, given that oil exists
$\displaystyle q_{j}$ = probability that oil exists at site j
u = number of units of money remaining
$\displaystyle m_{j} (u) $= minimum probability of not finding oil, given that the company is in state u at the start of stage j