A factory needs a special machine for each of the next seven years and plans to buy a new machine now. The machine is inspected at the end of every year and then either refurbished for use in the following year or replaced by a new one. The overhaul cost and residual value depend on the age of the machine and are given in the table below. A machine that has been in use for five years cannot be refurbished and must be replaced. A new machine costs 10000. Determine an optimal maintenance- replacement schedule using a shortest-path problem in an acyclic network. Age 1 2 4 5 Overhaul Cost 800 900 1100 1600 Residual Value 6000 5000 4000 1500 500