A student is concerned about her car and does not like dents. When she drives to school, she has a choice of parking it on the street in one space, parking it on the street and taking up two spaces, or parking in the lot. If she parks on the street in one space, her car gets dented with probability 1 1

0

. If she parks on the street and takes two spaces, the probability of a dent is 5 1

0 and the probability of a $15 ticket is 1 3

0

. Parking in a lot costs $5, but the car will not get dented. If her car gets dented, she can have it repaired, in which case it is out of commission for 1 day and costs her $50 in fees and cab fares. She can also drive her car dented, but she feels that the resulting loss of value and pride is equivalent to a cost of $9 per school day. She wishes to determine the optimal policy for where to park and whether to repair the car when dented in order to minimize her (long-run) expected average cost per school day.

(a) Formulate this problem as a Markov decision process by identifying the states and decisions and then finding the Cik.

(b) Identify all the (stationary deterministic) policies. For each one, find the transition matrix and write an expression for the (longrun) expected average cost per period in terms of the unknown steady-state probabilities (0, 1, . . . , M).

A

(c) Use your OR Courseware to find these steady-state probabilities for each policy. Then evaluate the expression obtained in part

(b) to find the optimal policy by exhaustive enumeration.