MA 417 Spring 2021 EXAM II

Due Wed April 4/7 at 11:59PM

1-The exam has 4 equally weighted problems. For each problem, please show your work. Simply ``guessing’’ the answer does not get you any points even if your guess is correct. The exam is open-book and open-notes but you have to work alone. You are not allowed to ask for help from friends or tutors (this includes online tutors)

2-Write your answers clearly and in an organized fashion on blank pages. Number the page and write your name on every page you plan to submit. Submit all the work that you deem relevant but do not submit ``scratch work``.

3-Make sure to clearly define all the variables in any equation you use.

4-Please do not submit more than 10 pages for the entire exam. If you have problems submitting your answers to Canvas, you can email them to me directly as a pdf.

5-All the problems on this exam can be solved by hand. However, if you choose to, you can solve the various Bellman equations on the test by writing a simple computer code in your favorite programming language. In this case, please include a copy of the code and its output.

Problem 1.  Consider the following 4x5 array of numbers.

Suppose an individual movement in the array is allowed rightward one column or downward one row, but not both simultaneously. Suppose that we want to move from the upper left corner of the array to the lower right corner of the array by a sequence of such movements and in a way that minimizes the sum of the integers encountered.

a) Set this problem up as a shortest-path problem.

b) Write a Bellman equation that can be used to solve this problem. Make sure you define all the variables that you use in equation.

c) Solve the problem using the Bellman equation of part (b)

Problem 2.  An elementary school in Lexington has to come up with a replacement policy for its minibus over the next 6 years. A new minibus should be kept in service for at least for 2 years (unless it is bought at the beginning of the last period, in which case it can be sold at the end of that period). Moreover, the school cannot keep a minibus that is older than 5 years (if you enter a period with a 5-year- old bus, then you have to sell it at the beginning of that period). The price of a new minibus in period 1 is $50,000, and it increases at rate of 5% per year. The Salvage value of a minibus -as a function of its age- is given by the following table:

The per year maintenance cost of a minibus -as a function of its age- is given by the following table:

where age 0 means a new minibus. Assume that the School has to buy a new minibus at the beginning of period 1. For periods 2 through 6, the decision to keep or to replace the minibus is made at the beginning of every period. At the beginning of period 7, the school has to salvage the minibus. 

a) Let f(t,x) be the smallest cost of having the minibus from period t to the end of the period 6, if we start period t with a minibus of age x. Write the Bellman equation for f(t,x). Please define any variables you use.

b) Find the numerical value of f(4,3).

Problem 3.  Consider the following maximization problem:

Maximize 8x + 11y +6z +4w

Subject to 5x + 7y+ 4z +3w ≤ 14

where x, y, z, and w are binary variables with values that are either 0 or 1.

a) Formulate this problem as a knapsack problem.

b) Solve this problem using the Bellman equation of the knapsack problem.

Problem 4.  A tourist would like to visit 4 cities. The travelling time between a city i and a city j is shown in the table below. Starting from city 1, the tourist would like to visit all 4 cities (he does not have to return to the city where he started) in a way that minimizes the total travelling time. Suppose further the tourist does not want to stop at a city more than once.

For example, the travelling time between cities1 and 2 is 3 and travelling time between cities 3 and 4 is 2.

a) Using a Bellman equation, find the optimal path that this tourist must follow and find the corresponding travelling time it would take to complete this path.

b) Suppose the tourist can choose between starting his tour at city 1 or at city 4 (i.e the tourist can choose where to be dropped off initially). Where would he choose to start his tour ? (his goal is still to minimize travelling time and he still does not want to stop at the same city more than once). Please Justify your answer.