 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2019/algorithms/2/a/iv/solution

P = [0, 1]^{2}

, take

c = (1, 0)^{T}

and

x^{*} = (1, 1/2)^{T}

. The maximum of

c^{T} x

is one, attained at

x^{*}

. Yet

x^{*} = \frac{1}{2} (1, 0)^{T} + \frac{1}{2} (1, 1)^{T},

x^{*}

is not an extreme point, hence not a vertex of a linear polyhedron. An optimal face can contain many points; an arbitrary maximizer need not be one of its vertices of a linear polyhedron.

 New to topics? Read the docs here!