Optimisation Algorithms in Operational Research Worksheet

STAT0025: In-Course AssessmentPage 1
STAT0025: In-Course Assessment, 2022–23
Regulations
• The deadline for the assessment is Tuesday 22 November 2022 at 12:00, UK
time. You should submit the assessment on the STAT0025 Moodle page.
• There are three questions. Answer all questions. Question 1 is worth 19 marks.
Question 2 is worth 14 marks. Question 3 is worth 7 marks.
• You may refer to your notes and other resources. You may use a calculator or a
computer for routine calculations, including matrix manipulations. You may not
use linear programming software.
• Late submission will incur a penalty unless there are extenuating circumstances
supported by appropriate documentation. Penalties are set out in the latest editions of the Statistical Science Department student handbooks, available from the
departmental web pages.
• Failure to submit this in-course assessment will mean that your overall examination
mark is recorded as “non-complete”, i.e., you will not obtain a pass for the course.
• Your work will be marked and returned to you for feedback. The grade you receive
is a provisional grade, and will be confirmed at the Statistics Examiners’ Meeting.
Formatting your solutions for submission
• You should submit ONE document that contains your solutions for all questions/partquestions. Please follow UCL’s guidance on combining text and photographed/scanned
work, available here: https://www.ucl.ac.uk/news/2020/apr/seven-simple-stepssubmit-handwritten-answers-moodle-exams-or-assessments
• In handwritten solutions (on paper or via tablet) please use blue or black pen.
Submitting your document
• Only upload ONE file that contains ALL your work.
• You will be allowed to submit only once. Ensure that you submit the correct
document!
• It is safer to submit a PDF document as it will be stable in terms of formatting
across platforms.
• Name your file using your student number and the course code. For example, if your
student number is 18002119 then you should name your file 18002119-STAT0025.
This should also be input as the submission title on Moodle.
Turn Over
STAT0025: In-Course Assessment
Page 2
• Please write your student number on the first page of your submission. Do not write
your name on your submission.
Plagiarism and collusion
• You must work alone. You are encouraged to read the Department of Statistical
Science’s advice on collusion and plagiarism, which you can find at
https://www.ucl.ac.uk/statistics/sites/statistics/files/shbpc.pdf
• If there is any doubt as to whether the solutions you submit are entirely your own
work, this will be reported to the Department of Statistical Science, who may take
further action.
Turn Over
STAT0025: In-Course Assessment
Page 3
1. A company makes baby food out of applesauce, carrot puree, and crushed peas.
They sell product 1, First Taste, and product 2, Second Choice. Each product is
made by mixing together the component foods in different proportions, but there
is some flexibility in exactly how much of each component is in each product. The
allowable proportions, and the price for which each product is sold for (in £ per
litre), are given in this table:
Product
Apple
1: First Taste
2: Second Choice
Carrot
Pea
Sell price (£/L)
38 – 43 % 48 – 52 % 9 – 11 %
18 – 20 % 10 – 13 % 69 – 72 %
9
12
Each component has a cost to purchase it, and a maximum amount that is available
to the company (i.e., an upper bound). These costs (in £ per litre) and upper
bounds (in litres) are given in this table:
Component
Cost (£/L)
Upper bound (L)
Apple
Carrot
Pea
1
4
5
1000
800
900
(a) With the goal of maximising the profit (the difference between total sales
revenue and cost of components), write down a linear programming problem
(LPP) to determine the optimal composition of each product (in % of each
component), and how much of each product to produce (in litres). Explain
your objective function and constraints. Do not attempt to solve the LPP.
(Hint: if you struggle to find linear constraints, you may need to rethink your
choice of control variables.)
[10 marks]
In addition to mixing the components, the components themselves must be transported from their manufacture sites to the mixing sites, and in the problem above
the cost of transportation has been neglected. They are transported via two intermediate warehouses, and the road network between component manufacture sites,
warehouses and product mixing sites looks like this:
Turn Over
STAT0025: In-Course Assessment
A
Page 4
3
2
C
W
2
3
1
2
1
3
V
4
2
P
In this diagram, the vertices A, C and P are the component manufacture sites of
applesauce, carrot puree and crushed peas, respectively. The vertices W and V
are two intermediate warehouses through which the components must pass. The
vertices 1 and 2 are the product mixing sites at which products 1 and 2, respectively,
are produced. The annotation on each edge in the diagram is the cost (in £ per
litre) of transporting any component along that edge.
(b) With the goal of maximising profit (the difference between total sales revenue
and the cost of both components and transportation), write down a linear
programming problem to determine the optimal composition of each product
(in % of each component), how much of each product to manufacture (in litres)
and how much of each component to transport along each edge of the network
(in litres). Explain your objective function and constraints. Do not attempt
to solve the LPP.
[9 marks]
2. (a) A company makes products 1 and 2, which consume resources R and S. They
represent the problem of profit maximisation subject to these resource constraints (among other constraints) using the following linear programming
problem:
Maximise z = 8×1 + 2×2
subject to x1 + 5×2 ≤ 25
(resource R)
−x1 + 3×2 ≥ 0
3×1 + x2 ≤ 10
(resource S)
x1 + 2×2 ≤ 12
x1 , x2 ≥ 0.
(1)
(2)
(3)
(4)
(5)
Solve this problem using the graphical method (not the graphical naive method.)
[6 marks]
Turn Over
STAT0025: In-Course Assessment
Page 5
(b) There is a glut in resource S which means that the constraint (3) changes. The
company is not sure exactly how much additional resource S will be available,
so they replace this constraint with the inequality
3×1 + x2 ≤ 10 + ∆
(6)
where ∆ ≥ 0 is some small value; the company wishes to determine the sensitivity of the problem to the value of ∆.
The glut in resource S also causes the profit obtained from product 1 to change,
because a competing company is able to sell their own product for less, decreasing demand. The result is that the objective function changes to
1

z = 8 − ∆ x1 + 2×2 .
5
Determine how the optimal value of the LPP changes (as a function of ∆),
and for what range of ∆ your answer is valid.
[8 marks]
3. A university administrator needs to decide how many students to assign on each of
four optional modules. They denote by xi the number of students on module i (for
i = 1, 2, 3, 4). They decide that they can attempt to find an allocation of students
to modules by finding a solution of the problem
Maximise z = 0
subject to 4×1 + 8×2 + 6×3 + 2×4 ≥ 1200
2×1 + 5×2 + 3×3 + 6×4 ≥ 800
x1 + x2 ≤ 200
x3 + x4 ≤ 150
x1 , x2 , x3 , x4 ≥ 0,
x1 , x2 , x3 , x4 ∈ Z.
(7)
(8)
(9)
(10)
(11)
(12)
Constraints (7) and (8) reflect the minimum number of credit-hours that must be
offered by two departments, and constraints (9) and (10) are required by a bound
on the workload of two lecturers.
With the help of (a variant of) the simplex algorithm from this course, decide
whether or not there is any assignment of students to modules which will satisfy
constraints (7) to (12). If there is such an assignment, specify it (i.e., give explicitly
a valid choice of x1 , x2 , x3 , x4 .)
[7 marks]
End of Paper