MAT021/20
Solutions
1 (a) Betty plans to invest a total of £17, 000 in mutual funds, certificates of deposit,
and a high yield savings account. She doesn’t want to invest more in mutual
funds than the sum of her certificates of deposit and savings because of the risk
involved in mutual funds. She also wants the amount in savings to be at least
half the amount in certificates of deposit. Her expected returns are 8.5% on the
mutual funds, 5% on the certificates of deposit, and 3.7% on savings. How much
money should Betty invest in each area in order to have the largest return on her
investments? Formulate this as a linear programming problem, clearly describing
your decision variables, objective function, and constraints. Do not solve the LP
problem. [ 9 marks ]
Model Answer: (Class notes/exercise-practice questions/labs) Let x1 be the
amount invested in mutual funds, x2 the amount in certificates of deposit, and x3
the amount in savings. Then the problem can be written as an LP problem as
follows:
maximise z = 0.085x1 + 0.05x2 + 0.037x3
subject to: x1 + x2 + x3 = 17, 000
x1 − x2 − x3 ≤ 0
−x2 + 2x3 ≥ 0
x1, x2, x3 ≥ 0
(b) Solve the following linear programming problem by using the Dual Simplex Method:
minimise z = 2x1 + 3x2 + 3x3
subject to: x1 − 2x2 ≥ −8
2x2 + x3 ≥ 15
2x1 − x2 + x3 ≤ 25
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Clearly provide the optimal solution for the problem and the corresponding ob-
jective function value. [ 8 marks ]
- 2 -
MAT021/20
Model Answer:
(Class notes/exercise-practice questions)
The initial simplex tableau is:
x1 x2 x3 s1 s2 s3 Solution
2 3 3 0 0 0 0
-1 2 0 1 0 0 8
0 −2∗ -1 0 1 0 -15
2 -1 1 0 0 1 25
It’s infeasible. The leaving variable is s2, and the entering variable is x2 (resp.,
the work column): the ratios/quotients are Qx2 = | 3−2 | and Qx3 = | 3−1 |. Since
Qx2 < Qx3 , the second column is an active column, and the pivot causes x2 to
enter the basis and s2 to leave the basis:
x1 x2 x3 s1 s2 s3 Solution
2 0 3/2 0 3/2 0 -22.5
-1 0 −1∗ 1 1 0 -7
0 1 1/2 0 -1/2 0 7.5
2 0 1.5 0 -1/2 1 32.5
The pivot will cause x3 to enter the basis and s1 to leave the basis:
x1 x2 x3 s1 s2 s3 Solution
1/2 0 0 3/2 3 0 -33
1 0 1 -1 -1 0 7
-1/2 1 0 1/2 0 0 4
1/2 0 0 1.5 1 1 22
This is the final simplex tableau for the problem – the optimal solution is x1 = 0,
x2 = 4, x3 = 7, and z = 33.
(c) The solution to the linear programming problem
maximise z = 5x1 + 8x2
subject to: x1 + x2 ≤ 6
5x1 + 9x2 ≤ 45
x1, x2 ≥ 0
is
x1 x2 s1 s2 Solution
0 0 5/4 3/4 165/4
1 0 9/4 -1/4 9/4
0 1 -5/4 1/4 15/4
.
(i) Perform sensitivity analysis on the coefficient of decision variable x2 in the
objective function. [3 marks]
- 3 -
MAT021/20
Model Answer: (using the formula and explanations from the lecture notes)
5 ≤ t ≤ 9
(ii) Find the solution to the following linear programming problem, without re-
solving it from scratch: [5 marks]
maximise z = 5x1 + 8x2 + 2x3
subject to: x1 + x2 + x3 ≤ 6
5x1 + 9x2 + 2x3 ≤ 45
x1, x2, x3 ≥ 0.
Model Answer: (using the pre-multiplication matrix, formula and explana-
tions from the lecture notes)
x1 x2 x3 s1 s2 Solution
0 0 3/4 5/4 3/4 165/4
1 0 7/4 9/4 -1/4 9/4
0 1 -3/4 -5/4 1/4 15/4
.
- 4 -
MAT021/20
2 (a) The Ayatola Oil Company controls two oil fields. Field 1 can produce up to 40
million barrels of oil per day, and field 2 can produce up to 50 million barrels of oil
per day. Ayatola sells oil to two countries, England and Japan. The company’s
profit per barrel of shipping oil from each of the fields is shown in the following
table:
From\To England Japan
Field 1 £1.5 £2.5
Field 2 £2 £3
Each day, England is willing to buy 40 million barrels, and Japan is willing to
buy 30 million barrels. Formulate a balanced transportation problem to maximise
Ayatola’s profits. Do not solve the problem. [10 marks]
Model Answer: (Class notes/labs) In this transportation problem, we have the
total demand equal to 70 million barrels per day, and the total supply is equal to
90 million barrels per day, i.e. the total supply exceeds the total demand. There-
fore, we need to introduce a dummy country with demand equal to the difference
between the total supply and the total demand, i.e. 90− 70 = 20 million barrels
per day, and profits of shipping oil to this dummy country set equal to 0:
From\To England Japan Dummy
Field 1 £1.5 £2.5 0
Field 2 £2 £3 0
Then we have decision variables xij = number of barrels (in millions) per day
produced at field i and shipped to country j, i = 1, 2, j = 1, 2, 3 (1 – England,
2 – Japan, 3 – Dummy).
Then we have the objective function:
z = 1.5x11 + 2.5x12 + 2x21 + 3x22 −→ max
(total profit from the production and shipping, in million pounds)
subject to:
x11 + x12 + x13 = 40 (Field 1 supply constraint)
x21 + x22 + x23 = 50 (Field 2 supply constraint)
x11 + x21 = 40 (England demand constraint)
x12 + x22 = 30 (Japan demand constraint)
x13 + x23 = 20 (Dummy demand constraint)
xij ≥ 0, (i = 1, 2, j = 1, 2, 3)
(Using a graphical representation of the problem, i.e. drawing a simple diagram
with a bipartite graph representing the problem would be helpful here.)
- 5 -
MAT021/20
(b) Using the Branch-and-Bounds method, solve the following instance of the Knap-
sack Problem:
maximise 10x1 + 6x2 + 7x3 + 12x4 + 9x5
subject to 3x1 + 2x2 + 4x3 + 6x4 + 4x5 ≤ 10
x1, x2, x3, x4, x5 = 0 or 1
Use the ratio choice method to obtain solutions to the LP relaxations of the cor-
responding problems. Provide all the necessary details and explanation, and draw
a Branch-and-Bounds tree of sub-problems for the solution process. [15 marks]
Model Answer: (Class notes and exercise/practice questions)
We consider the linear relaxation of the original problem (P0):
maximise 10x1 + 6x2 + 7x3 + 12x4 + 9x5
subject to 3x1 + 2x2 + 4x3 + 6x4 + 4x5 ≤ 10
0 ≤ x1, x2, x3, x4, x5 ≤ 1
To solve the LP relaxation of (P0), we can use the ratio choice method.
We find the following ratios:
r1 = 10/3 = 3.33,
r2 = 6/2 = 3,
r3 = 7/4 = 1.75,
r4 = 12/6 = 2,
r5 = 9/4 = 2.25.
Thus, r1 > r2 > r5 > r4 > r3.
Therefore, the solution to the LP relaxation of (P0) is x1 = x2 = x5 = 1, x4 = 1/6,
x3 = 0, and z = 27 is an upper bound for any integer solution.
Since this is not an integer solution, consider branching by x4, i.e. subproblems
(P1)=(P0)+(x4 = 1) and (P2)=(P0)+(x4 = 0).
The solution to the LP relaxation of (P1) is x4 = x1 = 1, x2 = 1/2, x3 = x5 = 0,
and z = 25.
The solution to the LP relaxation of (P2) is x4 = 0, x1 = x2 = x5 = 1, x3 = 1/4,
and z = 26.75.
Since these are not integer solutions, and (P2) has a higher objective function
value, we first consider branching (P2) by x3, i.e. subproblems
(P3)=(P2)+(x3 = 1) and (P4)=(P2)+(x3 = 0).
The solution to the LP relaxation of (P3) is x3 = x1 = x2 = 1, x4 = 0, x5 = 1/4,
and z = 25.25.
The solution to the LP relaxation of (P4) is x1 = x2 = x5 = 1, x4 = x3 = 0, and
- 6 -
MAT021/20
z = 25. As the solution to the LP relaxation of (P4) is an integer solution, this
becomes a lower bound, and (P4) is fathomed.
Since an integer solution to (P3) is upper-bounded by 25, because of the lower
bound of 25 from (P4) now, (P3) is fathomed.
Since an integer solution to (P1) is upper-bounded by 25 and is equal to the lower
bound given by (P4) now, (P1) is fathomed (we don’t need to branch (P1) be-
cause we cannot get a better integer solution in that branch).
So, all the nodes of the search tree are fathomed, and the optimal solution to the
original problem (P0) is x1 = x2 = x5 = 1, x4 = x3 = 0, with z = 25.
- 7 -
MAT021/20
3 (a) Give an informal description of the (basic) Assignment Problem. Provide an Inte-
ger Programming formulation of the Assignment Problem. Explain the meaning
of all parameters, variables, and constraints. [ 5 marks ]
Model Answer: (Class notes) In an assignment problem, we have n people
p1, p2, . . . , pn and n jobs w1, w2, . . . , wn, and the cost cij of performing job j by
person i, i = 1, 2, . . . , n, j = 1, 2, . . . , n. We wish to find an assignment of people
to jobs (one person per job and one job per person) such that the total cost of per-
forming the jobs is minimised. The costs are normally given by a matrix C = [cij].
Using zero-one decision variables xij such that xij = 1 iff employee i is assigned
to job j, the assignment problem can be expressed as an IP problem as follows:
min z =
n∑
i=1
n∑
j=1
cijxij
s.t.
n∑
i=1
xij = 1, j = 1, 2, . . . , n
n∑
j=1
xij = 1, i = 1, 2, . . . , n
xij = 0 or 1, i, j = 1, . . . , n,
where the first set of constraints guarantees that each job has exactly one person
assigned to perform it, and the second set of constraints guarantees that each
employee is assigned to exactly one job.
(b) Provide an Integer Programming formulation of the Travelling Salesman Problem
(TSP). Explain the meaning of all parameters, variables, and constraints.[7 marks]
Model Answer: (Class notes) Define zero-one variables xij = 1 iff city i is vis-
ited immediately prior to city j. Let cij represent the distance between cities i
and j (assume that the distances cii are prohibitively high). Suppose that there
are n cities that must be visited on the tour.
- 8 -
MAT021/20
Then the TSP can be expressed as an IP problem as follows:
min z =
n∑
i=1
n∑
j=1
cijxij
s.t.
n∑
i=1
xij = 1, j = 1, 2, . . . , n
n∑
j=1
xij = 1, i = 1, 2, . . . , n
u1 = 1
2 ≤ ui ≤ n, i = 2, . . . , n
ui − uj + 1 ≤ (n− 1)(1− xij), i, j = 2, . . . , n
xij = 0 or 1, i, j = 1, . . . , n
ui is integer, i = 1, . . . , n
The first set of constraints says that you must go into each city j exactly once,
and the second set of constraints says that you must leave each city i exactly once.
These constraints ensure that there are two edges adjacent to each city, one in and
one out. This does not prevent so-called sub-tours of less than n arcs: a sub-tour
occurs when there is a cycle containing a proper subset of the cities. Instead of
having one tour of all of the cities, the solution can eventually be composed of two
or more sub-tours each of less than n arcs. The constraints with ui variables elimi-
nate sub-tours – ui are integer variables representing position of city i on the tour.
(c) Given an instance of the TSP and an instance of the Assignment Problem with
the same costs matrix C = [cij], which of the two instances will eventually have
a smaller value of the objective function on its optimal solution? (Assume that
the costs cii, i = 1, 2, . . . , n, are prohibitively high.) Justify your answer.[3 marks]
Model Answer: (Class notes/unseen) The value of the objective function of the
Assignment Problem is a lower bound for the value of the objective function of
the corresponding TSP since both problems have the same objective function,
but TSP has additional constraints in comparison to the IP formulation of the
assignment problem. In other words, the value of the objective function cannot
improve with additional constraints.
(d) Explain how you would use a greedy heuristic to produce a solution to the TSP.
State one advantage and one disadvantage of a greedy heuristic. [3 marks]
Model Answer: Starting from city i, choose the nearest unvisited city and con-
tinue until all cities have been visited. Advantage is very quick, disadvantage is
that solution is likely to be poor especially towards the end of the process.
- 9 -
MAT021/20
(e) Explain how you would use simulated annealing to produce a solution to the TSP.
Include in your answer a definition of the cost function, neighbourhood and start-
ing solution and state any parameters that are required. State one advantage and
one disadvantage of simulated annealing. [7 marks]
Model Answer:
Starting from a random solution choose two cities at random and swap their
position. Evaluate the effect on the cost function (distance). If the distance is
decreased, accept the change. Otherwise accept if a random number between
0 and 1 is less than exp(−d/t) where d is the increase on distance and t is a
parameter. The value of t is lowered during the search using t = r ∗ t where r is
a parameter ≤ 1. Stop when t is too low to accept further moves. Advantage is
can escape from local optima. Disadvantage is the need to set parameters.
- 10 -
MAT021/20
4 (a) You are given the following set of jobs:
Job Duration Due Time
1 12 23
2 8 15
3 17 34
4 10 20
5 5 13
6 11 35
(i) Define the terms makespan and slack in a scheduling context. [3 marks]
Model Answer: Makespan is the total length of time it takes to complete
all jobs. Slack is the length of time for which a job can be delayed and still
be completed by its due date.
(ii) Produce a schedule using the Critical Ratio method. [3 marks]
Model Answer: Job 2 (finishes at time 8), Job 4 (finishes at time 18), Job
5 (finishes at time 23), Job 1 (finishes at time 35), Job 6 (finishes at time 46),
job 3 (finishes at time 63).
(iii) Produce the schedule which minimises the number of late jobs using Moore’s
Algorithm. [4 marks]
Model Answer: Order is 5-2-4-1-6-3. Only 5 and 2 are on time. Move 2 to
end. New order is 5-4-1-6-3-2. Only 5 and 4 are on time. Move 4 to the end.
new order is 5-1-6-3-2-4. 5, 1 and 6 are on time, so 3 jobs are on time. This
is optimal.
(b) An investor is deciding how to invest £5 million between three different investment
schemes. The table below shows the amounts that can be invested in each of the
three schemes, together with the expected returns. All values stated are in millions
of pounds.
Scheme 1 Scheme 2 Scheme 3
Proposal Cost Revenue Cost Revenue Cost Revenue
1 0 0 0 0 0 0
2 1 1 2 2.5 1 1.5
3 2 3 3 4 3 4
4 3 4 - - - -
Use dynamic programming to determine how much should be invested in each
scheme in order to maximise the expected return. Give all optimal solutions. In-
clude all definitions in your answer. No marks will be awarded if a method other
than dynamic programming is used. [15 marks]
- 11 -
MAT021/20
Model Answer n = schemes left to consider, i = remaining money
f(0, 0) = 0
f(1, 5) = 4
f(1, 4) = 4
f(1, 3) = 4
f(1, 2) = 1.5
f(1, 1) = 1.5
f(1, 0) = 0
f(2, 5) = max(0 + f(1, 5), 2.5 + f(1, 3), 4 + f(1, 2)) = 6.5
f(2, 4) = max(0 + f(1, 4), 2.5 + f(1, 2), 4 + f(1, 1)) = 5.5
f(2, 3) = max(0 + f(1, 3), 2.5 + f(1, 1), 4 + f(1, 0)) = 4
f(2, 2) = max(0 + f(1, 2), 2.5 + f(1, 0)) = 2.5
f(3, 5) = max(0 + f(2, 5), 1 + f(2, 4), 3 + f(2, 3), 4 + f(2, 2)) = 7
Solution is 2 in scheme 1, 0 in scheme 2 and 3 in scheme 3 or
2 in scheme 1, 2 in scheme 2 and 1 in scheme 3 or
2 in scheme 1, 3 in scheme 2
- 12X -

































































































































































































































































































































学霸联盟