# Dynamic programming problem with machines

A company will be using a new technology for 5 years. For this purpose a specialized machine is required. The company currently has one, which will be 2-year old at the beginning of next year. The cost of a new machine is £6,000. The profit that can be obtained from the machine is decreasing with the age of the machine. There is no salvage value for an old machine. $$\begin{array}{cc}\hline\text{Age of Machine}&\text{Profit}\,\,(\text{in}\,\,{\it£}1,000)\\\hline0 & 10\\1 & 7\\2 & 5\\3 & 1\\\hline\end{array}$$ By the end of each year it has to be decided whether or not to replace the old machine by a new one. In any case, the age of the machine must not exceed 3. The goal is to maximize the net profit during the next 5 years. Formulate and solve the problem as a shortest path problem.

I have tried it using dynamic programming:

Define $$p_{i,j}$$ as profit from using a machine from years $$1,2,3,4,5,6$$ where $$1\le i. Then $$p_{1,2}= 1$$ since at the second year I would face a cost of buying a new machine and the machine is already going into its second year, hence the $$7$$ profit. Thus $$p_{1,3}= 7+5=12$$ and $$p_{2,3}$$ would be $$10-6=4$$, since we are buying a new machine after second year. The same logic would be for all the other arcs.

What I got as a result is that the profit maximizing path would be $$1-3-5-6$$ since $$p_{1,3}=7+5=12$$ then $$p_{3,5}=4+7=11$$ and $$p_{5,6}=4$$.

$$\begin{array}{|c|c|}\hline p_{i,j}&1&2&3&4&5&6\\\hline1&&1&6&7&-&-\\\hline2&&&4&11&12&-\\\hline3&&&&4&11&12\\\hline4&&&&&4&11\\\hline5&&&&&&4\\\hline\end{array}$$

I just calculated this result using the graph I sketched, but not using the recursive method as dynamic programming tells us to do. How do I solve this using the method, and are my results/reasoning correct?

## 1 Answer

For the following I did not check in depth the rules related to end-of-period/beginning of period, so this is something you should carefully check for your problem. However, the approach does not differ much if this is incorrect (but your numbers may end up different). Sanity checks are definitely in order before you take this answer for granted!

I think your state variable is a bit strange. Given the problem, I would be inclined to define $$p_{i,j}$$ as the cumulative profit in years periods from $$1$$ up to and including period $$i$$, assuming there is currently a machine with age $$j$$ in time period $$i$$.

We first need to define recurrent relationships on the state variables $$p_{i,j}$$. For the first period, where $$i=1$$, we can do so as follows:

$$p_{1,j} = \left\{ \begin{array}{ll} 5 & \mbox{ if } j=2 \\ -\infty & \mbox{ otherwise } \end{array}\right.$$

The idea here is that we have a profit of $$5$$ (thousand) for the state where we have a two year old machine at the end of the first year. Since it is not possible to have any other machine at the end of the first year, the states related to that situation have $$-\infty$$ profit, as this value will be discarded by the consecutive steps of the recurrence relation.

For the later periods, where $$i \geq 2$$, we can compute the best possible profit based on the previous period by means of the following recurrence relation

$$p_{i,j} = \left\{ \begin{array}{ll} \max_{k \in \{0,\dots,3\}} p_{i-1,k} + 10 - 6 & \mbox{ if } j=0 \\ p_{i-1,j-1} + 7 & \mbox{ if } j=1 \\ p_{i-1,j-1} + 5 & \mbox{ if } j=2 \\ p_{i-1,j-1} + 1 & \mbox{ if } j=3 \\ \end{array} \right.$$

Here the idea is that if in a later period the age of the machine is $$0$$, it means we must have bought a new machine in the previous period. Since multiple machine states were possible in the previous period, we should do so in the state that yields maximum profit. This is where we apply the Bellman optimality principle. In case we have a machine with a greater age, we know for certain that we had a machine with one age smaller in the previous period and therefore, there is nothing to optimize.

Now you can construct a table for these recurrence relations. The following python code does this in a bit of a quick-and-dirty way, and hasn't been carefully checked.

# Problem constants
profits = {0: 10, 1: 7, 2: 5, 3: 1}
cost = 6

def dp(i,j,table={}):
if (i,j) in table:
return table[(i,j)]
# Deal with the base case
if i==1:
if j==2:
table[(i,j)] = 5
else:
table[(i,j)] = float('-inf')
# Deal with the recurrent case
elif j==0:
# If we have a new machine, determine in which state it could best be bought
best = dp(i-1,0,table)
for k in range(1,4):
val = dp(i-1,k,table)
if val > best:
best = val
table[(i,j)] = best + profits - cost
# If we don't have new machine, just add the profit
elif j in profits:
table[(i,j)] = dp(i-1,j-1,table) + profits[j]
# We should now have a value for the state
if (i,j) in table:
return table[(i,j)]
raise ValueError

table = {}
for k in range(0,4):
ans = dp(5,k, table)
print(k, ans)


This prints the following numbers: $$\begin{array}{ll} 0 & 25 \\ 1 & 27 \\ 2 & 25 \\ 3 & 22 \end{array}$$

which are based on the following numbers stored in the table dictionary:

$$\begin{array}{l|rrrrr} & 1 & 2 & 3 & 4 & 5 \\ \hline 0 & -\infty & 9 & 13 & 20 & 25 \\ 1 & -\infty & -\infty & 16 & 20 & 27 \\ 2 & 5 & -\infty & -\infty & 21 & 25 \\ 3 & -\infty & 6 & -\infty & -\infty & 22 \\ \end{array}$$

Which suggests that the maximum profit is obtained if you end with a 1 period old machine, and make a profit of 27000. If you want to obtain the exact policy, you would need to keep track of the predecessor states, possibly via an additional table.