MA231-2019-exam

Summer Exam MA Operational Research Methods Suitable for all candidates Instructions to candidates This paper contains 6 questions. You may attempt as many questions as you wish, but only your best answers will count towards the nal mark. All questions carry equal numbers of marks. Answers should be justi ed by showing work. Please write your answers in dark ink (black or blue) only. Time Allowed Reading Time: None Writing Time: hours and minutes You are supplied with: No additional materials You may also use: No additional materials Calculators: Electronic Calculator (as prescribed in the examina- tion regulations) © LSE ST /MA Page of

Question (a) Suppose that in the entire confectionary market there are only two brands of chocolate bar, namely bar and bar . Given that a person last purchased bar , there is a % chance that her next purchase will be bar . Given that a person last purchased bar , there is an 8 % chance that her next purchase will be bar . (i) Each consumer’s purchases can be represented as a Markov chain. Write down the transi- tion matrix. (ii) If a person is currently a bar purchaser, what is the probability that she will purchase bar two purchases from now? If a person is currently a bar purchaser, what is the probability that she will purchase bar three purchases from now? (iii) The two brands have been established in the market for many years, and the consumers’ behaviour described above has remained stable for a long time. Compute the respective market shares of bar and bar . (iv) Suppose that each consumer purchases one chocolate bar during each week ( year= weeks). Suppose there are million chocolate bar consumers, and both companies make a net pro t of £ per chocolate bar sold. For £ million per year, an advertising rm guarantees to decrease from % to % the fraction of bar consumers who switch to bar after a purchase. Should the company that makes bar hire the advertising rm? [ marks] (b) Consider a Markov chain with n + 1 states 0 , 1 , 2 , . . . , n , where 0 is an absorbing state. From state 1 , we reach in one step any of the other n states { 0 } ∪ { 2 , . . . , n } with equal probability 1 /n . From any state i ∈ { 2 , . . . , n } , we reach in one step any of the n states 1 , . . . , n with equal probability 1 /n (in particular, we stay at i with probability 1 /n ). (i) Which states are recurrent? Which states are transient? Is there a limiting distribution? (ii) What is the expected number of steps to reach absorbing state starting from state ? What is the expected number of steps to reach absorbing state starting from any of the states 2 , . . . , n ? [8 marks] © LSE ST /MA Page of

Question (a) Sally has just bought a new car. She needs a car for years, but may decide at one or more times during the years to sell her car and replace it with a new one. She wants to decide on a replacement strategy to minimize the annual operating costs and resale value. To keep things simple, she decides that she will keep each car for a whole number of years. At the end of the year period she will sell the car that she owns at that time. Suppose that the price of a new car is xed for the next ve years at £ . The tables below show the resale value and annual maintenance costs of a car depending on its age. Age of car Resale (years) value (£) , 6, , , , Age of car Maintenance (years) cost (£) 8 , ,6 For example, if Sally decides to replace the car when it is years old, then the total cost of ownership will be the following: she will be spend £ , at the beginning, another £ , when the car reaches years, she will recover £ , by selling the rst car after three years, and another £6, by selling the second car after years. The maintenance cost of the rst car will be £ ,6 and the maintenance cost of the second car will be £8 . The total cost will be £ , . (i) Formulate the problem of determining the cheapest replacement policy as a shortest path problem. [6 marks] (ii) Find the optimal solution of the shortest path problem formulated in part (a) by using Dijk- stra’s algorithm. [8 marks] (b) The daily demand for substitute teachers in Camden follows the distribution given in the follow- ing table. Number Needed Probability . . . . . . . 6 . Camden Council wants to know how many teachers to keep in the substitute teacher pool. Whether or not the substitute teacher is needed, it costs £6 per day to keep a substitute teacher in the pool. If not enough substitute teachers are available on a given day, regular teachers are used to cover classes at a cost of £ per regular teacher. How many teachers should Camden have in the substitute teacher pool? [6 marks] © LSE ST /MA Page of

Question (a) At the present time, an average of . customers per hour arrive at a single-pump petrol station. It takes an average of minutes to service a car. Assume that interarrival times and service times are both exponential. What is the expected number of cars at the petrol station? How long will it take, on average, for a car to ll up the tank? [6 marks] (b) Joe wants to buy a laptop that costs £6 , despite having only £ . Joe is a gambler. There is a local casino that only takes bets that are multiples of £ , and allows a maximum of three games. In each game, Joe will bet a certain amount x . The game is designed so that he will win with probability 1 / 3 and lose with probability 2 / 3 . If he wins the game, he doubles the amount he bet (so he will get back the amount x he bet, plus x from the casino), whereas if he loses the casino keeps the money he bet. (i) Formulate the problem of maximizing the probability of buying the laptop as a dynamic program. [ marks] (ii) Solve the dynamic program. [ marks] (iii) What is the optimal probability of Joe buying the laptop? How much should he bet in the rst game? [ marks] © LSE ST /MA Page of

Question 6 Consider the linear programming problem ( P ) max 4 x 1 - 2 x 2 - 2 x 3 x 1 - 2 x 2 - x 3 ≤ 3 - x 1 + x 3 ≥ 5 - x 2 + x 3 = 8 - x 1 - x 2 ≤ 6 x 1 ≤ 0 , x 3 ≥ 0 (a) Write down the dual ( D ) of ( P ) . [ marks] (b) Prove that the point x * = (0 , - 3 , 5) is an extreme solution for ( P ) , and that it is optimal. Find a dual optimal solution y * . [ marks] (c) Can the dual ( D ) have more than one optimal solution? And the primal? In both cases, either provide alternate optimal solutions, or argue that none exist. [6 marks] (d) The objective coef cient of x 1 is currently 4 . If we replace it by another number c 1 , for which values of c 1 does the solution x * = (0 , - 3 , 5) remain optimal? [ marks] END OF PAPER © LSE ST /MA Page of