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.

Tue Jun 16 13:34:09 EDT 1998