IN THE CLASSROOMRICK HESSE, Feature Editor, Mercer University
Dynamic investments using lookup tablesby Rick Hesse, Mercer University Certainly one of the least taught of the management science techniques is dynamic programming. One reason is that it is a difficult algorithm to program for general problems. However, for certain structured problems, spreadsheets and the ability to use lookup tables, make this an easy setup. Rather than solve one n-dimensional nonlinear problem, dynamic programming solves n one-dimensional nonlinear problems. A standard problem that is used to illustrate the power of dynamic programming is a tabular nonlinear investment problem. Figure 1 shows the data for the problem. The problem is to maximize the return on $5,000 invested in any or all of three investments, where you are limited to investing in the quantities from $0 to $5,000 in steps of $1,000. You cannot invest twice in the same investment. The return on the investments is nonlinear, which is shown by the fact that the increase in return per $1,000 is not uniform. Mathematical Formulation The mathematical formulation as a single nonlinear problem is: Maximize Return = F1(X1) + F2(X2) + F3(X3)
Subject to: X1 + X2 + X3 $5,000
In classic DP fashion, we solve the problem ``backwards.'' First we solve the problem as if we had only Investment #3, F3, to go, and given the amount of money we have left, we would simply look up the return for Investment #3 to finish the problem. This is referred to as Stage 3. With two investments to consider, for each possible amount left over, all the possible combinations of investing in F2 are considered, and then with what amount is left over, we know how to optimally invest it. This is Stage 2. Backing up to Investment #1, we can then look at each investment level for #1 and then know optimally what to do with the rest of the money for the other investment, which is Stage 1. Thus for each box shown in Figure 2, we are solving a nonlinear problem with only one variable. Spreadsheet Model Shown in Figure 3 is the table for Stage 2 in cells A13..G18 and the optimal return and amount to invest is summarized in columns H and I. The table in rows 11-18 shows what the result would be investing anywhere from $0 to $5,000. For instance, if there is $1,000 left, Cell B14 gives the result of putting nothing in Investment 2, which leaves $1,000 for Investment 3. This gives a return of $0 + $1,250 = $1,250. Cell C14 gives the result of putting $1,000 in Investment which leaves $0 for Investment 3. The resulting return $2,200 + $0 = $1,000. The values to the right for investing $2,000 or more gives $0, indicating that it is infeasible to invest more than available. This is accomplished by using an IF function to determine if the investment is feasible and is shown below in Excel format. B13: =IF($A13>>=B$12,VLOOKUP(B$12,RETURN1,3) +VLOOKUP($A13-B$12,RETURN1,4),0) and copied from B13..G18 The formula found in B13..G18 uses what spreadsheets call a lookup table. The first table is named RETURN1 and contains the values for all the investments. The VLOOKUP function (V stands for vertical) contains three arguments: VLOOKUP (Arg1, Arg2, Arg3) with a fourth default value not needed here. This function checks the left column of the table named in Arg2 and finds the first number bigger than Arg1, then backs up a row, and returns the value in that row and column Arg3. (If you are using Quattro Pro or Lotus, the last argument must decreased by 1.) It is important that the first column contains numbers in ascending order. The IF function in B13..G18 checks first for enough money to invest and if there is not enough, sets the result in the new table to $0. If there is enough money, then the VLOOKUP function is used to determine the investment return from Investment #2 in the third column RETURN1. The second part of the return is derived from the remaining money ($A13-B$12) to be put into Investment #3 and is found in the same table but in column 4. A new table is calculated from this information, with the summary in H13..H18 and the amount to invest in I13..I18. The latter uses both the MATCH and INDEX functions to determine what amount to invest.
H13: =MAX(B13:G13) and copied to H13..H18
Finally, with $5,000 to invest, we can consider the combinations of investing in Investment 1 and with the remaining amount we know how to optimally invest the rest, as shown in Figure 4. Row 22 makes the calculations of how much money is made by first investing in Investment #1 using the table RETURN1 and then using RETURN2 (A13..H18) as another lookup table to determine the optimal use of the remaining money.
B22:=IF($A22>>=C$12,VLOOKUP(C$12,RETURN1,2)
The optimal solution is determined from row 22. We know that the optimal return is $6,600 from cell H22. Looking in B22..G22, we see that the $6,600 occurs when $2,000 is put into Investment 1. This leaves $3,000 to put into the last two investments, and takes us back to the table in A13..H18. With $3,000 to invest at this point, the optimal use of the money yields $3,800, found in H16. This is achieved by not investing in Investment #2 (B16) which leaves $3,000 for Investment #3. Figure 5 summarizes the result. Conclusion This small problem illustrates both the power of dynamic programming and the use of lookup tables and match and index functions. If the table is oriented by columns instead of rows, use the HLOOKUP (H is for Horizontal) function. It is also a simple matter to add extra investments or change the amount available to invest. DP uses the summary table from the stage before and solves one investment problem at a time, because we know the optimal allocation of investments with the rest of the money. This template can give students a brief exposure to the power of dynamic programming.
mentioned in this article, contact the Managing Editor at hjacobs@gsu.edu
Dr. Rick Hesse
|