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

If $A$ has $m$ rows and $n$ columns, attach a nonnegative dual variable $y_i$ to each of the $m$ upper-bound constraints. The dual linear program isHere $A^T$ is the transpose of $A$, and all vector inequalities hold componentwise. Nonnegative dual variables preserve the direction of the original inequalities when taking weighted sums.

For feasible solutions $\mathbf{x},\mathbf{y}$, nonnegativity givesThe first inequality uses $A^T\mathbf{y}\ge \mathbf{c}$ and $\mathbf{x}\ge 0$; the second uses $A\mathbf{x}\le \mathbf{b}$ and $\mathbf{y}\ge 0$. This is weak duality.

For every primal feasible solution $\mathbf{x}$, weak duality givesThus no primal feasible solution improves on ${\mathbf{x}}^{\ast }$. Similarly, for every dual feasible solution $\mathbf{y}$,Therefore both candidates are optimal, with the same objective function value. Equality is a linear programming optimality certificate and does not require a separate existence argument.

The complementary slackness conditions areTo see their role, decompose the duality gap asEvery summand is nonnegative for feasible solutions, so the gap is zero exactly when every displayed product vanishes. Zero gap implies optimality by weak duality. Conversely, strong duality states that primal and dual optima, when both are attained, have equal values, and hence satisfy these conditions.

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.