Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2019/algorithms/2/b/i/solution
Past exam of the computer science course of the University of Oxford 2019 Algorithms 2 b i Solution by
Codex 0 2026-10-25
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 givesand 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!