Use the policy improvement algorithm to find an optimal policy for Prob. 21.2-1.
Prob. 21.2-1
During any period, a potential customer arrives at a certain facility with probability ½ If there are already two people at the facility (including the one being served), the potential customer leaves the facility immediately and never returns. However, if there is one person or less, he enters the facility and becomes an actual customer. The manager of the facility has two types of service configurations available. At the beginning of each period, a decision must be made on which configuration to use. If she uses her "slow" configuration at a cost of $3 and any customers are present during the period, one customer will be served and leave the facility with probability 3/5 If she uses her "fast" configuration at a cost of $9 and any customers are present during the period, one customer will be served and leave the facility with probability 4/5 The probability of more than one customer arriving or more than one customer being served in a period is zero. A profit of $50 is earned when a customer is served.
(a) Formulate the problem of choosing the service configuration period by period as a Markov decision process. Identify the states and decisions. For each combination of state and decision, find the expected net immediate cost (subtracting any profit from serving a customer) incurred during that period.
(b) Identify all the (stationary deterministic) policies. For each one, find the transition matrix and write an expression for the (longrun) expected average net cost per period in terms of the unknown steady-state probabilities
(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.