1.(20 points) Suppose that the purchase price of a new car is $9,000. As the car is getting older, operating costs increase while resale values decrease. The maintenance costs and resale values are given in the following table. We are planning to purchase a new car. Suppose that we must have a car during the following five years and then we sell the car. When is it optimal to replace the car in the following five years in order to minimize the total cost? (a) (10 points) Formulate the problem as a shortest route model. (b) (5 points) Write down a mathematical model for the shortest route problem (please define the decision variables clearly and specify the objective function and the constraints explicitly). (c) (5 points) Which algorithm do you suggest to solve the problem. Please implement the algorithm and find the optimal solution