Past exam of the computer science course of the University of Oxford / 2019 / Algorithms / 2 / a / iv / Solution

No. For the linear polyhedron $P=[0,1{]}^2$, take $c=(1,0{)}^T$ and $x^{\ast }=(1,1/2{)}^T$. The maximum of $c^{T}x$ is one, attained at $x^{\ast }$. Yetso $x^{\ast }$ 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.