# Dynamic Programming

• Dec 8th 2009, 12:37 PM
gigi12
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 dynamic-programming approach, determine how much money should be allocated to exploration of each site to maximize the probability of discovering oil. Treat this as a three-stage 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