EPM945/EPM504
CITY UNIVERSITY
London
Optimization and Decision Making
Linear Programming and Decision Making
2015
Time allowed: 2 hours
Full marks may be obtained for correct answers to
THREE of the FIVE questions.
All necessary working must be shown.
1 Turn over . . .
1. 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 wi.
(a) Show that the expected revenue from the portfolio is
∑n
i=1wiµi, and
find an expression for the variance of the portfolio revenue. [8]
(b) Still for a general number of n stocks, formulate this as an optimiza-
tion problem to minimize the expected variance for a given expected
rate of return using Lagrange multipliers, and find a set of linear
equations for the optimal values of the wis. You do not need to solve
the problem at this stage. [7]
(c) Now consider a problem with three stocks, where the means, vari-
ances and covariances are as follows:
µ1 = 0.07, µ2 = 0.05, µ3 = 0.03, σ
2
1 = 0.5, σ
2
2 = 0.2, σ
2
3 = 0.1, σ12 =
0.2, σ13 = −0.1 and σ23 = 0.1.
Find the optimal portfolio (i.e. the one with the minimum variance)
if the targeted expected rate of return is 0.05. [15]
2. A company manufactures three different sizes of picture frames; Small,
Medium and Large. The production of each picture frame is comprised of
three parts; Construction, Assembly and Packing. The Assembly times for
each pciture frame are one minute for a Small, two minutes for a Medium,
and three minutes for a Large. The Construction times for each frame are
one minute for a Small, four minutes for a Medium, and ten minutes for
a Large. Finally the Packing times for each frame are one minute for a
Small, one minute for a Medium, and one minute for a Large. There are
two workers in the Assembly department, giving a total of 4800 minutes
of labour time per week; three workers in the Construction department,
giving a total of 7200 minutes of labour time per week and one worker
in the Packing department, giving a total of 2400 minutes of labour time
per week. The proft for each picture frame is 4 pounds for a Small, 6
pounds for a Medium and 9 pounds for a Large. The company wish
to maximise their profit, subject to the time constraints specified above,
without changing their staffing levels.
(a) Set up the problem as a linear program. [12]
(b) Solve the problem using the simplex method. [18]
2 Turn over . . .
3. A bus company is considering starting a new bus service in a town. The
town is a tourist destination, and the main business will be over the Sum-
mer, but the company can test the likely demand in the Spring by operat-
ing a Limited service, which will give some idea of what will happen over
the Summer (it will not start a service in the Summer without running
this Limited Spring service). In the Spring, passenger numbers can be
designated either as High (Spring) or Low (Spring). The company esti-
mates that there is a 0.6 chance of High (Spring) passenger numbers.
If passenger numbers in the Spring are low, it will cost the company
£100000, and they will abandon plans of operating any service in the
Summer. If they are high, they will then have enough confidence to run a
service in the Summer. This service can be Limited or Full. The profits
achieved would depend upon the nature and level of passenger numbers,
which we categorize as either High (Summer) or Low (Summer).
If the company opted for a Full service and numbers were high, a £250000
profit would be obtained. If the numbers were low in this case, however,
the company would make a loss of £200000.
If the company decided to go for the Limited service, High passenger
numbers would generate a profit of £150000 and Low numbers would
generate a profit of £50000.
The company estimates that there is a 0.75 chance of High (Summer)
passenger numbers in the Summer if there were High (Spring) numbers in
the Spring.
(a) Construct a decision tree to represent this decision problem. [15]
(b) Assuming that the company’s objective is to maximize its expected
profit, determine the policy that it should adopt. [5]
(c) The company’s estimated probability of High (Spring) numbers may
not be correct. Assuming that all other problem elements remain the
same, determine how low this probability would have to be before the
option of not running any service should be chosen. [5]
(d) Before the final decision is taken a new Finance Director joins the
company, who insists that a utility theory approach is taken to the
problem, and who gives the utilities shown below for the sums of
money involved in the decision. What implications does this have for
the policy that you found from b) and why? [5]
Value (£ million) -200000 -100000 0 50000 150000 250000
Utility 0 0.4 0.7 0.8 0.95 1
3 Turn over . . .
4. Consider the primal linear program below.
Maximise x1 + 2×2 + 3×3,
subject to
x1 + x2 + 6×3 ≤ 12,
x1 + 3×2 + x3 ≤ 9,
x1, x2, x3 ≥ 0.
(a) Construct the dual problem and solve it graphically. [12]
(b) Determine a solution to the primal problem, stating clearly any re-
sults that you use. [12]
(c) Now suppose that 9 replaces 12 in the first constraint in the primal
problem, i.e. we have x1 + x2 + 6×3 ≤ 9. Find the solution to this
new problem. [6]
5. Containers arrive at four different ports, and are distributed to warehouses
in three different cities.
Ports A, B, C and D have received 8, 12, 14 and 6 containers respectively.
Warehouses 1, 2 and 3 require the contents of 10, 10 and 20 containers
respectively.
The transportation costs (in pounds) of supplying one container from a
given port to a given city are given in the following table. The aim is to
minimise the total cost of transporting the containers.
1 2 3
A 170 160 200
B 130 220 220
C 110 180 190
D 160 150 230
(a) Formulate, but do not solve, the problem as a linear program. [7]
(b) Now write the problem in the form of a transportation array and
hence find the optimal transportation solution. [16]
(c) How would the solution to the above problem change if the cost of
transportation from port B to depot 1 rose to 150? [7]
Internal Examiner: Professor M. Broom
External Examiners: Dr E.J. Collins
Dr L. Jackson
4