# Linear programming problem formulation

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. - I can solve it with brute-force by considering every invest possibility at the beginning of each year. But how to solve it as linear programming? I have trouble in modeling the problem. – zf xiao Sep 7 '11 at 12:18 Is there any cost to 3-year certificate ? – user13838 Sep 7 '11 at 13:23 I don't think there is. The only condition is the three-year certificate starts at the beginning of the 2nd year. – zf xiao Sep 7 '11 at 13:41 yes but you see the pattern,no?. Is it a compound interest or is the money fixed ? Does it only depend on the money Fred has initially at the beginning of the 2nd year? Then we go for a one year and obtain %4 anyhow, to get the max out of the 3-year thing. – user13838 Sep 7 '11 at 14:12 My understanding is it's a compound interest. For example, if Fred goes for a one year at the beginning of the first year. then he has 5000(1+4%) available for investment at the beginning of the 2nd year. The problem is he has multiple options in each year. And the available money depends on his previous investments... so I was trapped. – zf xiao Sep 7 '11 at 14:28 ## 3 Answers Notice that Fred can always invest in 1-year deposits and get this money at the beginnig of the next year for further investments. This means that always all available money will be invested and we do not bother about some rests. (1) Start of 1st year: invest x1 in 1-year deposit 4%, x2 in 2-year 9% x1 + x2 <= 5000 (= available money)  (2) Start of 2nd year: invest x3 in 1-year 4%, x4 in 2-year 9%, x5 in 3-year 15% x3 + x4 + x5 <= 1.04*x1 (= available money)  (3) Start of 3rd year: invest x6 in 1-year 4%, x7 in 2-year 9%, x8 in 3-year 15% x6 + x7 + x8 <= 1.04*x3 + 1.09*x2 (= available money)  (4) Start of 4th year: invest x9 in 1-year 4%, x10 in 2-year 9% x9 + x10 <= 1.04*x6 + 1.09*x4 (= available money)  (5) Start of 5th year: invest x11 in 1-year 4% x11 <= 1.04*x9 + 1.09*x7 + 1.15*x5 (= available money)  (6) Start of 6th year: available money = 1.04*x11 + 1.09*x10 + 1.15*x8 = final cash = maximize !  So, if I did not make any 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. - Looks good to me, although you might want to throw in the nonnegativity constraints for completeness. – Mike Spivey Sep 7 '11 at 16:15 @Mike: added. Thanks! – Jiri Sep 7 '11 at 16:23 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?

-

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;

-