Past exam of the mathematics course of the University of Cambridge / 2008 / ib / Paper 3 / 20H / Solution

Set $y=x_3+5$, so $y\ge 0$ and $y\le 10$. Introduce nonnegative slack and surplus variables $s_1,s_2,s_3$:The objective is $z=x_1+2x_2-6y+30$. A feasible simplex basis is $(x_2,s_1,s_3)$ with nonbasic variables $(x_1,s_2,y)=0$; its basic values are $(3,9,10)$. The initial simplex dictionary isIn the simplex algorithm, choose $s_2$ as the entering variable since it has positive objective coefficient. With the other nonbasic variables zero, only $s_1$ decreases; the simplex ratio test gives $s_2\le 18$. Thus $s_1$ leaves. Pivoting its row givesAll nonbasic variables are nonnegative, and all objective coefficients in the final dictionary are nonpositive, proving optimality. Setting them to zero gives $x_1=0$, $y=0$, $x_2=12$, henceThe surplus value is $s_2=18$, so the lower constraint is indeed satisfied, not mistakenly treated as equality at the optimum. The strict negative objective coefficients also show uniqueness of the optimizer.