EXAMINATION PAPER Examination Session: May Year: 2019 Exam Code: MATH3141-WE01 

 Title: Operations Research 

 Time Allowed: 3 hours Additional Material provided: None Materials 

Permitted: None Calculators Permitted: Yes Models Permitted: Casio fx-83 GTPLUS or Casio fx-85 GTPLUS. Visiting Students may use dictionaries: No Instructions to Candidates: Credit will be given for: the best FOUR answers from Section A and the best THREE answers from Section B. Questions in Section B carry TWICE as many marks as those in Section A. Revision: ED01/2019 University of Durham Copyright Page number 2 of 7 Exam code MATH3141-WE01 SECTION A 1. Solve the following linear program by using the two phase method, and state all feasible values of x1, x2, and x3 for which the optimal value is attained. max 3x1+4x2x3 subject to x1 +x3 4 x1 x2x3 3 x1 0 x2 0 x3 0 2. Consider the transportation problem with costs, supplies, and demands respectively given by: 1 2 3 30 [cij]= 3 2 6 [ai]= 70 [bj]= 60 20 20 (a) Find the optimal transportation scheme. (b) Consider the same problem but where transportation from source 1 to destina- tion 1 (with c11 = 1) is no longer possible. Derive the new optimal transporta- tion scheme. 3. Consider the following network: 1 1 3 266 416 3447 327 554 The numbers on the arcs denote distances between nodes. (a) Apply Dijkstras algorithm to find the shortest distance from node 1 to node 7. (b) Identify all shortest paths from node 1 to node 7. ED01/2019 CONTINUED University of Durham Copyright ED01/2019 CONTINUED Page number Exam code 3 of 7 MATH3141-WE01 4. An allotment enthusiast wishes to plant their 17 foot wide allotment space with rows of carrots, potatoes and pumpkins. Each row of carrots takes up 2 feet of space, each row of potatoes takes up 4 feet of space while each row of pumpkins takes up 7 feet of space. The allotment enthusiasts personal returns (on a scale of 1 to 10) are 1 for each row of carrots, 4 for each row of potatoes and 9 for each row of pumpkins. However, the allotment enthusiast has already 2 rows of potatoes planted from last winter, which they are not willing to dig out (so there are already 2 rows of potatoes planted). Formulate the above resource allocation problem and use dynamic programming to find the selection of rows that maximizes the enthusiasts total personal reward. 5. Consider the economic lot-size model in which shortages are not permitted, the rate of continuous demand is a, orders have setup cost K and unit cost c, and the continuous holding cost is h per unit of inventory per unit time. (a) Show that the average cost per unit time as a function of the order size Q is U(Q) = aK + ac + Qh. Q2 (b) Deduce a formula for the optimal order size Q in terms of a, K, and h. Suppose now that a 50% quantity discount is introduced, so that the unit cost is reduced to c/2 on orders of at least 15 units. (c) IfK=100,c=1,a=2,andh=1,findtheoptimalordersizeforthemodel with 50% quantity discount. 6. Consider a Markov chain (Xn) with state space {1, 2, 3, 4, 5, 6} and transition matrix 1 0 0 0 0 0 (a) (b) 100000 What is the probability of hitting state 6 before state 1 when starting from state 2? Compute the expected time of reaching state 1 when starting from state 2. 21 0 12 0 0 0 P = 21 0 0 0 12 0 . 0 1 0 0 0 1 22 000101 22 University of Durham Copyright Page number 4 of 7 Exam code MATH3141-WE01 SECTION B 7. Consider a transportation system that can be represented by the following flow network, with capacities as labelled: a 4 1 5 6 3 d g 3 s6b33t 8 3 4 2 e 3 5 c 4 h 4 ED01/2019 CONTINUED We are specifically interested in the flow from s to t. (a) Apply the Ford-Fulkerson algorithm to find the maximum flow from the source s to the terminus t. (b) Find a cut separating s and t with minimal capacity. (c) Identify all arcs that provide an opportunity for increasing the maximal flow, and provide a theoretical argument as to why only these arcs provide this op- portunity. You may use, without proof, any theorems proved in the lectures, as long as you state them clearly. (d) Pick one of the arcs that you just identified. Increase its capacity by 3, and find the new maximal flow as well as a new cut between s and t with minimal capacity. University of Durham Copyright Page number Exam code 5 of 7 MATH3141-WE01 8. Consider a case where someone has solved the following linear programming prob- lem: max x1 +3x2 +4x3 +2x4 (1a) subject to 2x1+ x2+ x3+2x4 2 (1b) 3x1+ x2+2x3+2x4 3 (1c) x1+2x2+4x3+ x4 7 (1d) and subject to all xi 0 for i {1,2,3,4}. The initial simplex table for this problem is T0 x1 x2 x3 x4 s1 s2 s3 z1342 0 0 00 s1 21121002 (2) s2 31220103 s3 12410017 and the final simplex table is T x1 x2 x3 x4 s1 s2 s3 z60042107 x2 1 1 0 2 2 1 0 1 (3) x3 10101101 s3 5 0 0 3 0 2 1 1 Now consider a similar linear programming problem, with modifications as indicated in bold: max x1 +3x2 +4x3 +2x4 (4a) subject to 2x1+ x2+ x3+2x4 2 (4b) 3x1+ x2+2x3+2x4 32 (4c) x1+2x2+4x3+ x4 76 (4d) and still subject to all xi 0 for i {1, 2, 3, 4}. Here, is an arbitrary fixed value in R. For this modified problem, use post-optimal analysis to answer all of the following questions: (a) For what values of R does the basis {x2, x3, s3} give a basic feasible solution? (b) For what values of R does the basis {x2,x3,s3} give an optimal basic feasible solution? In those cases where the basis {x2,x3,s3} gives an optimal basic feasible solution, what is the optimal value of the objective function as a function of ? (c) Find the optimal solution of the modified problem for = 1. ED01/2019 CONTINUED University of Durham Copyright ED01/2019 CONTINUED Page number Exam code 6 of 7 MATH3141-WE01 9. The newly developed tutorial centre in Durhams mathematical sciences department consists of a sequence of service periods. A student that completes the service in a period departs at the end of that period. Just at the end of each service period, a new student arrives with probability 1/2. The next service period starts soon after. If there are already two students in the centre, the newly arriving student gets frustrated, leaving immediately and vows never to return again. However, if there is one student or less already in the centre, the newly arriving student will join the service. At most one new student who can join the service arrives per period and at most one student can be served in a period. The manager of the tutorial centre has two service configurations available: deploy a postgraduate fellow, labelled a PG configuration, or deploy a teaching fellow, labelled a TF configuration. The manager decides which configuration to use at the beginning of each period (so service completions precede arrivals which precede decisions). The PG configuration costs 3 units and the student being served during the period will complete the service and leave the centre at the end of the period with probability 3/5 (otherwise, the student remains in the system). The TF config- uration costs 9 units and the student being served during that period will complete and leave the tutorial centre with probability 4/5. The tutorial centre earns a credit of 50 units each time a student leaves the service. (a) (b) Formulate the problem of choosing the service configuration, period by period, as a Markov decision process. Identify the states and decisions. For each com- bination of states and decisions, find the expected net immediate return (sub- tracting any running costs) earned during that period. The manager is currently implementing policy A1, where the PG configuration is used in all states. Perform two complete steps of the policy improvement algorithm to find an improved policy for the long-run expected reward per unit time. After two steps of the policy improvement algorithm, are you able to conclude whether you have reached the optimal policy or not? University of Durham Copyright Page number Exam code 7 of 7 MATH3141-WE01 10. Three investment schemes (A, B, and C) accept investments in multiples of 3000. Schemes A and B mature after one year, and generate returns distributed as follows: annual return on 3000 investment probability A 0 0.2 5000 0.8 B 3000 0.4 4000 0.3 5000 0.3 Tabulated returns include the original investment so that, for example, 0 means loss of the entire investment and investment B has a 40% chance of breaking even over one year. Scheme C matures after two years, generating a guaranteed return as follows: two-year return on 3000 investment probability C 5000 1.0 ED01/2019 END You have 3000 to invest at the start of a period of N years. At the end of a year that does not bring the investment period to a close, any return from that year, together with any amount not invested that year, is available to invest for the next year. Investment may be split between the schemes as desired (provided the rule that investments must be in units of 3000 is respected). Use stochastic dynamic programming to find the optimal (in terms of expected total profit) investment strategy for the first year of the given investment period in the case where (a) N = 1; (b) N = 2; (c) N = 3. Hint: Although you can re-use many calculations from one part of this question to the next, be careful to take full account of money left over from previous years, particularly in answering part (c). University of Durham Copyright