EPM945 OPTIMIZATION AND DECISION MAKING –
COURSEWORK
Assignment set on Thursday, 24 November 2016.
Completed assignment, to be handed in by
Thursday, 19 January 2016 at the School O�ce by 4.00 pm.
Late submissions will be penalised.
Answer all questions. Show all necessary working.
Question 1
Use the simplex method to solve the following simplex problems.
a) Maximise 2×1 + 3×2 + 2×3 subject to
3×1 + 2×2 + x3 6,
x1 + x2 + x3 4,
x1 + 3×2 + 3×3 10
x1, x2, x3 � 0.
b) Maximise �5×1 � x2 � 3×3 subject to
x1 + 7×2 1,
2×1 + 4×2 � x3 0,
�3×1 + x2 � 2×3 �2
x1, x2, x3 � 0.
c) Maximise 5×1 + x2 + 4×3 + 3×4 subject to
x1 + x2 + x3 + x4 6,
�x1 + 2×2 + 4×4 = 1,
x1 + 3×3 = 6
x3 unrestricted, x1, x2, x4 � 0.
(15 marks)
Question 2
Consider the primal linear programming problem below.
Maximise 4×1 + 4×2 + 5×3,
subject to
3×1 + 8×2 + 6×3 10,
8×1 + 3×2 + 6×3 12,
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.
(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 300, 200 and 400 cars respectively.
A, B and C require 200, 250 abd 350 cars respectively.
The aim is to minimise the total cost of transporting the cars.
A B C
1 9 18 8
2 8 12 4
3 10 16 6
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 77 81 82 82 84
2 79 71 71 90 81
3 88 84 83 94 79
4 87 76 74 75 82
5 77 83 78 92 78
Each of the five candidates must be assigned exactly one job. Find the optimal job
assignments.
(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 port-
folio 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 co-
variances are as follows:
µ1 = 0.07, µ2 = 0.09, µ3 = 0.10, �
2
1 = 0.1, �
2
2 = 0.3, �
2
3 = 0.6, �12 = �0.1, �13 = 0.1
and �23 = 0.2.
Find the optimal portfolio (i.e. the one with the minimum variance) for the expected
rate of return of 0.09.
d) Now suppose that the target rate of return is reduced to 0.08. Find the optimal
portfolio in this case.
(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 proba-
bilities 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 100000 kegs, but it is felt by some managers that the stock
sholud be increased.
The Operations Manager has propoased that 8000 new kegs be ordered immediately.
The Accountant was not convinced. Kegs cost £60 each, so this would lead to an
expenditure of £480000. They would be usable next year, but assuming 5% interest
on capital, buying now rather than waiting until next year would cost £24000.
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.8 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.5, they will increase by a lower amount with
probability 0.4, and there will be no increase with probability 0.1.
The Data Processing Manager suggests three possible strategies; buying 0, 4000 or
8000 kegs immediately. The associated change in profit from these three strategies
were estimated, based upon the assumption that with a 10% sales increase 8000
extra kegs will be used (if available), and for a lower increase 4000 extra kegs will be
used (if available), with an associated profit of £7 per keg. These are summarised
in Table 1.
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.
Number of kegs Increase on last year
purchased None Up to 10 % Over 10 %
0 0 0 0
4000 -12000 16000 16000
8000 -24000 4000 32000
Table 1: Predicted changes in profit (in £) for combinations of di↵erent immediate
purchasing strategies and sales increases.
Actual increase Predicted increase Total months
over the previous year None Up to 10 % Over 10 %
� 10% 2 6 15 23
< 10% 7 21 7 35
0 14 7 5 26
Table 2: Sales over the last 84 months.
(24 marks)
vagrant