Solution

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

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 . Hence
There are also nonvertex optima. In terms of the slack variables, the exact objective function identity is
Equality requires , leaving the entire optimal face
Negative 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!