MA231-2018-exam solutions
pdf
keyboard_arrow_up
School
London School of Economics *
*We aren’t endorsed by this school
Course
231
Subject
Mathematics
Date
Nov 24, 2024
Type
Pages
15
Uploaded by ONYNO_
Summer 2018 examination
MA231
Operational Research Methods
Suitable for all candidates
Instructions to candidates
This paper contains
6
questions. You may attempt as many questions as you wish, but only
your
best 5
answers will count towards the final mark.
All questions carry equal numbers of
marks.
Answers should be justified by showing work.
Please write your answers in dark ink (black or blue) only.
Time Allowed
Reading Time:
None
Writing Time:
2 hours and 45 minutes
You are supplied with:
Answer booklets
You may also use:
No additional materials
Calculators:
Calculators are not allowed in this examination
c
LSE ST 2018/MA231
Page 1 of 15
Question 1
(a)
Use Dijkstra’s algorithm to find a shortest path tree in the network below. The network
has undirected edges; each such edge can if you prefer be thought of as a pair of oppositely
directed arcs of the same lengths.
s
A
B
E
C
D
8
1
7
9
5
7
2
1
3
2
3
Copy the supplied table into your exam booklet and complete it.
Each row represents
an iteration of the algorithm.
In the “added to R” column, show the node added and,
in parentheses, its cost.
In the columns for each node A through E, show the current
distance estimate and, in parentheses, the corresponding predecessor (if any).
iter
to R
A
B
C
D
E
0
–
∞
∞
∞
∞
∞
1
s (0)
8 (s)
.
.
.
[7 marks]
Solution
:
In the table below, once a node has been added to the set
R
its column
is done, and we mark the remaining entries with a dash.
iter
to R
A
B
C
D
E
0
–
∞
∞
∞
∞
∞
1
s (0)
8 (s)
1(s)
∞
∞
7 (s)
2
B (1)
8 (s)
–
4 (B)
10 (B)
6 (B)
3
C (4)
5 (C)
–
–
10 (B)
6 (B)
4
A (5)
–
–
–
8 (A)
6 (B)
5
E (6)
–
–
–
8 (A)
–
6
D (8)
–
–
–
–
–
(b)
Dijkstra’s algorithm maintains a set
R
of nodes
v
whose shortest path distances
d
(
v
)
from the source
s
are known. For any
u
∈
R
and
v /
∈
R
where there is an arc (
u, v
) of
length
d
(
u, v
),
v
can be reached from
s
at distance
d
(
u
) +
d
(
u, v
) — i.e., staying within
R
except for one last hop out — but there may be shorter paths to
v
. Over
u
∈
R
and
v /
∈
R
, let
u
*
and
v
*
be a pair minimising
d
(
u
)+
d
(
u, v
). Prove that the shortest distance
from
s
to
v
*
is indeed
d
*
:=
d
(
u
*
) +
d
(
u
*
, v
*
) and thus
v
*
can be added to
R
.
Where
does your argument rely on the fact that the arc lengths are nonnegative?
[5 marks]
Solution
:
If the shortest distance from
s
to
v
*
is not
d
(
u
*
) +
d
(
u
*
, v
*
) then there
must be some shorter path
P
from
s
to
v
*
. Since
P
starts in
R
(at
s
) and ends
outside
R
(at
v
*
), it has some arc (
w, x
) that first crosses out of
R
, and the length
c
LSE ST 2018/MA231
Page 2 of 15
of
P
is the sum of its lengths from
s
to
x
and from
x
to
v
. The length from
s
to
x
is included in the minimisation whose result was
d
*
(it comes from a path within
R
except for a final hop out), and thus is
≥
d
*
. The length from
x
to
v
*
is
≥
0,
using
that all arc lengths are nonnegative
. Thus the length of
P
is
≥
d
*
, contradicting
this being a shorter path.
(c)
A set of customised widgets
W
1
, W
2
, . . . , W
n
must be manufactured in that order. The
customisation means that ideally, the machine would be specifically tuned to each widget.
If widgets
W
i
, W
i
+1
, . . . , W
j
are manufactured together in one “run”, the machine cannot
be perfectly tuned for any of them, and all of them come out slightly imperfect; the
manufacturer models this with a penalty cost
f
(
i, j
) that they can easily compute.
For
this reason it is not good to make too many widgets at once. On the other hand, each run
takes 1 hour, modelled as a cost of
£
100, so it is also not good to make too few widgets
at once.
The goal is to produce the widgets
W
1
, W
2
, . . . , W
n
at minimum cost, including the penalty
costs
f
(
i, j
) and the run costs
£
100. Show how to model this problem as a shortest path
problem.
[8 marks]
Solution
:
Take nodes 1
,
2
, . . . , n, T
, representing the widgets and a terminal
node, and search for a shortest path from 1 to
T
. Include arcs (
i, j
) for any
j > i
.
An arc (
i, j
) represents a run starting at widget
i
and ending at
j
-
1. A path from
1 to
T
represents a breakdown of the widgets into runs, for example an arc entering
j
representing a run ending with
W
j
-
1
, the arc leaving
j
representing the next run
starting with
W
j
. There is a one-to-one correspondence between 1-to-
T
paths, and
sets of runs comprising all widgets. Define arc lengths by
d
(
i, j
) = 100 +
f
(
i, j
-
1),
the time and penalty costs for the run. Then the total cost of the run is the length
of the path, and a minimum 1-to-
T
path gives an optimal manufacturing plan.
c
LSE ST 2018/MA231
Page 3 of 15
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Question 2
(a)
M
is a Markov chain with the transition diagram shown below; transition probabilities are
not shown but are positive.
A
B
C
D
E
F
G
H
I
(i)
What are the equivalence classes?
[3 marks]
Solution
:
The classes are
{
A, B, D, E
}
,
{
C
}
,
{
F, G, H
}
,
{
I
}
.
Within each
class you can get from any state to any state.
(ii) What is the period of each state?
[2 marks]
Solution
:
All states in a class have the same period. The periods of the classes
above are respectively 1 (the cycles of lengths 2 and 3 combine to give period
1), undefined, 3, 1.
(iii) Which states are transient?
[1 mark]
Solution
:
Again, this is a class property. The classes
{
C
}
and
{
F, G, H
}
are
transient.
(iv) Which states are absorbing?
[1 mark]
Solution
:
Again a class property, but here only
I
is absorbing.
(v) Which states are recurrent?
[1 mark]
Solution
:
Again a class property, and indeed the negation of “transient”. The
classes
{
A, B, D, E
}
and
{
I
}
are recurrent.
(b)
Joe Java is addicted to coffee. He can’t get enough. He drinks a cup an hour, 24 hours a
day. And he likes it good: he walks 15 minutes each way to the best local espresso joint,
and he reckons the round-trip journey costs him
£
10 in lost time. He gets his coffee to
go, drinking it on the walk and when he’s back home. To save time, he gets a few cups
at once; each cup costs
£
2. Of course, the coffee cools and congeals over time; Joe puts
the decline in value to him at
£
0.25 per hour per cup. Joe has just taken an OR course.
He’s sitting the exam right now, his mind is wandering, and he finds himself wondering if
he can optimise his coffee buying.
(i)
Joe remembers the formula
Q
*
=
q
2
dK
h
·
p
+
h
p
. What is the
meaning
of each of these
variables, and what are their
values
in Joe’s case? (Remember to include the units of
c
LSE ST 2018/MA231
Page 4 of 15
measurement – pounds, hours, whatever.)
How many cups
of coffee should Joe buy
at a time?
[3 marks]
Solution
:
K
=
£
10 is the fixed ordering cost.
h
=
£
0
.
25 per cup per hour is
the holding cost.
d
= 1 cup per hour is the fixed demand rate. As described,
shortage is not allowed, so we can either ignore the
p
+
h
p
term or, equivalently,
set
p
=
∞
(which makes the term 1). Then 2
Kd/h
= (2
·
10
·
1
/
0
.
25) cups
2
=
80 cups
2
, so the economic order quantity — the amount Joe should buy per
order — is
Q
*
=
√
80 cups. We round this to 9 cups.
(ii) Joe is worried that the
£
2 cost of a cup of coffee doesn’t seem to have entered his
calculation. Explain why this makes sense.
[3 marks]
Solution
:
Whatever purchase policy Joe follows, on average he must buy 1
cup per hour, thus must spend
£
2 per hour on the coffee itself.
Since the
goal is to minimise the net cost per hour, this additive constant has no effect.
(Minimising
f
+ constant is equivalent to minimising
f
.)
(iii) Joe is thinking that
Q
*
cups is a lot to carry at once. If he bought
Q
*
-
1 cups at
a time instead, would you expect it to make much difference to his net average cost
per cup? Explain your reasoning.
[2 marks]
Solution
:
The change from 9 to 8 is, in itself, neither large nor tiny at about
10%. But
Q
*
is chosen to minimise cost per cup (actually cost per time, but
they are the same up to a factor
d
) and as such the derivative at
Q
*
is 0, so
changes to
Q
*
will make very small changes to the function value.
(iv) Joe wonders what he could save if he’d be willing to go without coffee for a while. He
puts his shortage cost at
£
2 per cup per hour of waiting. By this measure, once his
coffee runs out, what is the total shortage cost over the first hour? What is the total
shortage cost over the first two hours?
[2 marks]
Solution
:
The shortage cost is
p
=
£
2 per cup per hour. At the start of the
1 hour he is 0 cups short, and by the end of it 1 cup short, so on average he
is 1/2 a cup short.
The cost is
p
·
1
2
cup
·
1 hour
=
£
1.
After 2 hours, on
average he is 1 cup short, for 2 cup-hours, thus
£
4.
(v) How much would allowing shortage change
Q
*
?
[2 marks]
Solution
:
Q
*
increases by a factor
q
p
+
h
p
=
p
2
.
25
/
2 =
√
1
.
125
≈
1
.
06.
Since it was just under 9, it becomes something less than 9
.
54; it might now
round to 10 rather than 9.
(Exact calculations show it doesn’t:
it’s about
9
.
487.)
c
LSE ST 2018/MA231
Page 5 of 15
Question 3
(a)
Compare absorbtion times for the following two Markov chains.
(i)
The undirected graph
G
is a cycle of 5 vertices,
v
1
–
v
2
–
v
3
–
v
4
–
v
5
–
v
1
, and
v
3
is absorbing.
From any other vertex, walk randomly to either of its neighbors.
(Throughout this
question, “random” is shorthand for “uniformly random”:
every choice is equally
likely.)
What is the expected absorption time from each of the 5 vertices?
Also,
starting from a random one of the 5 vertices, what is the expected time to absorption?
Take advantage of symmetry in your calculations.
[3 marks]
Solution
:
Let
a
be the expected time from
v
2
and
v
4
(they are equal by sym-
metry), and
b
the expected time from
v
1
and
v
5
. Then
a
= 1 +
1
2
b
+
1
2
0 and
b
= 1 +
1
2
a
+
1
2
b
. The latter gives
1
2
b
= 1 +
1
2
a
, thus
b
= 2 +
a
. Then, the
former gives
a
= 1 + 1 +
1
2
a
, for
1
2
a
= 2. We thus have
a
= 4 and
b
= 6. The
average time is
1
5
(0 + 4 + 4 + 6 + 6) = 4.
(ii) The undirected graph
H
is a path of 5 vertices,
v
1
–
v
2
–
v
3
–
v
4
–
v
5
. Vertex
v
3
is absorbing.
From vertex
v
2
, walk randomly to vertex
v
1
or
v
3
; symmetrically, from
v
4
walk randomly
to
v
5
or
v
3
. From vertex
v
1
, walk only to
v
2
; symmetrically, for
v
5
, walk only to
v
4
.
What is the expected absorption time from each of the 5 vertices? Starting from a
random one of the 5 vertices, what is the expected time to absorption?
[3 marks]
Solution
:
Let
a
be the expected time from
v
2
and
v
4
(they are equal by sym-
metry), and
b
the expected time from
v
1
and
v
5
.
Then
a
= 1 +
1
2
b
+
1
2
0
while (this is different)
b
= 1 +
a
.
Substituting the latter into the former,
a
= 1 +
1
2
(1 +
a
), for
1
2
a
=
3
2
. We thus have
a
= 3 and
b
= 4. The average
time is
1
5
(0 + 3 + 3 + 4 + 4) =
14
5
<
3.
(iii) The expected absorbtion time is longer for one of these Markov chains than the other.
Give an intuitive, calculation-free explanation of this. (You need only explain for length
5, but one simple explanation applies equally to paths and cycles of any odd length.)
[2 marks]
Solution
:
On the path, we always go from a “b” vertex like
v
1
to an “a”
vertex. Suppose that instead we allowed the walk to stay at
v
1
(and
v
5
) with
probability
1
2
; this would be a random walk on a graph
H
0
like
H
but with “loops”
on the end vertices. This walk is obviously slower: it is the same except that
sometimes we simply don’t move. But staying at
v
1
is, by symmetry, no different
from moving to
v
5
, so if from
v
1
the choices are
v
2
or
v
5
, that walk has the same
speed as the one on
H
0
. But this is exactly the walk on
G
. So absorbtion on
H
is faster than that on
H
0
which is the same as that on
G
.
(b)
A garment distributer supplies (among many other things), mens suits in a particular
popular style, colour, and size. They pay
£
200 for each suit, and sell it to a retailer for
£
300. They expect their retailers demand for these to be around 200 suits; specifically,
uniformly distributed between 190 and 209 (inclusive). They will stock in X suits. If this
exceeds the retailer demand, every excess suit is sold to a discounter for
£
50. If it is less
than the demand, there is no particular consequence.
(i)
What is the unit purchase cost
c
? What are the shortage cost
p
and holding cost
h
(or, at your preference, the underordering cost
c
u
and overordering cost
c
o
)?
[2 marks]
c
LSE ST 2018/MA231
Page 6 of 15
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Solution
:
c
= 200,
p
= 300,
h
=
-
50,
c
u
=
p
-
c
= 100,
c
o
=
h
+
c
= 150.
(ii) What is the optimal service level
F
(
X
*
)?
[3 marks]
Solution
:
F
(
X
*
) =
c
u
c
o
+
c
u
=
100
150+100
=
2
5
.
(iii) How many suits
X
*
should they optimally stock?
[3 marks]
Solution
:
The distribution is uniform over 20 values, 190–209, so each has
probability mass 0
.
05 and together the first 8 of them (190–197) have probability
0
.
4 =
2
5
. That is,
X
*
= 197, since this gives cumulative probability
F
(
X
*
) = 0
.
4.
(iv) What is their expected profit if they stock
X
*
suits?
[4 marks]
Solution
:
If demand is 197 the profit is 197(300
-
200) + 0(50
-
200) =
19
,
700. For each unit less demand, they lose one retail sale profit of 100, and
take on one discount sale loss of 150, making 250 less than the above. That is,
for demand of 196 they make 1
·
250 less, for demand 195 they make 2
·
250 less,
. . . , and for demand 190 they make 7
·
250 less. The average over these cases
(demand 196 to 190) is
1+7
2
·
250 = 4
·
250 = 1
,
000 less, and these 7 cases
occur with probability 7
/
20. In the other cases they make the full
£
19,700. So
the expectation is 19
,
700
-
7
20
·
1
,
000 = 19
,
700
-
350 =
£
19
,
350.
c
LSE ST 2018/MA231
Page 7 of 15
Question 4
(a)
A baker has an order to deliver 3 cakes on Monday, 3 on Tuesday and 4 on Wednesday.
He can make at most 5 cakes on a single day. The cakes can be stored for up to 3 days,
hence the cakes baked on Monday can be still delivered on Wednesday. The cost of making
cakes varies depending on the day they are made and also on the number of cakes made
at a time. The following table indicates the cost. For example, if three cakes are made
on Tuesday, then the total cost of making these three cakes is
£
40.
Nr of cakes
Monday
Tuesday
Wednesday
1
40
25
10
2
45
35
20
3
50
40
30
4
55
45
40
5
65
50
45
The baker wants to find a baking schedule to minimize costs assuming there is no cost in
storing a cake overnight.
(i)
Use dynamic programming to determine the optimal baking schedule.
Include the
details of your formulation as well as the detailed calculations. If there are multiple
optimal schedules, list all of them.
[10 marks]
Solution
:
We define three stages for the three days;
n
= 1 for Wednesday,
n
= 2 for Tuesday, and
n
= 3 for Monday.
At any stage, the state
s
means that we still need to bake
s
cakes for the
remaining days.
The action
x
is the number of cakes baked at this day. The transition function
is
t
(
n, s, x
) =
s
-
x
. We must have
x
≤
5, and we can always assume
x
≤
s
.
We let
x
*
(
n, s
) denote the optimal action in state
s
at stage
n
.
The costs
c
(
n, x
) are given in the table; the cost is independent of the state
s
.
Let
d
(
n
) denote the demand at each day, that is
d
(1) = 4,
d
(2) =
d
(3) = 3.
Let
D
(
n
) =
∑
n
i
=1
d
(
n
) denote the number of cakes to be baked on days 1 to
n
.
Then, for every state
n
, the set of feasible actions is
max
{
0
, s
-
D
(
n
-
1)
} ≤
x
≤
s.
Here, the lower bound expresses that the demand for day
n
must be satisfied.
We let
f
(
n, s
) to denote the minimum total cost at (
n, s
). Bellmann’s recursive
equation is
f
(
n, s
) = min
{
c
(
n, x
) +
f
(
n
-
1
, s
-
x
) : max
{
0
, s
-
D
(
n
-
1)
} ≤
x
≤
s
}
Stage 1
(
n
= 1)
, Wednesday
Now,
x
=
s
is the only possible action, thus,
x
*
(1
, s
) =
s
. Note that
s
≤
4.
s
x
*
(1
, s
)
f
(1
, s
)
0
0
0
1
1
10
2
2
20
3
3
30
4
4
40
c
LSE ST 2018/MA231
Page 8 of 15
Stage 2
(
n
= 2)
, Tuesday
We now have
s
≤
7 (the total number for Tue and Wed).
The actions are
x
≤
min
{
s,
5
}
. Further, we must have
x
≥
max
{
0
, s
-
4
}
, since we cannot leave
more than 4 for Wednesday.
s
\
x
0
1
2
3
4
5
x
*
(2
, s
)
f
(2
, s
)
0
0
0
0
1
10
25
0
10
2
20
35
35
0
20
3
30
45
45
40
0
30
4
40
55
55
50
45
0
40
5
65
65
60
55
50
5
50
6
75
70
65
60
5
60
7
80
75
70
5
70
Stage 3
(
n
= 3)
, Monday
We are only interested in
s
= 10, the total number of cakes for the three days.
The set of actions is 3
≤
x
≤
5, since we must satisfy the demand for Monday.
s
\
x
3
4
5
x
*
f
(2
, s
)
10
120
115
115
4,5
115
We see that the minimum total cost is 115.
There are two optimal baking
schedules: 4 on Monday, 5 on Tuesday, and 1 on Wednesday, or 5 on Monday,
5 on Tuesday, and 0 on Wednesday.
(Other formulations are also possible, e.g.
s
could alternatively denote the
inventory at the beginning of the day.)
(ii) Suppose there was a cost of
£
5 for storing each cake overnight.
State how the
formulation of the dynamic program would change.
You do not need to solve this
problem.
[2
marks]
Solution
:
The number of cakes remaining for the next day can be computed as
r
(
n, s, x
) = (10
-
s
+
x
)
-
3
X
i
=
n
d
(
n
)
,
where (10
-
s
+
x
) is the number of cakes baked on days 3
, . . . , n
, and the second
term is the number of cakes delivered on these days. The modified formula will be
f
(
n, s
) = min
{
c
(
n, x
) + 5
r
(
n, s, x
) +
f
(
n
-
1
, s
-
x
) : max
{
0
, s
-
D
(
n
-
1)
} ≤
x
≤
s
}
(b)
A two-person zero-sum game is given by the following payoff matrix:
A
=
0
2
17
-
3
-
2
0
-
12
0
-
17
12
0
8
3
0
-
8
0
.
This is called a
symmetric game
, since
A
is a skew-symmetric matrix, that is,
A
=
-
A
>
.
(i)
What is the expected payoff if both players play the same mixed strategy?
[2 marks]
c
LSE ST 2018/MA231
Page 9 of 15
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Solution
:
If both players play the same strategy
p
, then the expected payoff
is
p
>
Ap
= 0
,
since all diagonal elements of
A
are 0 and the off-diagonal terms cancel out.
(ii) Determine the value of this game. Justify your answer.
[2
marks]
Solution
:
From the previous part, we see that column player can always guar-
antee
≤
0 by mimicking the strategy of row player.
Similarly, the row player
can always guarantee
≥
0. Thus, the value of the game must be 0. Another
argument is by looking at the two LPs as in the next part.
(iii) Write the LPs describing the optimal mixed strategies for both the row player and
the column player. Using these LPs, show that if (
x
1
, x
2
, . . . , x
n
) is an optimal mixed
strategy for the row player, then (
x
1
, x
2
, ..., x
n
) is also an optimal mixed strategy for
the column player.
[4
marks]
Hint: no calculations are needed to answer these questions.
The same answers will be
valid for any symmetric game.
Solution
:
The LP the row player has to solve is
min
v
y
>
A
≤
v
X
i
y
i
=
1
y
≥
0
.
The LP of the column player is
max
u
Ax
≥
u
X
i
x
i
=
1
x
≥
0
.
We see that these are the same for
A
=
-
A
>
, by setting
u
=
-
v
. Therefore, the
set of optimal mixed strategies must be the exact same.
c
LSE ST 2018/MA231
Page 10 of 15
Question 5
(a)
Consider the following linear programming problem:
min
5
x
1
+2
x
2
+ 6
x
3
x
1
-
2
x
2
+ 2
x
3
≥
3
x
2
+ 4
x
3
≥
1
x
1
+
x
2
≥
4
x
2
≤
0
, x
3
≥
0
(
P
)
(i)
Write down the dual linear program (
D
) of (
P
).
[3
marks]
Solution
:
max
3
y
1
+
y
2
+4
x
3
y
1
+
y
3
=
5
-
2
y
1
+
y
2
+
y
3
≥
2
2
y
1
+4
y
2
≤
6
y
1
, y
2
, y
3
≥
0
(
D
)
(ii) Prove that the point
x
*
= (4
,
0
,
1
4
) is an optimal solution to (
P
), including finding an
appropriate dual solution.
[3
marks]
Solution
:
We first check that
x
*
is feasible by substituting into all inequalities.
For
x
*
, the tight constraints are the second and third ones. By complementary
slackness,
y
1
= 0 in an optimal solution, and the first and third dual inequalities
must hold at equality. From the first equality, we see that
y
3
= 5. From the
third one, we see that
y
2
= 1
.
5.
The only candidate dual optimal solution is
y
*
= (0
,
1
.
5
,
5).
This is feasible,
since 1
.
5+5
>
2, and has the correct signs. Therefore, it verifies the optimality
of
x
*
.
(iii) Is
x
*
is an extreme point of the system (
P
)?
Justify your answer.
Does (
P
) have
any other optimal solutions? Provide another optimal solution, if there exists one, or
argue that
x
*
is the unique optimal solution.
[3
marks]
Solution
:
The point
x
*
satisfies altogether three inequalities at equality (second, third,
and
x
2
≤
0). These inequalities are linearly independent, and therefore
x
*
is an
extreme point.
x
*
is the unique optimal solution. Indeed, (0
,
1
.
5
,
5) was a dual optimal solution.
By complementary slackness, all primal optimal solutions must satisfy the 2nd
and 3rd inequalities at equality, and must have
x
2
= 0. These uniquely define
the extreme point
x
*
.
(iv) The coefficient of
x
2
in the objective function is 2; let us replace it by another number
α
∈
R
. For what values of
α
does
x
*
remain an optimal solution to (
P
)?
[4
marks]
Solution
:
The possible values of
α
are (
-∞
,
6
.
5). For any value in this range,
y
*
remains
a feasible optimal solution, and certifies optimality.
c
LSE ST 2018/MA231
Page 11 of 15
If
α >
6
.
5, then
y
*
will not be optimal. To see this, we note that the argument
in (i) is valid for any value of
α
, showing that any dual optimal
y
must satisfy the
first and third dual inequalities at equality, and must have
y
1
= 0. Consequently,
y
=
y
*
is the only possible choice; if it is infeasible, we can conclude that
x
*
is
not optimal anymore.
(b)
Let
G
= (
V, A
) be a directed graph, with nonnegative arc lengths
c
:
A
→
R
+
, and let
s, t
∈
V
be two vertices.
(i)
Provide a linear programming formulation of the shortest path problem from
s
to
t
.
[4
marks]
Solution
:
We let
x
:
E
→
R
be the variables in the formulation.
δ
in
(
u
) and
δ
out
(
u
) are
the sets of incoming and outgoing arcs from
u
, respectively. The formulation is
as below.
minimise
∑
e
∈
A
c
(
e
)
x
e
subject to
x
(
δ
in
(
s
))
-
x
(
δ
out
(
s
))
=
-
1
x
(
δ
in
(
u
))
-
x
(
δ
out
(
u
))
=
0
∀
u
∈
V
\ {
s, t
}
x
(
δ
in
(
t
))
-
x
(
δ
out
(
t
))
=
1
x
e
≥
0
∀
e
∈
A.
(ii) Write down the dual of this linear program.
[3
marks]
Solution
:
The dual variables
y
:
V
→
R
correspond to the vertices. The formulation is
maximise
y
t
-
y
s
subject to
y
v
-
y
u
≤
‘
(
u, v
)
∀
(
u, v
)
∈
A.
Variant without
y
s
also accepted at full marks.
c
LSE ST 2018/MA231
Page 12 of 15
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Question 6
(a)
Define the concept of an extreme point in a linear program of the form
Ax
≤
b
for a matrix
A
∈
R
m
×
n
,
b
∈
R
n
. What is the importance of extreme points in linear programming?
[3
marks]
Solution
:
Extreme point: feasible and satisfies
n
linearly independent constraints.
LP importance: if there is an optimal solution, there is always one that is an extreme
point.
(b)
Aldwick Chemical manufactures three chemicals:
A
,
B
, and
C
.
These chemicals are
produced simultaneously via two production processes: 1 and 2. The table below shows
the number of units that are produced by running each processes for one hour. The table
also reports the cost per hour of running each process, as well as the amount of each
chemical that the the company needs to produce in order to meet daily demand.
Process 1
Process 2
Demand
Chemical
A
2
5
20
Chemical
B
2
2
16
Chemical
C
6
1
18
Cost (
£
/hour)
10,000
12,000
(i)
Formulate an LP to help Aldwick determine the daily production plan, in order to
minimize total cost while ensuring that demands of each chemical are met.
Use
variables
x
1
and
x
2
, representing, respectively, the number of hours that process 1 and
process 2 are run for during the day. Express costs in thousands of pounds.
[3
marks]
Solution
:
min
10
x
1
+12
x
2
2
x
1
+ 5
x
2
≥
20
2
x
1
+ 2
x
2
≥
16
6
x
1
+
x
2
≥
18
x
1
, x
2
≥
0
(ii) Formulate the dual LP.
[3
marks]
Solution
:
max
20
y
1
+16
y
2
+18
y
3
2
y
1
+ 2
y
2
+ 6
y
3
≤
10
5
y
1
+ 2
y
2
+
y
3
≤
12
y
1
, y
2
, y
3
≥
0
An optimal solution, as computed above, is (2
/
3
,
13
/
3
,
0).
(iii) Draw the feasible region of the primal LP. Give primal and dual optimal solutions.
[4
marks]
Solution
:
c
LSE ST 2018/MA231
Page 13 of 15
The optimal solution is at the intersection of constraints 1 and 2. Setting them
at equality and solving for
x
1
and
x
2
gives
x
1
= 20
/
3 and
x
2
= 4
/
3. To prove
optimality, we need to solve the system
2
y
1
+ 2
y
2
=
10
5
y
1
+ 2
y
2
=
12
,
which gives
y
1
= 2
/
3,
y
3
= 13
/
3.
Since
y
1
, y
2
≥
0, it follows that
x
=
(20
/
3
,
4
/
3) is optimal for the primal.
(iv) Aldwick is interested in knowing how changes in the demand for chemical
B
affect the
total cost. How much does a unit increase or decrease in the demand affect the total
cost? Compute the range of demand for chemical B for which this cost increase rate
is valid (i.e., compute the allowable increase and allowable decrease for this variable).
[4
marks]
Solution
:
The dual constraint relative to Chemical
B
is
y
2
, which takes
value 13
/
3. Therefore any unit increase or decrease in the right hand side will,
respectively, increases or decreases the total cost by 13
/
3, as long as the change
in right-hand side does not change the optimal dual solution. The optimal dual
solution does not change as long as the optimal primal solution is defined by
constraints 1 and 2.
Thus the right-hand side can increase until constraint 2
passes through the intersection of constraint 1 and of the constraint
x
2
≥
0,
and decrease until constraint 2 passes through the intersection of constraints 1
and 3. Constraint 1 and of the constraint
x
2
≥
0 intersect at point (10
,
0), thus
the demand for Chemical B can increase until
2
·
10 + 2
·
0 = 20
.
Constraints 1 and 2 intersect at point (5
/
2
,
3), therefore the demand for Chem-
ical B can decrease until
2
·
5
/
2 + 2
·
3 = 11
.
(v) Due to a new large client, the demand for Chemical
A
will increase to 34 units. What
is the primal optimal solution in this case? Show that the dual problem of the modified
LP has more than one optimal solution.
[3
marks]
c
LSE ST 2018/MA231
Page 14 of 15
Solution
:
When the demand for Chemical A becomes 34, the relative con-
straint (constraint 1) becomes 2
x
1
+ 5
x
2
≥
34. In this situation the constraint
passes through the intersection point of constraints 2 and 3, which is the point
x
= (2
,
6).
This will be the optimal solution.
The dual solution
y
1
= 2
/
3,
y
2
= 0,
y
3
= 13
/
3 remains optimal, but we can now obtain a new dual solution
by choosing constraints 1 and 3 as defining constraints for the optimal point
x
= (2
,
6). We then need to solve the system
2
y
1
+ 6
y
3
=
10
5
y
1
+
y
3
=
12
This gives another optimal dual solution, namely
y
1
= 31
/
14,
y
2
= 0,
y
3
=
13
/
14.
END OF PAPER
c
LSE ST 2018/MA231
Page 15 of 15
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help