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

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$.