Linear Programming to find the loan plan to minimize the interest payment

Question

Assume that it is the first of July and you are running a small shop. The sales revenue and the amount of bills you have to pay for the next six months are estimated as following:

In short, you will make $4000 profit at the end of the year. However since all bills must be paid in full every month, you may be short on cash in earlier months until you see the big sales in November and December. You have two sources of loan:

• Long term loan of six months at 10% of interest, e.g. you borrow $100$ now , and payback $110$ at the end of the year. Early payback is not allowed. You have to keep the money for six months at 10% of interest.

• Monthly loan at 4% of interest, e.g. you borrow $100$ at the beginning of any month and pay back $104$ at the end of the month. No monthly loan is available in December.

Assume you have zero cash at the moment.

Apply the linear programming to find the loan plan to minimize the interest payment.

For this question, I have selected 12 decision variables. $X_1-X_6$: Sales Revenue $X_7- X_{12}$: Bills

$X_7+ X_8+ X_9+ X_{10}+X_{11}+X_{12} \leq 20,000$ and $X_1+X_2+ X_3+X_4+X_5+X_6\leq 24,000$

I do not know if above constraints is actually correct, and I don't know how to continue from there! Please help and maybe instead of providing the answers, if any links or example of similar question, it will also help!

Edit: Thanks for the explaination, however I still can't seem to find the answer. During my lecture, the lecturer have told us that there are 12 decision variables.

Which from the answer you provided, it will be $L, S_1...S_5 and C_1 ... C_6$. My understanding on decision variables is that, it will have to be all included in the objective function.

Therefore my objective was Min: $1.1L + 1.04S - (C_1....C_6)$

Please kindly advise how to interpret the results for the loan plan base on the software.

Answer 1

When solving problems of this sort it helps to systematically follow something like the following procedure.

1) Write down the variables that you want to solve for.

In this case, you want to find the amount of each loan that you want to take out. Let us let $L$ be the number of long term loans that you want, and $S_1$ to $S_5$ be the amount of each short term loan, $S_1$ the loan amount for July, to $S_5$ the loan amount for November. Each of these loan amounts must be greater than or equal to 0.

2) Write down the constraints (adding internal variables if necessary).

Here there is only one type of constraint -- at the beginning of each month, after cash on hand along with last months income and loans have been applied to last months bills and expiring loans.

We see that cash on hand at the beginning of each month is a probably best described as a variable (otherwise we would need to repeat computations in the constraints). So to simplify the constraints, let us add variables $C_1$ to $C_6$ denoting cash on hand at the beginning of August to January. These variables are constrained to be greater than or equal to 0. This makes the 6 constraints:

$$L + S_1 + 3000 - 6000 = C_1$$ $$C_1 + S_2 + 2000 - 6000 - 1.04 S_1 = C_2$$ $$C_2 + S_3 + 1000 - 4000 - 1.04 S_2 = C_3$$ $$C_3 + S_4 + 2000 - 2000 - 1.04 S_3 = C_4$$ $$C_4 + S_5 + 6000 - 1000 - 1.04 S_4 = C_5$$ $$C_5 + 10000 - 1000 - 1.04 S_5 - 1.1 L = C_6$$

3) Write down the objective.

Here this is just the amount of money left over at the beginning of January, and we want as much of it as possible, so the Objective is to maximize $C_6$.

4) Solve.

In answer to your extended question: I am not familiar with the software you are using, so I cannot explain its results. It does seem that the answers that you are getting are absurd. For a problem like this that you can solve without resorting to a linear program (once you have chosen the amount of the long term loan, everything else is determined), solve it. Then compare your solution with the output of the software.

Answer 2

This is my solution to the question; i have used the 6 constraits above.

Answer 3

Addendum to @deinst 's answer:

Here is the table of the OP

month       Rev Bills 
July       3000  6000 
August     2000  6000 
September  1000  4000 
October    2000  2000 
November   6000  1000 
December  10000  1000 

The values

month       Rev Bills
September  1000  4000 

mean that on end of September we get 1000 revenues for sales and after that we have to pay 4000 for bills. Thats not clear for me when I read the OP but we will assume this and it is assumed in deinst's answer , too.

The problem can be formulated for the online LP solver http://vinci.inesc.pt/lp/ as

max:-0.1 L-0.04  S1-0.04  S2-0.04  S3-0.04  S4-0.04  S5;
c1:L+ S1-3000>=0;
c2:L-0.04  S1+ S2-7000>=0;
c3:L-0.04  S1-0.04  S2+ S3-10000>=0;
c4:L-0.04  S1-0.04  S2-0.04  S3+ S4-10000>=0;
c5:L-0.04  S1-0.04  S2-0.04  S3-0.04  S4+ S5-5000>=0;

and one gets the solution

Value of objective function: -944.8000048518181
L = 7000.0
S1 = 0.0
S2 = 0.0
S3 = 3000.0
S4 = 3119.999997317791
S5 = 0.0
Using Simplex

So one has to borrow 7000 in july for an half year (long term loan) , on September one borrows 3000 for one month and on October one borrows 3120 for one month. The proft at the end of the year is 4000-944.8 = 3055.2.

We can get the result by reasoning withou using an LP program.

Let's extend the table

month       Rev Bills  Saldo
                            0
July       3000  6000   -3000
August     2000  6000   -7000
September  1000  4000  -10000
October    2000  2000  -10000
November   6000  1000   -5000
December  10000  1000    4000

The Saldo column says that at end of september we have earned 10000 less than we have to pay: we have 6000 got from sales revenues but the bills we have to pay sum up to 16000.

If we take a long term loan of 10000 we will survive without taking any short term loan because the maxmimal saldo is -10000. Then we have to pay back 11000 at the end of september and the profit will be 4000-(11000-10000)=3000.

It does not make sense to borrow the 3000 needed for July borrow as a short term loan. Our saldo is negative until december so we have to borrow the 3000 forJuly (and for its interest and compound interest) also on August until November. This means at least 5*4% interest (ignoring compund interset) which is 20% and therefore more than th 10% we have to pay for a long term loan.

So we borrow 300 and get the following table

month       Rev Bills  Saldo
credit                   3000
July       3000  6000       0
August     2000  6000   -4000
September  1000  4000   -7000
October    2000  2000   -7000
November   6000  1000   -2000
December  10000  1000    7000

Again we see that it makes sense to borrow the differende of 4000 needed in july also as long term loan. We get

month       Rev Bills  Saldo
credit                   7000
July       3000  6000    4000
August     2000  6000       0
September  1000  4000   -3000
October    2000  2000   -3000
November   6000  1000    2000
December  10000  1000   11000

For September it makes sense to borrow the 3000 on a monthly basis. We have to borrow it again on October so we have to pay 2*4% = 8% interest. but this is less than the 10% that we have to pay if we borrow it for a halfe year in July. In October we have also to borrow a small amount to pay the 4% interest of the September loan but this has no influence on our decision.