COMPUTER SCIENCE TRIPOS Part II – 2018 – Paper 7
Advanced Algorithms (TMS)
(a) What are the three possible cases for the solution of a linear program? For each
of them, give an example of a linear program in standard form exhibiting this
case. [6 marks]
(b) What is the set of optimal solutions for the following linear program?
Minimize − x1 − x2
−x2 ≥ −3
2×1 + x2 ≤ 8
x1, x2 ≥ 0
[6 marks]
(c) For a given linear program LP1
Maximize Xn
j=1
cjxj
Xn
j=1
aijxj ≤ bi (1 ≤ i ≤ m)
xj ≥ 0 (1 ≤ j ≤ n),
consider a new linear program LP2:
Minimize Xm
i=1
biyi
Xm
i=1
aijyi ≥ cj (1 ≤ j ≤ n)
yi ≥ 0 (1 ≤ i ≤ m).
(i) Prove that if x is a feasible solution for LP1 and y is a feasible solution for
LP2, then c
T x ≤ b
T
y. [6 marks]
(ii) Using your answer in Part (c)(i), what can we conclude about LP2 if we
know that LP1 is unbounded? [2 marks]