MAT021 Foundations of Operational Research and Analytics
Foundations of Operational Research and Analytics
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Module Code: MAT021
Examination Paper Title: Foundations of Operational Research and Analytics
Duration: 3 hours (from the release of the paper to the submission deadline for solu-
tions).
Please read the following information carefully:
Structure of Examination Paper:
• There are 5 pages including this page.
• There are FOUR questions in total.
• There are no appendices.
• The maximum mark for the examination paper is 75 and the mark obtainable for a
question or part of a question is shown in brackets alongside the question.
Instructions for completing the examination:
• Answer THREE questions.
- 1 - Please turn over
MAT021/21
1. (a) Solve the following linear programming problem by using the Simplex Method.
Provide all the details and explanations.
maximise z = 2x1 + 5x2 + 3x3
subject to: x1 + 2x2 ≤ 28
2x1 + 4x3 ≤ 16
x2 + x3 ≤ 12
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Explicitly provide the optimal solution for the problem and the corresponding
objective function value. [ 7 marks ]
(b) Write the Dual problem for the problem in part (a). [ 3 marks ]
(c) Write the Dual problem from part (b) in standard form, with non-negative right-
hand side constants in the constraints. [ 2 marks ]
(d) Suppose you need to find a feasible basic solution for the problem in part (c) by
using the Two-Phase Method. Write the problem you would have to solve in the
first phase of the Two-Phase Method. (Do not solve the problem.) [ 3 marks ]
(e) Provide the solution of the Dual problem in part (b) by analysing the solution of
the problem in part (a). [ 2 marks ]
(f) A business executive has the option of investing money in two plans. Plan A
guarantees that each pound invested will earn 70 pence in one year, and plan B
guarantees that each pound invested will earn £2.00 in two years. Plan A al-
lows yearly investments, while in plan B, only investments for periods that are
multiples of two years are allowed. How should the executive invest £100,000 to
maximise the earnings at the end of three years? Assume all the intermediate
earnings are re-invested. Formulate this problem as a linear programming prob-
lem. (Do not solve the problem.) [ 8 marks ]
- 2 -
MAT021/21
2. (a) A company is taking bids on four construction jobs. Three people have placed
bids on the jobs. Their bids (in thousands of pounds) are given in the table below,
where a * indicates that the person did not bid on the given job:
Person/Job 1 2 3 4
1 50 46 42 40
2 51 48 44 *
3 * 47 45 45
Person 1 can do only one job, but persons 2 and 3 can each do as many as two
jobs. Formulate an LP/IP problem to minimise the cost of assigning persons to
jobs. (Do not solve the problem.) [8 marks]
(b) Using the Branch-and-Bounds method, find all the solutions to the following
instance of the Knapsack Problem:
maximise 23x1 + 19x2 + 28x3 + 14x4 + 44x5
subject to 8x1 + 7x2 + 11x3 + 6x4 + 19x5 ≤ 25
x1, x2, x3, x4, x5 = 0 or 1
Use the ratio choice method to obtain solutions to the LP relaxations of the
corresponding problems. Provide all the details and explanation, and draw a
Branch-and-Bounds tree of sub-problems for the solution process. [17 marks]
- 3 - Please turn over
MAT021/21
3. (a) Consider the travelling salesman problem.
i. Explain how you would produce a solution using a greedy algorithm.
[2 marks]
ii. Explain how you would produce a solution using random descent. [4 marks]
iii. Explain how you would produce a solution using tabu search. [4 marks]
(b) 4 towns are linked by the following road network.
Towns A and B are linked by a road of length 3.
Towns A and C are linked by a road of length 4.
Towns B and D are linked by a road of length 6
Towns C and D are linked by a road of length 4.
The council wish to locate a hospital along the road connecting B and D so
that the maximum distance anyone has to travel from any of the four towns is
minimised. Use Hakimi’s Algorithm to find the optimal location. [15 marks]
- 4 -
MAT021/21
4. (a) A manufacturing company has 4 jobs A,B,C,D that need to be each completed
in turn on Machine 1 followed by Machine 2. The times each job takes on each
machine are as follows:
Job Time on Machine 1 Time on Machine 2
A 7 12
B 12 9
C 12 10
D 14 13
Use Johnsons Algorithm to find the sequence that minimises the makespan. Find
the makespan of your solution by drawing a suitable Gantt chart. [7 marks]
(b) A company that make roadsweepers is planning its production for the next four
months. Although it knows the demand for its product in months 3 and 4, it is
uncertain about the demand for the first two months. It believes the demand for
its product is as follows:
Month Demand
1 30% probability of 1, 70% probability of 2
2 60% probability of 2, 40% probability of 3
3 5
4 2
The company can make up to 4 roadsweepers per month and it costs £5, 000 to
make one roadsweeper, £9, 500 to make two roadsweepers, £13, 000 to make three
roadsweepers and £16, 000 to make four roadsweepers. Storing a roadsweeper
costs £1, 000 per month and they can store up to three roadsweepers at any time.
Given the company starts this period with zero roadsweepers in stock and wishes
to end the four months with zero in stock, use dynamic programming to find the
optimal production plan. Assume that the company will not allow the possibility
of not being able to meet the demand or having more than three roadsweepers in
stock. [18 marks]