4
$\begingroup$

Stuck in this problem for quite a while. Anyone can offer some help? The problem is as follows:

Fred has $5000 to invest over the next five years. At the beginning of each year he can invest money in one- or two-year time deposits. The bank pays 4% interest on one-year time deposits and 9 percent (total) on two-year time deposits. In addition, West World Limited will offer three-year certificates starting at the beginning of the second year.These certificates will return 15% (total). If Fred reinvest his money that is available every year, formulate a linear program to show him how to maximize his total cash on hand at the end of the fifth year.

  • 0
    I see the difficulty because although it seems like a continuous process this is a discrete time problem. So time is not an issue. it is only a matter of 5 steps that the revenue is maximized in.2011-09-07

3 Answers 3

2

Notice that Fred can always invest in 1-year deposits and get this money at the beginning of the next year for further investments. This means that all available money will always be invested and we do not bother about the rest.

Year 1: invest $ x_1 $ in 1-year deposit $ 4\% $, $ x_2 $ in 2-year $ 9\% $

  • $ x_1 + x_2 \leq 5000 $ (= available money)

Year 2: invest $ x_3 $ in 1-year $ 4\% $, $ x_4 $ in 2-year $ 9\% $, $ x_5 $ in 3-year $ 15\% $

  • $ x_3 + x_4 + x_5 \leq 1.04 \times x_1 $ (= available money)

Year 3: invest $ x_6 $ in 1-year $ 4\% $, $ x_7 $ in 2-year $ 9\% $, $ x_8 $ in 3-year $ 15\% $

  • $ x_6 + x_7 + x_8 \leq 1.04 \times x_3 + 1.09 \times x_2 $ (= available money)

Year 4: invest $ x_9 $ in 1-year $ 4\% $, $ x_{10} $ in 2-year $ 9\% $

  • $ x_9 + x_{10} \leq 1.04 \times x_6 + 1.09 \times x_4 $ (= available money)

Year 5: invest $ x_{11} $ in 1-year $ 4\% $

  • $ x_{11} \leq 1.04 \times x_9 + 1.09 \times x_7 + 1.15 \times x_5 $ (= available money)

Year 6:

  • available money = $ 1.04 \times x_{11} + 1.09 \times x_{10} + 1.15 \times x_8 $ = final cash = maximize !

So, if I did not make a mistake, there are 11 unknowns x1, ..., x11 for the individual investments, 5 linear inequalities (1) - (5), and one linear goal function (6) to be maximized. This linear programming problem can be solved by the simplex algorithm.

ADDED (based on Mike's comment): for completeness the 11 inequalities xi >= 0 for the unknowns should be added.

  • 0
    This formulation makes the implicit assumption that all money available at the beginning of each year should be immediately reinvested. This assumption is justified in this case because there is a one-year investment option, but it does not hold in general.2017-10-21
0

I came up with a bit different model that I think it's more compact. I know it's been some years since this question was made, but please, someone let me know if it's not correct:

Being $ x_{ij} $ the amount invested in option i at year j, we look to
maximize $ z $ = 1,04$x_{15}$ + 1,09$x_{24}$ + 1,15$x_{33}$,
subject to:

  • $ x_{11} $ + $x_{12}$ <= 5000
  • $ x_{31} $ = $x_{34}$ = $x_{35}$ = 0
  • $ x_{12} $ + $x_{22}$ + $x_{32}$ <= 1,04 $x_{11}$
  • $ x_{13} $ + $x_{23}$ + $x_{33}$ <= 1,04 $x_{12}$ + 1,09 $x_{21}$
  • $ x_{14} $ + $x_{24}$ <= 1,04 $x_{13}$ + 1,09 $x_{22}$
  • $ x_{15} $ <= 1,04 $x_{14}$ + 1,09 $x_{23}$ + 1,15 $x_{32}$
  • $ x_{ij} $ >= 0

Does it make sense?

0

This is how i coded it in CPLEX. If it may help.

/*********************************************      * OPL 12.6.1.0 Model      * Author: shokirovn      *********************************************/   // decision variables   // x(ij) = amount of money invested in period i for j years i = 1,...,5 and j = 1,2,3.  // for j = 1 year  dvar float+ x11;  dvar float+ x21;  dvar float+ x31;  dvar float+ x41;  dvar float+ x51;   // for j = 2 years  dvar float+ x12;  dvar float+ x22;  dvar float+ x32;  dvar float+ x42;   // for special certificate j = 3  dvar float+ x23;  dvar float+ x33;   // expressions   dexpr float profit = 1.15*x33 + 1.09*x42 + 1.04*x51;    // model   maximize profit;  subject to {          // investment should not exceed available money in year i.         x11 + x12 <= 5000;          x21 + x22 + x23 <= 1.04*x11;         x31 + x32 + x33 <= 1.09*x12 + 1.04*x21;         x41 + x42 <= 1.09*x22 + 1.4*x31;         x51 <= 1.15*x33 + 1.09*x32 + 1.04*x41;   } **OUTPUT:** // Condition number of unscaled basis = 1.1e+001 //   x33 = 5450; x42 = 0; x51 = 6267.5; x11 = 0; x12 = 5000; x21 = 0; x22 = 0; x23 = 0; x31 = 0; x32 = 0; x41 = 0;