Financial Linear Programming Problem I'm very new at linear programming and I'm trying to figure out a way to approach this problem below:
You are a CFA (chartered financial analyst). Madonna
has come to you because she needs help paying off her credit
card bills. She owes the amounts on her credit cards shown
in the table below. Madonna is willing to allocate up to $5,000 per
month to pay off these credit cards. All cards must be paid
off within 36 months. Madonna’s goal is to minimize the
total of all her payments. To solve this problem, you must
understand how interest on a loan works. To illustrate,
suppose Madonna pays $5,000 on Saks during month 1.
Then her Saks balance at the beginning of month 2 is

    20,000 - (5,000 - 0.005(20,000))

This follows because during month 1 Madonna incurs
.005(20,000) in interest charges on her Saks card. Help
Madonna solve her problems!


Since this is a multi-period problem, I'm having a bit of difficulty finding a way to model it. I would guess that the decision variables are as follows:
$S_i = $ Amount spent at Saks Fifth Avenue during month $i$
$B_i = $ Amount spent at Bloomingdale's during month $i$
$M_i = $ Amount spent at Macy's during month $i$
$i = 1,2,3,...,36$
However, I am not sure where to go from here (or even if my choice of decision variables will work as chosen.) I would appreciate some advice. Thanks!
 A: I think the variables you have chosen so far are sound.
We can also temporarily introduce


*

*$BS_i=$ amount remaining at Saks Fifth Avenue month $i$

*$BB_i=$ amount remaining at Bloomingdale's month $i$

*$BM_i=$ amount remaining at Macy's month $i$


Now
$$BS_i=BS_{i-1}-(S_i-0.005BS_{i-1})=1.005BS_{i-1}-S_i,$$
so
$$
BS_{36}=1.005BS_{35}-S_{36}=1.005^2BS_{34}-1.005S_{35}-S_{36}=\ldots=
BS_0-\sum_{i=0}^{35}1.005^iS_{36-i},
$$
and similarly for Bloomingdale's and Macy's.
The problem can now be stated as:
$$
\begin{aligned}
\text{minimise} & \sum_{i=1}^{36}(S_i+B_i+M_i) & \\
\text{subject to} & S_i+B_i+M_i\leq 5000 \quad i=1,\ldots,36& \text{(monthly budget constraint)} \\
& S_i, B_i, M_i \geq 0 \quad i=1,\ldots,36 & \text{(she cannot borrow)} \\
& \sum_{i=0}^{35}1.005^iS_{36-i}=20000 & \text{(fully pay Saks Fifth Avenue)} \\
& \sum_{i=0}^{35}1.01^iB_{36-i}=50000 & \text{(fully pay Bloomingdale's)} \\
& \sum_{i=0}^{35}1.015^iM_{36-i}=40000 & \text{(fully pay Macy's)} \\
\end{aligned}
$$
