Consider a supermarket chain that has purchased 6 gallons of milk from a local dairy. The chain must allocate the 6 gallons to its three stores. If a store sells a gallon of milk, then the chain receives revenue of $2. Any unsold milk is worth just $.50. Unfortunately, the demand for milk is uncertain, and is given in the following table:
The goal of the chain is to maximize the expected revenue from these 6 gallons. (This is not the only possible objective, but a reasonable one.)
Note that this is quite similar to some of our previous resource allocation problems: the only difference is that the revenue is not known for certain. We can, however, determine an expected revenue for each allocation of milk to a store. For instance, the value of allocating 2 gallons to store 1 is:
We can do this for all allocations to get the following values:
We have changed what looked to be a stochastic problem into a deterministic one! We simply use the above expected values. The resulting problem is identical to our previous resource allocation problems. We have a stage for each store. The states for stage 3 are the number of gallons given to store 3 (0, 1, 2, 3); the states for stage 2 are the number of gallons given to stores 2 and 3 (0, 1, 2, 3, 4, 5, 6) and the state for stage 1 is the number of gallons given to stores 1, 2, and 3 (6). The decision at stage i is how many gallons to give to store i. If we let the above table be represented by (the value of giving k gallons to store i, then the recursive formulae are
If you would like to work out the values, you should get a valuation of $9.75, with one solution assigning 1 gallon to store 1, 3 gallons to store 2 and 2 gallons to store 3.