Past exam of the mathematics course of the University of Oxford / 2015 / Prelims / Mathematics IV / 5 / b

There are two primal inequalities, so there are two nonnegative dual variables. The five primal variables yield five dual inequalities:Each coefficient column of the primal linear program becomes one row of this dual linear program.

The inequality $3y_1+y_2\ge 6$, together with $y_2\ge 0$, impliesAlso $-y_1+y_2\ge -1$ impliesThus both inequalities are strictly slack throughout the feasible region. They are redundant: the remaining inequalities imply them, even with strict inequality. By complementary slackness, any primal optimum must therefore have $x_1=x_3=0$; this is the principle that strictly slack dual constraints force zero primal variables.

After removing the two redundant inequalities, the feasible region isIts lower boundary consists of three line segments or rays: $y_2=6-3y_1$ for $0\le y_1\le 4/3$, then $y_2=3-3y_1/4$ for $4/3\le y_1\le 16/7$, then $y_2=y_1-1$ for $y_1\ge 16/7$. The feasible region is everything on or above this boundary in the first quadrant.

The boundary extreme points areAlong its three successive pieces, the objective function $2y_1+y_2$ has respective slopes $-1$, $5/4$ and $3$ as $y_1$ increases. Thus it decreases to the middle extreme point and increases thereafter. For fixed $y_1$, moving above the boundary only increases the objective function. HenceAs an algebraic check of the graphical answer, the active inequalities givewith equality at the stated extreme point.

At ${\mathbf{y}}^{\ast }=(4/3,2)$, the first three dual left sides are $10/3$, $2/3$ and $14/3$, strictly above their bounds $1$, $-1$ and $-5$. Thus complementary slackness forces $x_1=x_2=x_3=0$. Both dual variables are positive, so both primal inequalities are equalities:Solving this linear system givesAll components are nonnegative, the two original upper bounds are met exactly, and the objective function equals the dual value. The weak duality bound therefore certifies optimality. The forced zero components and unique solution of the two remaining equalities also prove that the primal optimum is unique.