Problem $4(30$ points$).$ A factory needs a certain type $of$ machine for the next five years. The

purchase cost $of$ the machine goes $upin$ time: $$17,000in$ year $1,$ $$19,000in$ year $2,$ $$21,000in$

year $3,$ $$25,000in$ year $4,$ and $$30,000in$ year $5.$ Once a machine $is$ purchased, its maintenance

$cost$ also goes $upasit$ ages: $$3,800$ for year $1,$ $$5,000$ for year $2,$ $$9,700$ for year $3,$ $$18,200$ for

year $4,$ and $$30,400$ for year $5.$ A new machine can $be$ purchased and used $to$ replace the existing

one $at$ any time, and the old machine will $be$ discarded with $no$ trade$-in$ value. The goal $isto$

minimize the total cost $(purchase$ plus maintenance$)of$ keeping a machine for the five years.

$(15$ points$)$ Formulate the problem $as$ a shortest path problem and use Dijkstra's

algorithm $to$ solve $it.$

$(15$ points$)$ Formulate the problem $asa(mixed-)integer$ linear optimization model

and use computer tools $to$ find $an$ optimal solution.