Solution

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

Only have printed nonnegativity restrictions; are unrestricted. In four-dimensional space, a vertex of a linear polyhedron needs four independent active constraints. There are exactly four available constraints, so all must be active. Solving them gives
and therefore the only possible vertex of a linear polyhedron is . It is feasible, and its four active normals are independent, so it is indeed a vertex of a linear polyhedron.
One can also see uniqueness geometrically from the slack variables and . The feasible region is in affine bijection with the nonnegative orthant in :
That orthant has only the origin as an extreme point, giving the same unique vertex of a linear polyhedron.

New to topics? Read the docs here!