next up previous contents
Next: A second example Up: A Tutorial on Dynamic Previous: Contents

First Example

Let's begin with a simple capital budgeting problem. A corporation has $5 million to allocate to its three plants for possible expansion. Each plant has submitted a number of proposals on how it intends to spend the money. Each proposal gives the cost of the expansion (c) and the total revenue expected (r). The following table gives the proposals generated:

Table 1: Investment Possibilities

Each plant will only be permitted to enact one of its proposals. The goal is to maximize the firm's revenues resulting from the allocation of the $5 million. We will assume that any of the $5 million we don't spend is lost (you can work out how a more reasonable assumption will change the problem as an exercise).

A straightforward way to solve this is to try all possibilities and choose the best. In this case, there are only tex2html_wrap_inline862 ways of allocating the money. Many of these are infeasible (for instance, proposals 3, 4, and 1 for the three plants costs $6 million). Other proposals are feasible, but very poor (like proposals 1, 1, and 2, which is feasible but returns only $4 million).

Here are some disadvantages of total enumeration:

  1. For larger problems the enumeration of all possible solutions may not be computationally feasible.
  2. Infeasible combinations cannot be detected a priori, leading to inefficiency.
  3. Information about previously investigated combinations is not used to eliminate inferior, or infeasible, combinations.

Note also that this problem cannot be formulated as a linear program, for the revenues returned are not linear functions.

One method of calculating the solution is as follows:

Let's break the problem into three stages: each stage represents the money allocated to a single plant. So stage 1 represents the money allocated to plant 1, stage 2 the money to plant 2, and stage 3 the money to plant 3. We will artificially place an ordering on the stages, saying that we will first allocate to plant 1, then plant 2, then plant 3.

Each stage is divided into states. A state encompasses the information required to go from one stage to the next. In this case the states for stages 1, 2, and 3 are

Unlike linear programming, the tex2html_wrap_inline870 do not represent decision variables: they are simply representations of a generic state in the stage.

Associated with each state is a revenue. Note that to make a decision at stage 3, it is only necessary to know how much was spent on plants 1 and 2, not how it was spent. Also notice that we will want tex2html_wrap_inline868 to be 5.

Let's try to figure out the revenues associated with each state. The only easy possibility is in stage 1, the states tex2html_wrap_inline864 . Table 2 gives the revenue associated with tex2html_wrap_inline864 .

Table 2: Stage 1 computations.

We are now ready to tackle the computations for stage 2. In this case, we want to find the best solution for both plants 1 and 2. If we want to calculate the best revenue for a given tex2html_wrap_inline866 , we simply go through all the plant 2 proposals, allocate the given amount of funds to plant 2, and use the above table to see how plant 1 will spend the remainder.

For instance, suppose we want to determine the best allocation for state tex2html_wrap_inline882 . In stage 2 we can do one of the following proposals:

  1. Proposal 1 gives revenue of 0, leaves 4 for stage 1, which returns 6. Total: 6.
  2. Proposal 2 gives revenue of 8, leaves 2 for stage 1, which returns 6. Total: 14.
  3. Proposal 3 gives revenue of 9, leaves 1 for stage 1, which returns 5. Total: 14.
  4. Proposal 4 gives revenue of 12, leaves 0 for stage 1, which returns 0. Total: 12.
The best thing to do with four units is proposal 1 for plant 2 and proposal 2 for plant 1, returning 14, or proposal 2 for plant 2 and proposal 1 for plant 1, also returning 14. In either case, the revenue for being in state tex2html_wrap_inline882 is 14. The rest of table 3 can be filled out similarly.

Table 3: Stage 2 computations.

We can now go on to stage 3. The only value we are interested in is tex2html_wrap_inline888 . Once again, we go through all the proposals for this stage, determine the amount of money remaining and use Table 3 to decide the value for the previous stages. So here we can do the following at plant 3:

Therefore, the optimal solution is to implement proposal 2 at plant 3, proposal 2 or 3 at plant 2, and proposal 3 or 2 (respectively) at plant 1. This gives a revenue of 18.

If you study this procedure, you will find that the calculations are done recursively. Stage 2 calculations are based on stage 1, stage 3 only on stage 2. Indeed, given you are at a state, all future decisions are made independent of how you got to the state. This is the principle of optimality and all of dynamic programming rests on this assumption.

We can sum up these calculations in the following formulas:

Denote by tex2html_wrap_inline890 the revenue for proposal tex2html_wrap_inline892 at stage j, and by tex2html_wrap_inline896 the corresponding cost. Let tex2html_wrap_inline898 be the revenue of state tex2html_wrap_inline900 in stage j. Then we have the following calculations




All we were doing with the above calculations was determining these functions.

The computations were carried out in a forward procedure. It was also possible to calculate things from the ``last'' stage back to the first stage. We could define

This defines a backward recursion. Graphically, this is illustrated in Figure 1.

Figure 1: Forward vs. Backward Recursion

Corresponding formulas are:

The recursion formulas are:




If you carry out the calculations, you will come up with the same answer.

You may wonder why I have introduced backward recursion, particularly since the forward recursion seems more natural. In this particular case, the ordering of the stages made no difference. In other cases, though, there may be computational advantages of choosing one over another. In general, the backward recursion has been found to be more effective in most applications. Therefore, in the future, I will be presenting only the backward recursion, except in cases where I wish to contrast the two recursions.

next up previous contents
Next: A second example Up: A Tutorial on Dynamic Previous: Contents

Michael A. Trick
Sun Jun 14 13:05:46 EDT 1998