OPTIMIZATION AND DECISION MAKING

            Question 1 Use the simplex method to solve the following simplex problems. a) Maximise −5x1 − x2 − 3x3 subject to −x1 + 4x2 + 2x3 ≤ 0, 7x2 + x3 ≤ 1, −2x1 + x2 − 3x3 ≤ −2 x1, x2, x3 ≥ 0. b) Maximise 2x1 + 3x2 + 2x3 subject to 3x1 + x2 + 2x3 ≤ 6, x1 + x2 + x3 ≤ 4, 2x1 + 6x2 + 6x3 ≤ 20 x1, x2, x3 ≥ 0. c) Maximise 3x1 + x2 + 4x3 + 5x4 subject to x1 + x2 + x3 + x4 ≤ 6, 2x2 − x3 + 4x4 = 1, 3x1 + x3 = 6 x1 unrestricted, x2, x3, x4 ≥ 0. (15 marks) Question 2 Consider the primal linear programming problem below. Maximise 8x1 + 10x2 + 8x3, subject to 8x1 + 6x2 + 3x3 ≤ 12, 6x1 + 12x2 + 16x3 ≤ 20, x1, x2, x3 ≥ 0. a) Construct the dual problem and solve it graphically. b) Determine a solution to the primal problem, stating clearly any results that you use (do not use the simplex algorithm). (12 marks) 1 2 Question 3 Three car showrooms A, B and C are supplied by cars from three ports, 1, 2 and 3. The table below gives the cost, in pounds, of transporting a car from each port to each showroom. Ports 1, 2 and 3 have stocks of 600, 400 and 800 cars respectively. A, B and C require 400, 500 abd 700 cars respectively. The aim is to minimise the total cost of transporting the cars. A B C 1 10 9 3 2 14 11 5 3 16 10 7 a) Formulate, but do not solve, the problem in the form of a linear program. b) Now write the problem in the form of a transportation array, explaining how you deal with the fact that the total demand and the total supply are not equal. c) Find the optimal transportation solution. (15 marks) Question 4 Five candidates for five jobs are given an aptitude test for each job. The scores for the five candidates and the five jobs are given as follows; Cand/Job 1 2 3 4 5 1 69 68 69 64 71 2 77 58 58 66 68 3 62 63 61 74 69 4 81 71 70 75 66 5 79 70 65 64 65 a) Each of the five candidates must be assigned exactly one job. Find the optimal job assignments. b) How would this assignment change if candidate 2 was pre-assigned to do job 2? (10 marks) 3 Question 5 Suppose that you have to choose an optimal portfolio from a list of n stocks. Stock i has expected revenue rate µi with variance σ 2 i for i = 1, . . . , n, and the covariance of the revenues of stocks i and j is given by σij for i 6= j, i, j = 1, . . . , n. The proportion of stock i in the portfolio is denoted by xi . a) Showing your working carefully, show that the expected revenue from the portfolio is Pn i=1 xiµi , and find an expression for the variance of the portfolio revenue, again showing your working carefully. b) Still for a general number of n stocks, formulate this as an optimization problem using Lagrange multipliers, and find a set of linear equations for the optimal values of the xis. You do not need to solve the problem at this stage. c) Now consider a problem with three stocks, where the means, variances and covariances are as follows: µ1 = 0.06, µ2 = 0.04, µ3 = 0.07, σ2 1 = 0.3, σ2 2 = 0.1, σ2 3 = 0.6, σ12 = −0.1, σ13 = 0.2 and σ23 = 0.1. Find the optimal portfolio (i.e. the one with the minimum variance) for the expected rate of return of 0.06. d) Now suppose that the target rate of return is increased to 0.065. Find the optimal portfolio in this case and comment. (24 marks) Question 6 Read the following case study based on the Applegold Cider Company. You should then apply decision analysis to the problem facing Applegold. This will involve: a) Formulating the problem as a decision tree; b) using Bayesian analysis to update prior probabilities and find the correct probabilities in the tree; c) discuss the strengths and limitations of your analysis. Applegold is a major cider producer, producing draught cider for pubs and clubs, as well as bottles and cans, which has recently seen production and the number of outlets selling its products increase significantly. The growth in draught cider has created some problems for the company’s managers. In particular, there is concern that when sales reach their peak in August, there might not be enough kegs (steel re-usable cider containers) available to meet demand. Applegold own about 200000 kegs, but it is felt by some managers that the stock sholud be increased. The Operations Manager has propoased that 16000 new kegs be ordered immediately. The Accountant is not convinced. Kegs cost £90 each, so this would lead to an expenditure of £1440000. They would be usable next year, but assuming 5% interest on capital, buying now rather than waiting would cost £72000. 4 The Sales Manager proposes that the company wait until an accurate long range weather forecast is available for August, since demand depends heavily on the weather, with hot dry months leading to high demand. Such a forecast will be available in July. One problem is that it might be the case that other brewers had bought all of the available kegs by this time and the Operations Manager estimates a probability of 0.7 of getting the kegs if they wait until July. The Sales Manager produces an interim forecast, with no knowledge of the weather, of how good sales are likely to be in August. She estimates that they will be at least 10% higher with probability 0.45, they will increase by a lower amount with probability 0.4, and there will be no increase with probability 0.15. The Data Processing Manager suggests three possible strategies; buying 0, 8000 or 16000 kegs immediately. The associated change in profit from these three strategies were estimated, based upon the assumption that with a 10% sales increase 16000 extra kegs will be used (if available), and for a lower increase 8000 extra kegs will be used (if available), with an associated profit of £10.50 per keg. These are summarised in Table 1. Number of kegs Increase on last year purchased None Up to 10 % Over 10 % 0 0 0 0 8000 -36000 48000 48000 16000 -72000 12000 96000 Table 1: Predicted changes in profit (in £) for combinations of different immediate purchasing strategies and sales increases. The Sales Manager suggests that it might still be better to wait for the weather forecast in July, and run the risk of the kegs not being available. Whether it is best to do so depends upon how accurate the forecasts are. The data in Table 2 give some data on the recent performance of the forecasts. Actual increase Predicted increase Total months over the previous year None Up to 10 % Over 10 % ≥ 10% 2 7 17 26 < 10% 7 25 8 40 0 16 8 6 30 Table 2: Sales over the last 96 months. (24 marks)