Table 1 provides the net annual returns from the investment
opportunities expressed in millions of dollars. 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.
The investment problem has a general mathematical programming
formulation.
The notation is the general model is defined
below.
The problem as stated is similar in structure
to the knapsack problem but the objective function is
nonlinear. To formulate it as a mixed-integer linear
program it would be necessary to introduce 32 binary
variables, one for each nonzero level of investment.
Since the budget and investment amounts are integer
the slack variable, *y*, can be treated as integer. Rather than pursuing the MILP
formulation we will use the problem as an introduction
to dynamic programming. |