Suppose I start month 1 with $\$ 400$ and beginning of months 1,2,3 and 4 I receive as revenue $\$ 400,800,300,300$ respectively and pay bills $600,500,500,$ and $250$ month 1,2,3 and 4 respectively. Any money left over for one month can be invested at interest rate $0.1 \%$ per month, for two months $0.5 \%$ per month, for three months $1 \%$ per three months or for four months at $2 \%$ per month. My goal is to formulate a linear programming that can be used to maximize my total cash at hand at beginning of month 5.


If I call $x_i$ the amount of money at month $i$, i=1,2,3,4, then I want to maximize the function

$$ f(x_1,...,x_4) = -200x_1 + 300 x_2 - 200 x_3 + 50 x_4$$

my constraints:

at month 1, I have left over $800-200 = 200$ thus $0.1x_1 \geq 200$ month 2, $0.5x_2 \geq 500 $ month 3, $1 x_3 \geq 300 $ and month 4 , $2x_4 \geq 450 $.

also $x_i \geq 0$

Is this a correct formulation?

  • 1
    $\begingroup$ You have a mistake in the first constraint: $800-200 = 200$ ?! Please correct it and then explain how do you got it. $\endgroup$ – callculus Aug 31 '17 at 18:51
  • $\begingroup$ You have not addressed the point raised by callculus; also, why do you multiply the amount 200 with the amount $x_i$? $\endgroup$ – anderstood Sep 2 '17 at 16:56

Here is a geometrical approach (and not a linear programming one) which I hope will help you understand the problem.

The differences between the revenues and the bills are $(-200,300,-200,-50)$ and you start with $400$. You can plot this as a function of time (thick black curve):

enter image description here

Now the question boils down to placing rectangles as long (in the horizontal direction) as possible, starting from the bottom, as depicted. This ensures that the maximum amount is invested for a maximal duration, while ensuring that you always have the available funds to pay the bills.

Reading from the graph: invest 200 for four months at month 1, 50 for three months, 50 for two months and 200 for one month at month 2.

Note: this technique works because the interest rates are an increasing function of time. If the interest rate for 3 months was $10\%$, of course that would no longer hold.


In terms of linear programming I think you would have to say that you have these fixed rates $r_{1,2,3,4}$ to invest over 1,2,3, or 4 months, and you invest an amount $I^k_{t}$ for a time $k$ at time-step number $t$; meanwhile your revenues minus costs is some "profit" amount $p_{1,2,3,4}.$

The literal amount you have at time $t$ is therefore $$A_t = A_{t-1} + p_t - \sum_k I^k_t + \sum_k (1 + r_k)~I^k_{t-k}.$$ This is saying "the amount that I have at time $t$ is equal to the amount I had at time $t-1$ plus the raw profit from this timestep, minus the amounts I'm investing right now, plus the returns I got from my prior investments.

In this sort of problem one is maximizing $A_T$ for some final $T$ and one's constraints are that $A_t \ge 0$ for all $t < T.$ Since one has worthwhile investments which cover as small a time as one timestamp, one can make the early optimization to strengthen those constraints to $A_t = 0$ for all $t < T$, as it doesn't ever make any sense to just "leave the money in your account." (There is a similar optimization tacit in @anderstood's answer which is that given the way that the $r_k$ increase, one should ignore any $r_k$ if one could obtain more money by investing for the same time at a lower $r_k$. I am not sure that one can program this in a nice linear programming way but it does give immediate answers.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.