Past exam of the mathematics course of the University of Cambridge / 2005 / ib / Paper 3 / 20D (Optimization)

Continue the simplex algorithm using dictionaries, with nonbasic variables zero at the current vertex. The given basis has payoffThus $x_2$ enters. Its positive row coefficients give ratios $11$ for $z_1$ and $77/4$ for $z_2$; the $x_1$ row does not restrict this increase. Therefore $z_1$ leaves. After that pivot,Now $x_3$ enters. Only the $z_2$ row decreases along this move, and its ratio is $11/11=1$, so $z_2$ leaves. The final dictionary isAll reduced payoff coefficients are nonpositive. Since the slacks must be nonnegative, $f\le 41$, attained with $z=0$. Hence $\boxed{x^{\ast }=(7,22,1),f^{\ast }=41}$. Direct substitution makes all three original constraints equalities. The final dictionary is the optimal tableau expressed with basic variables on the left, not just a proposed feasible vertex.

The dual linear program isThe negatives of the final slack payoff coefficients give $\boxed{y^{\ast }=(1,2/3,2/3)}$. Its three dual constraints are equalities, and its objective is $11+32/3+58/3=41$. Equality with the primal objective proves optimality by weak duality, independently of tableau sign conventions. It is also the complementary slackness certificate, with all primal variables and all dual variables strictly positive.

The dual constraints and objective coefficients on $x$ are unchanged, so $y^{\ast }$ remains dual feasible. Since every component of $y^{\ast }$ is positive, complementary slackness forces every constraint of any primal optimum paired with it to bind. Let $A$ be the original three-by-three constraint matrix and $b^{\prime }=b+ϵ$. It is invertible, and the only possible paired primal point isIf this point is nonnegative, it is primal feasible with zero slacks and $c^T{x}^{\prime }=y^{\ast T}{b}^{\prime }$, proving $y^{\ast }$ optimal. Conversely, if $y^{\ast }$ is optimal, linear programming duality supplies a paired primal optimum, and complementary slackness forces it to be exactly this point. This proves the strictly positive dual certificate and right-hand-side sensitivity criterion:Non-strict inequalities are essential: boundary cases can be degenerate but retain the same optimal dual vector. This is the complete range, not just a small-perturbation sufficient condition for linear programming sensitivity within a fixed optimal basis.