Financial Linear Programming Problem

Question

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!

Answer 1

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} $$

Answer 2

Linear programming is not needed for this problem. A higher interest rate card should be fully paid first before paying anything on the lower interest rate card in order to minimize the cumulative interest payments. The reason is that the minimum payment required to pay off card balances is higher when there is an extra dollar of balance on a card with higher interest rate will than when there is an extra dollar of balance on a card with lower interest rate.

We can use the concept of future value. The balance of a card just before the payment at the end of month is $b_n=b_0(1+r)^n-\sum_{i=1}^{n-1}{p_i(1+r)^{n-I}}$ where $b_0$ is the initial balance on the card, $p_i$ is the payment at the end of month $i$ and $r$ is the monthly interest rate associated with the card.

First fully pay Macy's with highest interest rate of 1.5%. The initial balance of \$40,000 plus interest charges may be fully paid off in the 9th month when \$5000 is paid a month. Using Macy's interest rate, initial \$40,000 is equivalent to $\$40,000\times 1.015^9$ at the end of 9th month whereas 8 payments of \$5000 are worth $\$5000(1.015^8+1.015^7+...+1.015)$ so the amount required to payoff Macy's card in 9th month = $40,000 \times 1.015^9-5,000\times 1.015 \times (1.015^8-1)/(1.015-1)=\$2,938.94$.

The next costliest card is Bloomingdale's so pay \$2,061.06 towards that card in 9th month and then pay \$5000 in each of the subsequent months. Initial balance is \$50,000, so at least 10 full payments of \$5000 each are needed. Check if the card can be paid off in the 20th month. The initial balance and previous payments grow to $\$50,000 \times 1.01^{20}$ and $\$2061.06 \times 1.01^{11}+\$5000 \times (1.01^{10}+1.01^9+...+1.01)$, respectively so required payment in 20th month is $50,000 \times 1.01^{20}-2061.06 \times 1.01^{11}-5,000 \times 1.01 \times (1.01^{10}-1)/(1.01-1)=\$5,875.87$, exceeding \$5000. So it will have to be paid off in 21st month with payment of $50,000\times 1.01^{21}-2061.06\times 1.01^{12}-5,000\times 1.01\times (1.01^{11}-1)/(1.01-1)=\$884.63$.

Pay the remaining \$4,115.37 and future monthly payments for Saks Fifth Avenue (SFA) card. Since initial balance is \$20,000, at least 3 full payments of \$5000 are needed. Check if card can be paid off fully in the 25th month. Payment required in 25th month = $20,000\times 1.005^{25}-4115.37\times 1.005^{4}-5,000\times 1.005\times (1.005^{3}-1)/(1.005-1)=\$3,307.11$.

Total amount paid = $24 \times 5,000 + 3,307.11 = \$123,307.11$.