Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 38 / 2

Write the primal in the form $\min c^{T}x$ with $Ax\ge b$ and $x\ge 0$. Its dual linear program is $\max b^T\lambda$ with $A^T\lambda \le c$ and $\lambda \ge 0$. Indeed, nonnegative combinations of the primal inequalities give $c^{T}x\ge {\lambda }^{T}Ax\ge {\lambda }^{T}b$, which is weak duality. The specific dual isThe four dual inequalities correspond, in order, to the four primal variables.

Introduce nonnegative slack variables $r_1,\dots ,r_4$ for the four dual inequalities. The initial simplex dictionary isAt the origin all four basic slacks are positive. Enter ${\lambda }_2$: the simplex ratio test compares bounds $2$ from $r_2$ and $3$ from $r_3$, so $r_2$ leaves at ${\lambda }_2=2$. Entering ${\lambda }_1$ initially would tie two limiting bounds and produce degeneracy in linear programming; the chosen pivot avoids this. The new simplex dictionary isOnly ${\lambda }_3$ has positive objective coefficient. Enter it; the limiting bound is $1/3$ from $r_3$, rather than $7$ from $r_4$. Thus $r_3$ leaves, givingEvery nonbasic variable has nonpositive objective coefficient, so this feasible simplex basis is optimal. Setting the nonbasic variables to zero yieldsBoth new basic solutions have strictly positive basic coordinates; neither pivot is degenerate.

The first and fourth dual constraints have positive slacks $8/3$ and $20/3$. Complementary slackness therefore requires $x_1=x_4=0$. Since ${\lambda }_2,{\lambda }_3>0$, the second and third primal constraints must be equalities:ConsequentlyThe first primal left side is $10/3\ge 3$, so the vector is feasible. Its value matches the feasible dual value, giving a linear programming optimality certificate.

For any feasible primal vector, twice the second constraint plus one third of the third givesSince $x_1,x_4\ge 0$,The vector $(0,11/6,1/3,0)$ is feasible and attains this bound. It is optimal, by this direct inequality proof of weak duality, without assuming the simplex method or a duality theorem. Equality forces $x_1=x_4=0$ and both positively weighted constraints tight, so it also proves uniqueness.