Past exam of the mathematics course of the University of Cambridge / 2002 / ib / Paper 3 / 15H (Optimization)

Introduce surplus variables $s_1,s_2$, slack $s_3$, and artificial variables $a_1,a_2$, all nonnegative. The two-phase simplex standard-form equations arePhase I maximizes $w=-a_1-a_2$. An initial basic feasible solution has basic variables $(a_1,a_2,s_3)=(1,10,6)$ and all others zero. Its simplex dictionary isLet $x_1$ enter. The simplex ratio test gives $1$ from the $a_1$ row and $10/4$ from the $a_2$ row, so $a_1$ leaves. After this pivot,Choose $x_2$ to enter; the limiting ratios are $6/3=2$ and $6$, so $a_2$ leaves. The resulting dictionary isThus $\boxed{w_{\max }=0}$, attained at $(x_1,x_2,s_3)=(3,2,4)$ with $s_1=s_2=a_1=a_2=0$. Since $w\le 0$ for every feasible Phase I point, this proves feasibility and completes Phase I.

Delete the artificial variables and restore the original objective $z=-2x_1+3x_2$. The resulting Phase II dictionary isLet $s_2$ enter; only $s_3$ decreases, and it reaches zero at $s_2=12$. Pivoting givesAn optimal simplex tableau, with each row recording its equality, isBoth reduced costs in the maximization dictionary are negative. Setting nonbasic $s_1=s_3=0$ therefore givesAs a direct optimality check, $x_1\ge 1+x_2$ implies $z\le -2+x_2\le 4$; the displayed point attains both equalities.