Equipment replacement problem

Question

I have a question on the Equipment Replacement Problem, where the following is taken (with some syntactic modifications) from IB2070 Mathematical Programming II (MP2), Warwick Business School.

Equipment Replacement Problem \begin{array}{cc}\hline\text{Age of Car}&\text{Annual Maintenance}&\text{Trade-in Price at the}\\&\text{Cost}&\text{end of the period}\\\hline0&{\it\unicode{xA3}}2,000&{\it\unicode{xA3}}7,000\\1&{\it\unicode{xA3}}4,000&{\it\unicode{xA3}}6,000\\2&{\it\unicode{xA3}}5,000&{\it\unicode{xA3}}2,000\\3&{\it\unicode{xA3}}9,000&{\it\unicode{xA3}}1,000\\4&12,000&0\\\hline\end{array} When should I trade in my car?

Arc Length \begin{align}c_{i,j}=&\,\,\text{maintenance cost during years}\,\,i,i+1,\cdots,j-1\\&+\text{cost of purchasing a new car at year}\,\,i\\&-\text{trade-in value received at year}\,\,j\\\\c_{1,2}=&\,\,{\it\unicode{xA3}}2000+{\it\unicode{xA3}}12000-{\it\unicode{xA3}}7000={\it\unicode{xA3}}7000\\\\c_{2,3}=&\,\,{\it\unicode{xA3}}2000+{\it\unicode{xA3}}4000+{\it\unicode{xA3}}12000-{\it\unicode{xA3}}6000={\it\unicode{xA3}}12000\end{align}

Shortest Path Problem \begin{array}{|c|c|}\hline c_{i,j}&1&2&3&4&5&6\\\hline1&\phantom{25pt}&7,000&12,000&21,000&31,000&44,000\\\hline2&&&7,000&12,000&21,000&31,000\\\hline3&&&&7,000&12,000&21,000\\\hline4&&&&&7,000&12,000\\\hline5&&&&&&7,000\\\hline\end{array}

Could somebody please explain how in the last diagram, for $c_{2,3}$ they get $7,000$? I only understand how they get $c_{1,i}$ for $i=1,\ldots,6$ but that's all I can understand. If someone explains to me how they get it for $c_{2,3}$ then I'll be able to understand the whole of it.

Answer 1

It is the same calculation as $c_{1,2}$. The purchase price is £12,000 no matter when that purchase is made, and the rest of the costs depend on age of the car (number of years since purchase), not the actual year. So each row in the final table is the same as the previous row shifted one place to the right.

Answer 2

The constant car price means that $$c_{i,j}=12\,000-t_j+\sum_i^{j-1}m_i$$ where $t_j$ denotes the trade-in price on year $j$ and $m_i$ the maintenance cost on year $i$. Thus $$c_{i,i+1}=12\,000-t_{i+1}+m_i\tag1.$$ However, all indices can be shifted up or down (as @RobPratt mentions) as the age of the car from year $i$ to year $i+1$ is constant.

In particular, shifting $(1)$ down by $i-1$ and $i-2$ yields $c_{1,2}=c_{2,3}$ respectively.

Answer 3

In addition to @Rob Pratt's answer, consider the following table which helps you understand the shifts in each row of the matrix in the question:

\begin{array}{cccccc}\hline i & j & j-i & \rm{purchase} & \text{trade-in} & \rm{maintenance} & \rm{total}\\ \hline 1 & 2 & 1 & 12000 & 7000 & 2000 & 7000 \\ 2 & 3 & 1 & 12000 & 7000 & 2000 & 7000 \\ 3 & 4 & 1 & 12000 & 7000 & 2000 & 7000 \\ 4 & 5 & 1 & 12000 & 7000 & 2000 & 7000 \\ 5 & 6 & 1 & 12000 & 7000 & 2000 & 7000 \\ \hline \end{array}

This table summarizes the calculations for $c_{12},c_{23},c_{34},c_{45},c_{56}$ in each of its rows. All the costs are the same because the age or the value of $j-i$ is the same for all rows. Three other tables like the one I mentioned, this time with $j-i=2,3,4$ can be constructed to cover whole cost table in the question. This problem can also be solved by using Dynamic Programming.