COMPUTER SCIENCE TRIPOS Part II – 2020 – Paper 8
Advanced Algorithms (tms41)
(a) State the fundamental theorem of Linear Programming. [3 marks]
(b) Consider the following linear program:
minimise 4 · x1 − x2
−x1 + 5×2 ≥ 4
x1 − 0.5×2 ≤ 1
x1, x2 ≥ 0
(i) Convert this linear program into slack form. [3 marks]
(ii) What is the number of different slack forms of the linear program in Part
(b)(i)? [2 marks]
(iii) Give at least one non-feasible and one feasible basic solution of the linear
program in (b)(i). [4 marks]
(c) Consider the following separation problem. We are given m points x
1 =
(x
1
1
, x1
2
), x2 = (x
2
1
, x2
2
), . . . , xm = (x
m
1
, xm
2
) ∈ R
2 and n points y
1 = (y
1
1
, y1
2
), y2 =
(y
2
1
, y2
2
), . . . , yn = (y
n
1
, yn
2
) ∈ R
2
. The goal is to find a “separating” vector
w = (w1, w2) ∈ R
2
(if it exists) such that:
hx
i
, wi =
X
2
j=1
x
i
jwj > 0 for i = 1, 2, …, m,
and
hy
i
, wi =
X
2
j=1
y
i
jwj < 0 for i = 1, 2, …, n.
(i) Create a new, equivalent system of inequalities by replacing each strict
inequality by a suitable non-strict inequality. Justify why this new system
has a solution if and only if the original system has one. [4 marks]
(ii) Based on your answer in Part (c)(i), how can you solve the above problem
using linear programming? [4 marks]