Shortest Path Problem

Michael just bought a car for $\backslash (\backslash$$ $12,000\backslash )$ and he is planning to use it in the next $4$ years after which he wants to sell it again.

The initial purchase cost has to be included in the total cost calculation.

During this time, he has to take care of his car and will pay a maintenance cost each year, depending on the age of the car.

Below is the yearly cost of maintenance $($in thousands of dollars$)$:

Michael can trade$-$in his car and buy a new one for $\backslash (\backslash$$ $12,000\backslash )$ at the end of any year.

The price he will receive from a trade$-$in also depends on the age of the car.

Below is the trade$-$in values $($in thousands of dollars$)$:

Michael wants to come up with a plan on when to trade$-$in his car and buy a new one in the next $4$ years so that he minimizes his total cost.

Hint: Think this as a shortest path problem where you start from year $0$ and want to reach year $4$ with minimum cost.

Note: Maintenance costs are cumulative. For example, if Michael keeps his car for $2$ years, he will pay $2\mathrm{.}12$ in year $1$ and $3\mathrm{.}44$ in year $2,$ but will trade it for $7\mathrm{.}93.$

Develop a model to find the optimal solution.

Develop a LP model clearly state the decision variable xij, and the meaning of xij, object fucntion in open form, and flow balance constraints foe year $0-$year $4.$