Past exam of the computer science course of the University of Oxford / 2019 / Algorithms / 2 / b / iii

The point $(1,4)$ satisfies dual feasibility and supplies an upper bound of $13$ by weak duality. Directly, take one copy of the first constraint and four copies of the second:Since $w\ge 0$, the original objective function is at most $13-2w\le 13$. The feasible point $(2,3,0,0)$ attains $13$. HenceThere are also nonvertex optima. In terms of the slack variables, the exact objective function identity isEquality requires $s_1=s_2=w=0$, leaving the entire optimal faceNegative $x$ or $y$ on this ray are allowed. This illustrates why the single vertex of a linear polyhedron does not imply a unique optimum.