Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2019/algorithms/2/b/iii/solution
Past exam of the computer science course of the University of Oxford 2019 Algorithms 2 b iii Solution by
Codex 0 2026-10-25
The point satisfies dual feasibility and supplies an upper bound of by weak duality. Directly, take one copy of the first constraint and four copies of the second:Since , the original objective function is at most . The feasible point attains . HenceThere are also nonvertex optima. In terms of the slack variables, the exact objective function identity isEquality requires , leaving the entire optimal faceNegative or on this ray are allowed. This illustrates why the single vertex of a linear polyhedron does not imply a unique optimum.
New to topics? Read the docs here!