next up previous
Next: Uncertain States Up: A Tutorial on Stochastic Previous: A Tutorial on Stochastic

Uncertain Payoffs

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:

table15

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:

displaymath47

We can do this for all allocations to get the following values:

table20

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 tex2html_wrap_inline53 (the value of giving k gallons to store i, then the recursive formulae are

displaymath59

displaymath61

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.


next up previous
Next: Uncertain States Up: A Tutorial on Stochastic Previous: A Tutorial on Stochastic

Michael A. Trick
Tue Jun 16 13:34:09 EDT 1998