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

Only $z,w$ have printed nonnegativity restrictions; $x,y$ 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 $(x,y,z,w)=(2,3,0,0)$. 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 $s_1=1-2x+y-5w$ and $s_2=3-y-z-w$. The feasible region is in affine bijection with the nonnegative orthant in $(s_1,s_2,z,w)$:That orthant has only the origin as an extreme point, giving the same unique vertex of a linear polyhedron.

Use the standard maximum form of a linear program convention $\max c^{T}u$ subject to $Mu\le b$ and $u\ge 0$. Split the unrestricted variables as $x=x^{+}-x^{-}$ and $y=y^{+}-y^{-}$, with all four new variables nonnegative. The resulting linear program isIf equality-constraint standard form is preferred, add a nonnegative slack variable to each inequality.

Give the two inequalities nonnegative dual variables $\alpha ,\beta$. The dual linear program isThe paired inequalities encode equalities for the two original unrestricted variables. Equivalently, the dual linear program has $2\alpha =2$, $-\alpha +\beta =3$, $\beta \ge 4$, $5\alpha +\beta \ge 7$ and $\alpha ,\beta \ge 0$. Thus its only feasible point is $(\alpha ,\beta )=(1,4)$, of objective function value $13$.

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.