MA231-2019-exam-solutions

MA Operational Research Methods Exam Solutions Summer 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. Solution : P = . 9 . 1 . 2 . 8 (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? Solution : P (2) = . 9 . 1 . 2 . 8 . 9 . 1 . 2 . 8 = . 83 . 17 . 34 . 66 P (3) = . 9 . 1 . 2 . 8 . 83 . 17 . 34 . 66 = . 781 . 219 . 438 . 562 P (2) 21 = . 34 , hence the probability that a bar customer will purchase bar two purchases from now is . 34 . P (3) 11 = . 781 , hence the probability that a bar customer will purchase bar three purchases from now is . 781 . (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 . Solution : The Markov chain is irreducible and aperiodic, therefore it has a limiting dis- tribution. In the long run, the distribution corresponds to the market shares. The limiting distribution is the unique stationary distribution. Hence we need to solve the system ( π 1 , π 2 ) . 9 . 1 . 2 . 8 = ( π 1 , π 2 ) π 1 + π 2 = 1 The solution is π 1 = 2 3 , π 2 = 1 3 . (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 © LSE ST /MA Page of

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] Solution : The total yearly sales of chocolate bars account for a 5 . 2 B£pro t, of which 2 3 · 5 , 200 , 000 , 000 = 3 , 466 , 666 , 667 £ go to company . The advertising rm is offering to change the transition matrix to P = . 95 . 05 . 2 . 8 This will lead to a new steady state, determined by the solution of the system ( π 1 , π 2 ) . 95 . 05 . 2 . 8 = ( π 1 , π 2 ) π 1 + π 2 = 1 The new solution is π 1 = . 8 , π 2 = . 2 . The new annual pro t of company will be 0 . 8 · 5 , 200 , 000 , 000 - 500 , 000 , 000 = 3 , 660 , 000 , 000 £ . This is more than the current pro t, hence company should hire the advertising agency. (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? Solution : All states are transient except for state 0 , which is recurrent (indeed, it is ab- sorbent). Even though the Markov Chain is not irreducible (which is a requirement to apply the ergodic theorem), there is a limiting distribution, since eventually we will end up in the absorbing state 0 . The limiting distribution is π 0 = 1 , π i = 0 for i = 1 , . . . , n . (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 ? Solution : By symmetry of the problem, the expected number of steps q to reach absorbing state zero is equal for all starting states 2 , . . . , n . Let us denote by p the expected number of steps to reach 0 from state 1 . p and q must satisfy the following p = 1 + n - 1 n q q = 1 + n - 1 n q + 1 n p Solving this system gives p = n 2 , q = n 2 + n . Hence the expected number of steps to reach from any of the states 2 , . . . , n is n 2 + n . [8 marks] © LSE ST /MA Page of

0 - 2 - 4 3 0 3 5 - 4 s = 3 s = 1 s = 2 p = 0 p = 1 Todd’s expected payoffs for each of Steve’s available responses are as follows: • s = 1 : 3 p - 2(1 - p ) • s = 2 : - 4 p + 3(1 - p ) • s = 3 : 5 p - 4(1 - p ) From the gure, one can see that the lower-envelope of the lines corresponding to Steve’s strate- gies is de ned only from strategies s = 2 and s = 3 . The maximum of the lower envelope is achieved where the corresponding lines meet, that is, where - 4 p + 3(1 - p ) = - 5 p + 4(1 - p ) . Solving the above equation gives p = 7 / 16 . Hence the value of the game is v * = - 4 p + 3(1 - p ) = - 7 p + 3 = - 1 / 16 , and Todd’s optimal strategy is to play t = 1 with probability 9 / 16 and t = 2 with probability 7 / 16 . In the optimal strategy, Steven should never play strategy s = 1 , since the best response strate- gies against Todd’s (9 / 16 , 7 / 16) are s = 2 and s = 3 . If Steven plays s = 2 with probability q and s = 3 with probability 1 - q , the optimal q is the solution to the equation 3 q - 4(1 - q ) = - 4 q + 5(1 - q ) , where the LHS and RHS are, respectively, Steve’s expected losses if Todd plays t = 1 or t = 2 . The solution to the above equation is q = 9 / 16 , hence Steven’s optimal strategy is to play s = 2 with probability 9 / 16 , and s = 3 with probability 7 / 16 . (e) Todd proposes to change the game so that he can play , , or ngers, whereas Steven can play or ngers. (i) Should Steven accept? No calculations are needed; explain your reasoning. © LSE ST /MA Page of

Solution : Steve should not accept, since the new rules are more unfavourable to him than the previous ones. Indeed, Todd could still decide to play the same strategy as before (that is t = 1 with probability 9 / 16 , t = 2 with probability 7 / 16 , and t = 3 with probability 0 ), but now Steve would be forced to only play 1 or 2 , whereas we know from the previous point that his optimal response required him to play s = 3 with positive probability. (ii) Determine the optimal strategies of both players and the value of the game under these new rules. Solution : Under the new rules, the payoff matrix with Todd as row-player would be   - 2 3 3 - 4 - 4 5   . This is the transpose of the previous matrix. Steve now has two strategies, hence we can represent the problem of determining his optimal strategy with a diagram. If p is the proba- bility of playing s = 2 , and 1 - p the probability of playing s = 1 , the corresponding diagram for Steve is now the same as the one we drew above, with the difference that now Steve wants to nd the minimiser of the upper-envelope of the three lines corresponding to Todd’s strategy. From the picture, the minimiser is de ned by the lines corresponding to strategies t = 1 and t = 2 . Hence Steve’s optimal choice of p is the one that solves the equation 3 p - 2(1 - p ) = - 4 p + 3(1 - p ) , which is p = 5 / 12 . Hence Steve’s optimal strategy is to play s = 1 with probability 7 / 12 , and s = 2 with probability 5 / 12 . The value of the game is 1 / 12 . Todd’s optimal response is never to play t = 3 , and to play t = 1 with probability q , where q is the solution to the equation - 2 q + 3(1 - q ) = 3 q - 4(1 - q ) , which is q = 7 / 12 . Hence Todd’s optimal strategy is (7 / 12 , 5 / 12 , 0) . [6 marks] © LSE ST /MA Page of

Solution : We report the execution of Dijkstra’s algorithm in the table below. Each row represents an iteration of the algorithm. In the “added to R ” column we show the node added and, in parentheses, its distance from 0 . In the columns for each node through , we show the current distance estimate and, in parentheses, the corresponding pre- decessor (if any). iter Added to R 3 . 3 ( ) 4 . 8 ( ) 7 . 6 ( ) 9 . 8 ( ) 13 . 4 ( ) ( 3 . 3 ) – – – – – 13 . 1 ( ) ( 4 . 8 ) – – – – 9 . 6 ( ) 12 . 4 ( ) ( 7 . 6 ) – – – – – – ( 9 . 6 ) – – – – – – 6 ( 12 . 4 ) – – – – – – Hence the shortest path from 0 to 5 is the path 0 , 2 , 5 . The optimal solution is to replace car when it reaches years of age, and then keep it until the end. (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? Solution : This is a newsvendor problem. The shortage cost is p = 100 , whereas the pur- chase cost is c = 60 . There is no inventory cost, so h = 0 . The optimal level of substitute teachers on staff S * is determined by the equation F ( S * ) = p - c p + h = 0 . 4 , where F is the cumulative distribution. We see that F (400) = . 05 + . 10 + . 10 + . 15 = . 4 , hence S * = 400 . [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] Solution : λ = 7 . 5 cars per hour, μ = 15 cars per hour, ρ = λ μ = 1 2 . Number of cars in the system: L S = ρ 1 - ρ = 1 . The waiting time is W S = L S λ = 1 7 . 5 hours = 8 minutes . (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] Solution : The formulation is as follows: Stages: n = number of bets/games remaining (n= , , ) States: s = money at hand, in hundreds of pounds. Decisions: x = how much to bet in the current bet/game, must have x ≤ s . Transition probabilities: p ( n, s, x, j ) =          1 3 for j = s + x , x > 0 2 3 for j = s - x , x > 0 1 for j = s , x = 0 0 otherwise ( ) Finally, let f ( n, s ) = probability of raising £ 600 , if we use the optimal policy, given that we have s money at hand and n bets remaining. We have the following recursive equa- tion: f ( n, s ) = max 0 ≤ x ≤ s    X j p ( n, s, x, j ) f ( n - 1 , j )    . (ii) Solve the dynamic program. [ marks] Solution : We start with n = 1 , one investment period remaining. The state can be at most s = 8 (if Joe bets all his money twice and wins). Here, if s = 6 , 7 , 8 , then we © LSE ST /MA Page 8 of

Question Steelco uses coal, iron, and labour to produce two types of steel. The inputs (and sales price) for one ton of each type of steel are shown in the next table. The table also reports the sales price per ton of each steel. Steel Coal Iron Labour Sales required (tons) required (tons) required (hours) prices (£) . 6 . 8 Up to tons of coal can be purchased at a price of £ per ton. Up to 6 tons of iron can be purchased at £8 per ton, and up to labour hours can be purchased at £ per hour. (a) Formulate the problem of choosing the most pro table production mix as a linear programming problem. Let x 1 = tons of steel produced; x 2 = tons of steel produced. [ marks] Solution : Unit pro t for steel of type = 63 . 5 - 4 · 10 - 8 - 1 . 5 · 5 = 8 . Unit pro t for steel of type = 38 - 2 · 10 - 8 - 5 = 5 . The LP is max 8 x 1 +5 x 2 4 x 1 +2 x 2 ≤ 200 (Coal) x 1 + x 2 ≤ 60 (Iron) 1 . 5 x 1 + x 2 ≤ 90 (Labour) x 1 , x 2 ≥ 0 (b) Draw a diagram representing the problem de ned in the previous part. From the diagram, infer what the optimal solution is, and prove optimality algebraically. [ marks] Solution : © LSE ST /MA Page of

x 1 + x 2 ≤ 60 4 x 1 + 2 x 2 ≤ 200 1 . 5 x 1 + x 2 ≤ 90 x 1 x 2 The optimal solution is at the intersection of constraints and , and can be computed by solving the corresponding by system as the point x * = (40 , 20) . Optimality can be veri ed by computing the solution to the system 4 y 1 + y 2 = 8 2 y 1 + y 2 = 5 The solution is y 1 = 3 / 2 , y 2 = 2 . Since these are nonnegative, it follows that x * is primal optimal. The optimal value is . (c) Write the dual of the problem formulated in part (a). What is the optimal dual solution? [ marks] Solution : min 200 y 1 +60 y 2 +90 y 3 4 y 1 + y 2 +1 . 5 y 3 ≥ 8 (Steel1) 2 y 1 + y 2 + y 3 ≥ 5 (Steel2) y 1 , y 2 , y 3 ≥ 0 From the previous part, it follows that the optimal dual solution y * = ( 3 2 , 2 , 0) . (d) What would the pro t be if only tons of iron could be purchased? [ marks] Solution : The optimal basis does not change as long as the right-hand-side of the con- straint for iron is between 50 (at which point the optimal solution is de ned by the coal con- © 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] Solution : min 3 y 1 +5 y 2 +8 y 3 +6 y 4 y 1 - y 2 - y 4 ≤ 4 - 2 y 1 - y 3 - y 4 = - 2 - y 1 + y 2 + y 3 ≥ - 2 y 1 ≥ 0 , y 2 ≤ 0 , y 4 ≥ 0 (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] Solution : It is extreme because it satis es at equality linearly independent constraints. Namely, x 1 ≤ 0 and the second and third resource constraints. For optimality, we need to nd a dual solution y such that y 1 = y 4 = 0 , and such that y satis es the second and third dual constraint as equality. - y 3 = - 2 + y 2 + y 3 = - 2 y 1 = 0 , y 4 = 0 The solution is y * = (0 , - 4 , 2 , 0) . We verify that y * is indeed dual feasible, which indeed it is. It follows that x * is primal optimal and y * is dual optimal. (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] Solution : From the above argument, y * is the only dual optimal solution. However, in principle there might be more than one optimal primal solution, because y * satis es the rst dual constraint as equality while x * 1 = 0 . Since y * satis es all resource constraints at equality, a primal feasible solution is optimal if and only if it satis es at equality the constraints corresponding to nonzero entries of y * , that is, the second and third primal constraints. These are - x 1 + x 3 = 5 - x 2 + x 3 = 8 The optimal solutions are all the feasible solution that satisfy x 1 = x 3 - 5 , x 2 = x 3 - 8 , i.e. all points of the form x ( α ) = ( α - 5 , α - 8 , α ) . Note that x 1 ( α ) ≤ 0 if and only if α ≤ 5 . Substituting into the rst constraint gives α ≥ 4 , while substituting into the fourth constraints gives α ≥ 3 . 5 . In particular, x ( α ) is optimal for every α ∈ [4 , 5] . For example x = ( - 1 , - 4 , 4) is optimal. (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] © LSE ST /MA Page of

Solution : The solution x * remains optimal as long as the optimal dual solution y * = (0 , - 4 , 2 , 0) satis es the dual constraint y 1 - y 2 - y 4 ≤ c 1 . Since y * 1 - y * 2 - y * 4 = 4 , x * is optimal for all values c 1 ≥ 4 . END OF PAPER © LSE ST /MA Page of