MA231-2022-ST-solutions

MA Operational Research Methods Exam Solutions Summer Question (a) A car hiring company checks its vehicles at the end of every week, and classi es each vehicle in one of four categories: “good”, “tolerable”, “poor”, “bad”, in order from best to worst working con- ditions. If a vehicle is classi ed as “bad”, it is repaired over the weekend, and it is then classi ed as “good” at the beginning of the week. Throughout the week, the vehicles can deteriorate, al- though vehicles never deteriorate by more than one category. The probability of deterioration is given in the following table (the table refers to the classi cation of the vehicles at the beginning of the week) Classi cation at the beginning of the week good tolerable poor Probability of deterioration . . . (i) Write down the transition matrix for this process, and draw the transition diagram. [ marks] Solution : The Markov chain has three states: “Good” (G), “Tolerable” (T), and “Poor” (P). In state “Poor”, there is a . probability of deterioration, which means that the vehicle will be classi ed as “bad”, and therefore repaired over the weekend, meaning that the next state will be “Good”. The transition matrix and diagram for the Markov Chain are: P =   0 . 9 0 . 1 0 0 0 . 8 0 . 2 0 . 4 0 0 . 6   G T P 0 . 9 0 . 8 0 . 6 0 . 1 0 . 2 0 . 4 (ii) State formally the Ergodic Theorem. Does this speci c Markov chain satisfy the theorem’s hypotheses? Justify your answer. [ marks] Solution : The Ergodic theorem states that any nite, aperiodic, irreducible time homoge- nous Markov chain has a limiting distribution. Furthermore, the limiting distribution is the unique stationary distribution. The chain is aperiodic, because there is a positive probability of remaining in the same state, it is irreducible, because every state is reachable from every other state. (When stating the Ergodic Theorem, it is acceptable not to mention the hypoth- esis that the Markov chain is nite and time homogeneous, since this is always assumed throughout the lecture notes.) (iii) In the long run, what is the expected proportion of vehicles classi ed as “good”, “tolerable”, or “poor” at the beginning of any week? [ marks] © LSE ST /MA Page of

Solution : From the previous point, the chain has a limiting distribution, hence in the long run the expected proportion of vehicles classi ed as “good”, “tolerable”, or “poor” at the beginning of any week will be equal to the corresponding probabilities in the limiting distri- bution. To compute these, we need to nd the unique stationary distribution by solving the system - 0 . 1 π G + 0 . 4 π P = 0 0 . 1 π G - 0 . 2 π T = 0 0 . 2 π T - 0 . 4 π P = 0 π G + π T + π P = 1 The solution to this system is π G = 4 7 , π T = 2 7 , π P = 1 7 (iv) Every how many weeks, on average, is a vehicle repaired? [ marks] Solution : We want to know how long it takes, on average, for a vehicle that is currently classi ed as “good” to be classi ed as “bad”. To do this, we can modify our Markov chain to include a new state “bad” (B), which will be absorbing. The average number of weeks be- tween two consecutive repairs of the same vehicle is the expected number of steps before we reach the absorbing state B. P =    0 . 9 0 . 1 0 0 0 0 . 8 0 . 2 0 0 0 0 . 6 0 . 4 0 0 0 1    G T P B 0 . 9 0 . 8 0 . 6 1 0 . 1 0 . 2 0 . 4 If we let t i be the expected number of weeks to reach state B from state i ( i = G, T, P ), we need to solve t G = 1 + 0 . 9 t G + 0 . 1 t T t T = 1 + 0 . 8 t T + 0 . 2 t P t P = 1 + 0 . 6 t P The solution is t G = 17 . 5 , t T = 7 . 5 , t P = 2 . 5 . Hence a vehicle gets repaired, on average, every . weeks. (b) Consider the Markov chain with the following transition diagram, where the transition probabil- ities are given in terms of a parameter p , 0 < p < 1 . (i) Determine the expected number of steps, as an expression of p , before absorption in node 0 , in the case of starting from node 1 and in the case of starting from node 2 . [ marks] Solution : If we let t i , i = 0 , 1 , 2 be the average number of steps to absorption into node © LSE ST /MA Page of

(b) Reduce the game by eliminating dominated strategies. [ marks] Solution : Note that for Giacomo, HH dominates TT . Thus we can eliminate strategy TT : N 1 N 2 G 1 + G 2 + - (c) Find the best strategies for Giacomo and Neil. [ marks] Solution : Using the minimax criterion we nd that there are no solutions in pure strategies. We can use mixed strategies with mixtures ( p 1 , p 2 ) for G and ( q 1 , q 2 ) for N . We need to have p 2 = p 1 - 2 p 2 (payoff if N plays N 1 equals payoff if N plays N 2 ), which gives p 1 = 3 / 4 , p 2 = 1 / 4 . Similarly q 2 = q 1 - 2 q 2 (loss if G plays G 1 equals loss if G plays G 2 ), which gives q 1 = 3 / 4 , q 2 = 1 / 4 . This gives optimal mixtures ( 3 4 , 1 4 ) for ( G 1 , G 2 ) and ( 3 4 , 1 4 ) for ( N 1 , N 2 ) . (d) State the value of the game. [ marks] Solution : The value of the game is: p 2 = p 1 - 2 p 2 = 1 4 . Neil now suggests to Giacomo that in the case of three heads, Neil should take £ 1 from Giacomo, instead of the game being a draw, whereas in the case of three tails Giacomo should take £ 2 from Neil instead of a draw. (e) Write the problem of determining Neil’s optimal strategy for this new game as an LP. [ marks] Solution : The new game is as follows: N 1 N 2 G 1 - + G 2 + - G 3 - + From Neil’s perspective, this gives the LP min v - q 1 + q 2 ≤ v q 1 - 2 q 2 ≤ v - 2 q 1 +2 q 2 ≤ v q 1 + q 2 = 1 q 1 , q 2 ≥ 0 (f) Find the new optimal strategies. Should Giacomo accept Neil’s proposal? How much difference does it make to his expected winnings or losses? [ marks] © LSE ST /MA Page of

Solution : The game has no solution in pure strategies and we cannot reduce it using dom- inance. Since it is a 3 × 2 game we plot the strategies of player N as two vertical axes on a diagram and on these axes we plot the strategies of player K as shown in the diagram. N 1 N 2 G 1 G 3 G 2 From the diagram we can see that the two strategies of player G that will be involved in the optimal solution are G 1 = HH and G 2 = HT . The optimal strategy for Neil satis es - q 1 + q 2 = q 1 - 2 q 2 , which gives ( q 1 , q 2 ) = ( 3 5 , 2 5 ) . The new value of the game is v = - 1 5 . If Giacomo accepts the value will reduce from 1 4 to - 1 5 . Thus, if Giacomo accepts, his payoff is reduced by 9 20 . Question (a) DHK is an online distribution company. It has m packets to deliver to location X in the next N days. There can be up to one delivery every day; the delivery cost varies per day and is c t per packet on day t = 1 , . . . , N . On any day it cannot send more than the capacity of the vehicle, which is K . Further, any delivery before day N is subject to a storage cost of w per packet per night spent at location X before day N . For example, if packets are delivered on day , then the corresponding costs amount to 5 c 2 +5( N - 2) w . We want to determine the optimal delivery schedule for days 1 , . . . , N . (i) Formulate the problem as a dynamic program, using as state variable the number of pack- ets delivered so far. For all days, explicitly state upper and lower bounds for the action variable that ensure feasibility of the delivery process. [ marks] Solution : Stages: n = number of days remaining, n = 1 , . . . , N States: s = number of packets delivered so far. Decisions: x = number of packets delivered on current day, where we must have x ≤ K but also x ≤ m - s ; thus we have 0 ≤ x ≤ min { K, m - s } . Further, we need to ensure that we make a minimum delivery when there are n days remaining to ensure that it is possible to deliver all remaining packets m - s in the n - 1 remaining days excluding the current day(given that max K can be delivered per day); this gives: max { ( m - s ) - ( n - 1) K, 0 } ≤ x . Thus the inequalities for x to ensure feasibility are: © LSE ST /MA Page of

and the shortage cost is p = £ 12 . We compute Q * = s 2 dK h · p + h p = 120 , t * = Q * d = s 2 K dh · p + h p = 3 . Hence the store should order guitars every months. (ii) How would changing the selling price from £6 to £ change the cycle length? [ marks] Solution : The selling price has no relevance to the ordering strategy, hence the cycle length would not change. © LSE ST /MA Page of

Question A company producing custom parts relies on an expensive stamping machine. At the beginning of year , a new machine must be purchased. The cost of maintaining a machine i years old is given in the next table. Age at start Maintenance cost of year for the year (£) 8, 8 , , , , The cost of purchasing a machine is £ , , and will remain unchanged over the next years. There is no trade-in value when a machine is replaced. For example, if a machine is bought at the beginning of year and then replaced at the beginning of year , that machine will contribute to the total cost for +( 8+8 + ) thousands pounds (£ , being the purchasing cost of the new machine, and the machine having to be maintained for year at £ 8, , for year at £8 , , and for year at £ , ). Your goal is to minimize the total cost (purchase plus maintenance) of having a functioning machine in each of the next ve years (from the start of year through year ), by determining the years in which a new machine should be purchased. (a) Model this as a shortest path problem: you need to specify what the nodes are, what the arcs are, what the lengths of the arcs are, and how a shortest path corresponds to a minimum cost solution to the problem described above. [8 marks] Solution : The network has 6 nodes, 1 , . . . , 6 , and it has an arc ( i, j ) for every i, j such that 1 ≤ i < j ≤ 6 . Arc ( i, j ) corresponds to buying a new machine at the beginning of year i , and keeping it until the end of year j - 1 . The length ‘ ij of arc ( i, j ) is thousand pounds, plus the cost of maintaining the machine for j - i years. If we denote by c t the purchasing cost plus maintenance cost for t years (in thousand £), then ‘ ij = c j - i . We have • c 1 = 170 + 58 = 228 , • c 2 = 170 + 58 + 80 = 308 , • c 3 = 170 + 58 + 80 + 110 = 418 , • c 4 = 170 + 58 + 80 + 110 + 203 = 621 , • c 5 = 170 + 58 + 80 + 110 + 203 + 250 = 871 . 1 2 3 4 5 6 228 228 228 228 228 (b) Solve the above problem using Dijkstra’s algorithm. What is the optimal purchasing and main- tenance schedule for the machine? [ marks] © LSE ST /MA Page 8 of

Question Consider the following linear programming problem: min 2 x 1 +5 x 2 +3 x 3 x 1 +2 x 3 ≥ 1 x 1 + x 2 ≥ 4 - 2 x 1 + x 2 + x 3 ≥ 3 x 1 ≤ 0 , x 3 ≥ 0 . ( P ) (a) Write the dual linear program ( D ) of ( P ) . [ marks] Solution : max y 1 +4 y 2 +3 y 3 y 1 + y 2 - 2 y 3 ≥ 2 y 2 + y 3 = 5 2 y 1 + y 3 ≤ 3 y 1 , y 2 , y 3 ≥ 0 ( D ) (b) Prove that the point x * = (0 , 4 , 1 2 ) is an optimal solution to ( P ) by nding an appropriate dual solution. [ marks] Solution : We rst check that x * is feasible by substituting into all inequalities. For x * , the tight constraints are the rst and second one. By complementary slackness, y 3 = 0 in an optimal solution, and the second and third dual inequalities must hold at equality. From the second constraint, we see that y 2 = 5 . From the third one, we see that y 1 = 1 . 5 . The only candidate dual optimal solution is y * = (1 . 5 , 5 , 0) . This is feasible, since 1 . 5 + 5 > 2 , and has the correct signs. Therefore, x * is a primal optimal solution and y * is a dual optimal solution. (c) Is x * an extreme point of the system ( P ) ? Justify your answer. [ marks] Solution : The point x * satis es altogether three inequalities at equality (the rst, second, and x 2 ≤ 0 ). These inequalities are linearly independent, and therefore x * is an extreme point. (d) Does ( P ) have any other optimal solutions? Provide another optimal solution, if there exists one, or argue that x * is the unique optimal solution. [ marks] Solution : x * is the unique optimal solution. Indeed, y * = (1 . 5 , 5 , 0) was a dual optimal solu- tion. By complementary slackness, all primal optimal solutions must satisfy the rst and second inequality at equality, and must have x 2 = 0 . These uniquely de ne the extreme point x * . (e) The coef cient of x 1 in the objective function is ; let us replace it by another number α ∈ R . For what values of α does x * remain an optimal solution to ( P ) ? [ marks] Solution : The possible values of α are ( -∞ , 6 . 5) . To see this, the argument in (i) is valid for any value of α , showing that any dual optimal y must satisfy the second and third dual inequalities at equality, and must have y 3 = 0 . Consequently, y = y * = (1 . 5 , 5 , 0) is the only possible choice, hence x * is optimal for the primal if and only if y * is feasible for the dual. Note that y * satis es all the dual constraints except possibly for the rst one, which is y 1 + y 2 - 2 y 3 ≥ α . Substituting © LSE ST /MA Page of

y = y * in the inequality, the condition we obtain is α ≤ 1 . 5 + 5 + 2 · 0 = 6 . 5 . (f) The coef cient of x 2 in the objective function is ; let us replace it by another number α ∈ R . For what values of α does x * remain an optimal solution to ( P ) ? [ marks] Solution : This corresponds to replacing the right-hand-side of the dual constraint with α . The solution x * remain optimal if the unique solution to the system y 2 + y 3 = α 2 y 1 + y 3 = 3 y 3 = 0 is dual feasible. The solution is y = (1 . 5 , α, 0) . This is feasible if it is nonnegative – i.e. α ≥ 0 – and if it satis es the rst dual constraint – i.e. 1 . 5 + α ≥ 2 . Hence x * is optimal for every α ≥ 0 . 5 . © LSE ST /MA Page of

Solution : The optimal solution is at the intersection of constraints and , that is 3 x 1 +3 x 2 = 24 2 x 1 +5 x 2 = 20 which is the point x * = ( 20 3 , 4 3 ) . Note that this solution is indeed feasible. To prove optimality, we need verify that the solution to the system 3 y 1 +2 y 2 = 5 3 y 1 +5 y 2 = 6 is nonnegative. The solution is y 1 = 13 9 , y 2 = 1 3 , which is nonnegative. This proves that x * is optimal. (d) Write the dual of the problem de ned in part (a). Using the result of part (c), determine the optimal dual solution. [ marks] Solution : max 24 y 1 +20 y 2 +18 y 3 3 y 1 + 2 y 2 + 6 y 3 ≤ 5 3 y 1 + 5 y 2 + y 3 ≤ 6 y 1 , y 2 , y 3 ≥ 0 ( D ) The optimal dual solution, from the previous point, is y * = ( 13 9 , 1 3 , 0) . (e) Alset is interested in knowing how changing the target for Af uent Women affects the total cost. How much does a unit increase or decrease in the target affect the total cost? Compute the range for which this estimate holds (i.e. compute the upper and lower range for the target). [ marks] Solution : The dual variable relative to the Af uent Women target constraint is y 1 , which takes value 13 / 9 . Therefore any unit increase or decrease in the right hand side will, respectively, increase or decrease the total cost by 13 / 9 , as long as the change in right-hand side does not change the optimal dual solution. The optimal dual solution does not change as long as the optimal primal solution is de ned by constraints and . Thus the right-hand side can decrease until constraint passes through the intersection of constraints and , and increase until it passes through the intersection of constraint and of the constraint x 2 ≥ 0 . Constraints and intersect at point ¯ x = (5 / 2 , 3) , therefore the target for Af uent Women can decrease until 3 · 5 / 2 + 3 · 3 = 16 . 5 . Constraint and x 2 = 0 intersect at the point ¯ x = (10 , 0) , thus the target for Af uent Women can increase until 3 · 10 + 3 · 0 = 30 . Another, more formal way to do this, is that the range of the right-hand-side of constraint 1 can take values 24 + α for every α such that the solution to 3 x 1 +3 x 2 = 24 + α 2 x 1 +5 x 2 = 20 is feasible. The solution to the above system is x = ( 20 3 + 5 9 α, 4 3 - 2 9 α ) . © LSE ST /MA Page of

In order for the solution to be non-negative and to satisfy the third constraint, α must satisfy 20 3 + 5 9 α ≥ 0 = ⇒ α ≥ - 12 4 3 - 2 9 α ≥ 0 = ⇒ α ≤ 6 6( 20 3 + 5 9 α ) + ( 4 3 - 2 9 α ) ≥ 18 = ⇒ α ≥ - 7 . 5 This implies that - 7 . 5 ≤ α ≤ 6 , which means that the right-hand-side can can be between 6. and . (f) The £6, per slot cost for TV advertisement is just an estimate, so Alset would like to know how deviations from the estimate affect the solution. How much can the cost per minute of TV advertisement increase before the optimal solution computed in part (d) changes? How much can it decrease? [ marks] Solution : The current optimal primal solution remains optimal for the objective function 5 x 1 + θx 2 until θ increases to the point where its contours are parallel to constraint , that is 2 x 1 + 5 x 2 ≥ 20 . This happens when θ = 12 . 5 . The current optimal primal solution remains optimal for the objective function 5 x 1 + θx 2 until θ decreases to the point where its contours are parallel to constraint , that is 3 x 1 + 3 x 2 ≥ 24 . This happens when θ = 5 . END OF PAPER © LSE ST /MA Page of