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

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.