Example Problem

To illustrate using a built-in model we use the Investment Problem considering in the Models section of the site.

A portfolio manager with a fixed budget of $100 million is considering the eight investment opportunities shown in the table below. The manager must choose an investment level for each alternative ranging from $0 to $40 million. Although an acceptable investment may assume any value within the range, we discretize the permissible allocations to intervals of $10 million to facilitate the modeling. This restriction is important to what follows. For convenience we define a unit of investment to be $10 million. In these terms, the budget is 10 and the amounts to invest are the integers in the range from 0 to 4.

Table 1 provides the net annual returns from the investment opportunities expressed in millions of dollars. For example, an investment of $10 million in opportunity 1 provides an annual return of 4.1 million. When time value of money is considered this 4.1 would be considered the uniform annual equivalent of the opportunity.

A ninth opportunity, not shown in the table, is available for funds left over from the first eight investments. The return is 5% per year for the amount invested, or equivalently, $0.5 million for each $10 million invested. The manager's goal is to maximize the total annual return without exceeding the budget.

Problem Definition

Selecting the Model option from the Teach_DP menu presents the problem definition dialog. Fields accept the problem name and relevant parameters. Clicking a button on the left selects one of the problem types built into the program. We recognize the investment problem as a knapsack problem with the opportunities equivalent to items. The resource is the budget limitation. We click the Nonlinear box because the investment returns are not linear with the amount invested. The names of the fields at the right side of the dialog a affected by the problem type selected. The first checkbox label (here labeled Nonlinear) also depends on the type. When checked, the Make Random Problem box fills in the data form with random numbers appropriate to the problem type. Of course, these may be changed on the worksheet. The Show Comments adds a small red label to some of the cells of the worksheet.

After entering data and pressing the OK button, a worksheet is created with the name specified in the dialog. Many ranges on the worksheet are given Excel names with the preface being the worksheet name, so that name should not be changed after the worksheet has been constructed.

In the greater part of the worksheet the program constructs the dynamic programming model consisting of the state and decision definitions and all of the other components required for dynamic program. The problem specific data is placed to the right. We have entered the data for the example in the tables provided.

At the top of the worksheet we see a variety of information describing the problem, solution process, interaction and display. The Solve button initiates the dynamic programming solution process.

Without any knowledge of the DP model, the user can click the Solve button to obtain the solution below. Statistics of the solution process start in column M.

Excel Model

A DP model uses states and decisions to describe a sequential decision process. A number of functional expressions define the beginning, middle and end of the process. A quantitative measure determines the costs and/or benefits of the process.

When using this DP add-in for Excel, the expressions describing the model must be placed into cells as Excel equations. All DP model information is placed in first few columns of the worksheet (the number of columns depends on the number of state variables and decision variables). Regions outside the model definition can be used to hold problem specific data or equations.

We show below the Excel worksheet for the investment example. This is an instance of the knapsack problem with one decision variable and two state variables. Areas colored green hold formulas when the worksheet is constructed, but the contents may be changed by the user. This is useful when building models. During the solution process the computer manipulates the green areas during the various steps of the process. For the built-in models, the user need not be concerned with the green areas.

Areas colored yellow hold equations or data required by the program during the solution process and should not be changed by the user. Ranges outlined in red hold Excel equations that describe the dynamic programming model. These equations can be entered by the user, but in the case below they are filled entirely by the computer specifically to solve the knapsack problem. In the table below, we provide a brief description of each of the model areas. In the General section, the formulas are described in greater detail.