[Math] Building the model for a Linear Programming Problem

linear programmingoptimization

Problem

A young investor is planning to invest in the stocks of the Metalco company during the week. He has some predicted values for the buying and selling prices of the shares during the week. The prices are shown in the table.

Trading Strategy
The investor starts the week with $100 and he wants to formulate the buying-selling strategy through a linear program to maximize the total amount he would have at the end of the week. The following trading opportunities and restriction apply:

  1. He starts the week with no shares owned in Metalco.

  2. On any given day, he can only sell shares that he owns from previous trading days.

  3. No borrowing is allowed. This means that on any given day, the trader could only buy shares using money he had at the beginning of the week $\pm$ any profit/loss he incurred from the previous days of trading.

For simplicity, the amount of shares that can be bought can take non-integer values. Formulate a linear program that maximizes the amonut of money the trader has at the end of the week.

What I Have Done

  1. Initially I naively thought the Monday shares should be sold on Wednesday, and Tuesday shares should also be sold on Wednesday … and I could let this be the objective function to maximize. However, this is wrong since there might be no money left at all for Tuesday shares to buy in (actually there would be revenues available on Wednesday and Friday in this initial reasoning).

  2. Realizing the mistake in 1, I also found that the operation on one day would affect the operations on the following. Since it is impossible to enumerate all cases (since the problem allows non-integer stocks), I feel that there is nothing I could do.

  3. I heard that there might be dynamic programming that could help. However, I just have a week's linear programming course and only some basic concepts are introduced by the lecturer.

Could anyone help me, thank you in advance.

Best Answer

For each day $i$, where $1 \le i \le 5$, let

  • $B_i$ denote the specified buying price.$\\[4pt]$
  • $S_i$ denote the specified selling price.$\\[4pt]$
  • $b_i$ represent the number of shares to be purchased.$\\[4pt]$
  • $s_i$ represent the number of shares to be sold.$\\[4pt]$
  • $x_i$ represent the number of shares owned after all transactions are completed.
  • $v_i$ cash-on-hand after all transactions are completed.

Thus, for each day $i$, we have $4$ variables, $b_i,s_i,x_i,v_i$.

For convenience, define constants $x_0 = 0,\;v_0=100$.

For each day $i$, we have the constraints

  • $b_iB_i \le v_{i-1}$$\\[4pt]$
  • $s_i \le x_{i-1}$$\\[4pt]$
  • $x_i=x_{i-1}+b_i-s_i$$\\[4pt]$
  • $v_i=v_{i-1}-b_iB_i+s_iS_i$$\\[4pt]$
  • $b_i,s_i,x_i,v_i \ge 0$

The goal is to maximize $v_5$, subject to the above constraints.

If you solve the linear program, the optimal final value, in dollars, is $$v_5 = \frac{48000}{253} \approx 189.72$$

Related Question