Question 3 of 9: Equipment Replacement — Six-Year Car Ownership Policy
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — December 2019 — 17-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 135 marks across 9 questions (all worth 15 marks) and only 100 marks are required, so a candidate would normally answer a subset — all nine are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear programming & the simplex method (ch. 3–4), duality & sensitivity analysis (ch. 6), integer programming (ch. 12), network optimization & CPM/PERT (ch. 9–10), queueing theory (ch. 17), decision analysis (ch. 15–16), Markov chains (ch. 16), equipment replacement (ch. 11/19). Nahmias, Production and Operations Analysis — single-period (newsvendor) inventory models.
Given. New-car price $P=\$10{,}000$ (assumed the same for every replacement over the horizon — no escalation is stated); resale value and that year's operating cost as tabulated above, by the car's age; a new car is owned at the start of year 1; 6-year planning horizon.
Find. The replacement policy (which years to trade the car in) that minimizes total net cost (purchases + operating − resale) over the six years.
Approach. This is the classic equipment-replacement problem, solved as a shortest-path/dynamic-programming recursion over a network whose nodes are "start of year $t$ with a brand-new car" ($t=0,\dots,6$): an arc from node $i$ to node $j$ means "buy a car at the start of year $i{+}1$ and keep it $a=j-i$ years," priced at the purchase price plus that many years' cumulative operating cost minus the resale value at age $a$. The minimum-cost path from node 0 to node 6 is the optimal policy.
Build the cost of keeping one car for $a$ years,$f(a)=P+\sum_{k=1}^{a}(\text{op. cost, year }k)-(\text{resale value at age }a)$, using the cumulative operating cost $\sum_{k=1}^a$ (300, 800, 1600, 2800, 4400, 6600 for $a=1,\dots,6$):
Net cost of one ownership cycle of length $a$ years, $f(a)$
$a$ (yr)
1
2
3
4
5
6
$f(a)$
$3,300
$4,800
$7,600
$9,800
$12,400
$15,600
e.g. $f(2)=10{,}000+800-6{,}000=4{,}800$.
Forward DP recursion. Let $V(n)$ = minimum cost to own/operate a car (through any number of trade-ins) for the first $n$ years, $V(0)=0$:
$$V(n)=\min_{1\le a\le n}\big[V(n-a)+f(a)\big]$$
Evaluating $n=1,\dots,6$ (the minimizing $a$ at each stage is starred):
DP table — minimum cost to cover the first $n$ years
$n$
0
1
2
3
4
5
6
$V(n)$
0
3,300
4,800
7,600
9,600
12,400
14,400
best last cycle $a^*$
—
1
2*
3*
2*
5, 3 or 2 (tie)
2*
$V(4)=\min[f(4),\,V(1){+}f(3),\,V(2){+}f(2),\,V(3){+}f(1)]=\min[9800,\,10900,\,9600,\,10900]=9600$ (via $V(2)+f(2)$, i.e. two 2-year cycles back to back); $V(6)=\min[f(6),\,V(1){+}f(5),\,V(2){+}f(4),\,V(3){+}f(3),\,V(4){+}f(2),\,V(5){+}f(1)]=\min[15600,15700,14600,15200,\mathbf{14400},15700]$.
Read off the optimal policy by backtracking from $V(6)=14{,}400$, achieved via $V(4)+f(2)$, and $V(4)=9{,}600$ itself achieved via $V(2)+f(2)$:
$$\boxed{\text{Replace the car every 2 years: trade in at the end of year 2 and year 4, keep the third car through year 6}}$$
$$\boxed{\text{Minimum total net cost over 6 years} = \$14{,}400}$$
Shortest-path view of the DP: each arc is a complete ownership cycle, weighted by $f(a)$. The cheapest way to span 6 years is three 2-year cycles.
