Examination Paper for STAT0025 Page 1
STAT0025: Optimisation Algorithms in Operational
Research
2020/21, main exam session
• Answer ALL questions.
• You have three hours to complete this paper.
• After the three hours has elapsed, you have one additional hour to upload your solutions.
• You may submit only one answer to each question.
• The relative weights attached to each question are: A1 (20), A2 (20), B1 (20), B2 (20),
B3 (20).
• The numbers in square brackets indicate the relative weights attached to each part
question.
• Marks are awarded not only for the final result but also for the clarity of your answer.
Administrative details
• This is an open-book exam. You may use your course materials to answer questions.
• You may use a calculator. You may use a computer for routine calculations such as
matrix inverses. You may not use linear programming software.
• You may not contact the course lecturer with any questions, even if you want
to clarify something or report an error on the paper. If you have any doubts about a
question, make a note in your answer explaining the assumptions that you are making
in answering it. You should also fill out the exam paper query form online.
Formatting your solutions for submission
• You should submit ONE pdf document that contains your solutions for all questions/part-
questions. Please follow UCL’s guidance on combining text and photographed/scanned
work: https://egon.stats.ucl.ac.uk/slink/b7fa4615
• Make sure that your handwritten solutions are clear and are readable in the document
you submit.
Turn Over
Examination Paper for STAT0025 Page 2
Plagiarism and collusion
• You must work alone. In particular, any discussion of the paper with anyone
else is not acceptable. You are encouraged to read the Department of Statistical
Science’s advice on collusion and plagiarism: https://www.ucl.ac.uk/statistics/
sites/statistics/files/shbpc.pdf
• Parts of your submission will be screened via Turnitin to check for plagiarism and
collusion.
• If there is any doubt as to whether the solutions you submit are entirely your own work
you may be required to participate in an investigatory viva to establish authorship.
Continued
Examination Paper for STAT0025 Page 3
Section A
A1 (a) Consider a generic linear programming problem in standard form:
Maximise z = cTx subject to Ax ≤ b, x ≥ 0.
Regard this as the primal problem. Write down its dual, and convert it to standard
form. Maintain matrix notation throughout. [3]
(b) Is the following statement true or false? Justify your answer carefully. ‘The ranges
of validity of the shadow prices in the dual problem are related to the tolerance
intervals of the objective function coefficients in the primal problem.’ [3]
(c) Consider the following linear programming problem:
Maximise z = 2x1 + 6x2 − x3
subject to x1 + x2 + x3 ≤ 5 (1)
2x1 − x2 + 3x3 ≤ 2 (2)
−x1 + 6x2 + x3 ≤ 4 (3)
x1, x2, x3 ≥ 0. (4)
Regard this as the primal problem. The final tableau in the simplex algorithm
applied to the dual problem is
y1 y2 y3 y4 y5 y6 Sol
y3 3/11 0 1 −1/11 −2/11 0 14/11
y2 7/11 1 0 −6/11 −1/11 0 18/11
y6 13/11 0 0 −19/11 −5/11 1 79/11
−g 29/11 0 0 16/11 10/11 0 −92/11
(Note the objective function in the tableau is −g.) Using only this tableau, what
can you deduce about the primal problem? Justify your answer. [4]
(d) Consider the following game against nature.
Nature
N1 N2 N3
Player A1 10 10 10
A2 9 20 30
A3 20 5 20
Your beliefs about the state of nature are that N1 will occur with probability 1/4,
N2 with probability 3/8 and N3 with probability 3/8.
Find the optimal action on the basis of the expected value criterion, and its ex-
pected payoff. [4]
(e) The expected value criterion does not correspond to a Nash equilibrium in the
game against nature. Comment on the implications of this. [3]
Turn Over
Examination Paper for STAT0025 Page 4
(f) In the course, we saw the expected value-standard deviation (EVSD) criterion.
Comment on the effect of using the EVSD criterion as a way to distinguish between
actions A1 and A2 in (d), and its suitability in this example. (You might like to
set K = 2 as the parameter to the EVSD criterion.) [3]
Continued
Examination Paper for STAT0025 Page 5
A2 (a) In the following network, vertices are labelled with letters, and edges are labelled
with numbers. The label on each edge represents the costs of travelling along that
edge. For the two vertices in stage 3, there are terminal costs associated with
arriving at that vertex.
A
B
C
D
E
F
G
H
I
2
5
1
9
1
4
3
2
5
10
3
6
5
4
7
3
Stage 0 Stage 1 Stage 2 Stage 3 Terminal
costs
Find the path from stage 0 to stage 3 which attains the minimium cost across all
possible paths, taking into account the terminal costs. (If you decide to annotate
the network, you must define your annotations.) [6]
(b) Consider an optimal stopping problem with the following setup:
– There are two states, 1 and 2, in each stage.
– When transitioning to the next stage, the probability of remaining in the same
state is 1/5, and the probability of changing to the other state is 4/5.
– The cost of continuing is c(1) = 5 in state 1 and c(2) = 10 in state 2.
– The terminal reward is r(0)(1) = 40 in state 1 and r(0)(2) = 20 in state 2.
– The reward for stopping early is r(1) = r(2) = 12 in both states.
Find the optimal policy with two stages to go. [6]
(c) What features of dynamic programming problems make it possible to solve them
without listing every path through the problem? How do we preserve this solution
method in the context of Markov dynamic programming problems? [3]
Turn Over
Examination Paper for STAT0025 Page 6
(d) Solve the two-player, zero-sum game with the following payoff matrix:
Player B
B1 B2 B3 B4
Player A A1 2 0 −1 −1
A2 5 −3 −1 −2
A3 4 1 1 2
A4 −1 3 0 5
[5]
Continued
Examination Paper for STAT0025 Page 7
Section B
B1 Consider the following linear programming problem:
Maximise z = x1 + 4x2
subject to − x1 + 2x2 ≤ 6 (5)
x1 + 2x2 ≤ 8 (6)
2x1 − x2 ≤ 1 (7)
x1, x2 ≥ 0. (8)
(a) Draw the feasible region. Label all the basic solutions, and indicate, for each one,
which are the basic variables. (Use our standard notation for slack variables. You
do not have to find the values of the basic variables.) [4]
(b) Solve the problem using the simplex algorithm. [8]
(c) Using your solutions to the previous parts, answer the following questions about
the simplex algorithm:
(i) When entering a variable, why do we choose the column with the most negative
z-row entry?
In terms of your diagram of the feasible region, what is the meaning of the
z-row entries? [4]
(ii) When exiting a variable, why do we choose the row with the smallest non-
negative θ-ratio?
In terms of your diagram of the feasible region, what is the geometric meaning
of the θ-ratio (when this is non-negative)? [4]
Note: If you were unable to answer part (a) or (b), you may answer part (c) by
referring to any example from the course.
Turn Over
Examination Paper for STAT0025 Page 8
B2 You are running an import-export company. Each year, you must decide whether or
not to buy insurance.
Your revenue each year is £300. Your costs, due to loss of shipments, are random.
Each year, these costs are £100 with probability 5/12, £180 with probability 5/12, or
£360 with probability 1/6, independently of other years.
If you buy insurance, you must pay the insurer a premium of £80. In return, the
insurer will pay the portion of your costs above the excess of £200. For example, if
your costs are £100, your portion is £100 and the insurer’s portion is £0; if your costs
are £360, your portion is £200 and the insurer’s portion is £160.
If you do not buy insurance, you must pay all your costs.
Your profit each year is your revenue, minus the premium (if you buy insurance), minus
your portion of your costs due to loss of shipments.
Regard the company as having three financial positions: Good, Shaky and Bankrupt.
If the company is in a Good position, then they remain in a Good position next year
if the profit is positive, and move to a Shaky position if the profit is negative. If the
company is in a Shaky position, then they move to a Good position if the profit is
greater than £100, move to a Shaky position if the profit is between £0 and £100, and
move to a Bankrupt position if the profit is negative. If the comany is in a Bankrupt
position, then they remain in that position in all future years.
You run the company for the next N = 2 years. You get to keep the profit each year as a
reward. If, after that time, the company is in aGood position, you gain an extra reward
of £100; if it is in a Shaky position, you gain no extra reward; and if it is Bankrupt you
have lost your job, which we will treat as a penalty of £1000.
On the day you take over the company, it is in a Shaky position.
(a) Formulate this as a Markov dynamic programming problem with actions, with the
goal of maximising your expected reward. Make clear your choice of stages, states,
transition and terminal rewards and transition probabilities for each action. [8]
(b) Solve the problem, showing all necessary steps. [6]
(c) Under the optimal policy determined in (b), what is the probability that the com-
pany ends up in a Good position? [3]
(d) Suppose that, instead, you consider only the probability of bankruptcy, and
want to minimise this. How would you adapt the method of Markov dynamic
programming in order to determine the optimal actions to take? You do not need
to solve the problem, but you do need to describe it precisely.
(Give an answer that can be applied in general to problems of this type, rather
than one specific to the revenue, costs and probabilities in this specific problem.)
[3]
Continued
Examination Paper for STAT0025 Page 9
B3 You play a game with a friend. You hold three cards: a red 1, a black 3, and a joker.
Your friend holds two cards: a black 1 and a red 2.
The game works as follows. Suppose you both play number cards. If the colours are
the same, your friend pays you the sum of the two numbers. If the colours are different,
you pay your friend the sum of the numbers. (For example, if you play red 1 and your
friend plays black 1, then you pay £2 to your friend; if you play red 1 and your friend
plays red 2, then your friend pays you £3.)
Suppose that you play the joker. Then, if your friend plays a black card, they pay you
a jackpot of size J > 0; if your friend plays a red card, you pay them the jackpot of
size J .
(a) Formulate this as a two-player, zero-sum game, in which you are player A, and the
payoff is the payment you get. Write down its payoff matrix. [3]
(b) Let J = 3. Solve the game using the graphical method. [6]
(c) Describe in detail how the solution of the game depends on the value of J , giving
the optimal actions and payoff associated with every possible value of J > 0,
including non-integer values, [8]
(d) What happens to the value of the game as J →∞? Describe how your approach
to playing the game might change as J gets large. [3]
End of Paper