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

Use the original PDF constraints, whose right sides are $8$ and $9$. Introduce nonnegative surplus variables $s_1,s_2$, slack $s_3$, and artificial variables $a_1,a_2$:All seven variables are nonnegative. Phase I of the two-phase simplex method minimizes $w=a_1+a_2$ with initial basis $(a_1,a_2,s_3)$. The initial simplex dictionary isEnter $x_2$ and leave $a_2$: the ratio test gives $\min (8,9/3)=3$. Substituting $x_2=3-x_1/3+s_2/3-a_2/3$ givesNow enter $x_1$ and leave $a_1$. The bounds from $a_1,x_2,s_3$ are $3,9,6$, so the ratio test selects $3$. The new dictionary isThe associated basic solution has $a_1=a_2=0$ and $w=0$, which is a global minimum because artificial variables are nonnegative. Delete their columns for Phase II. In the remaining basis $(x_1,x_2,s_3)$ the objective isFor $2\le p\le 9/4$, both reduced costs are nonnegative, so the simplex method has reached the optimum at $(x_1,x_2)=(3,2)$:For $9/4<p\le 3$, the coefficient of $s_1$ is negative. Enter $s_1$; the ratio test gives $10$ from $x_2$ and $5$ from $s_3$, so $s_3$ leaves. Eliminating $s_1$ givesand henceThe two reduced costs are now positive, so $(6,1)$ is optimal andAt $p=9/4$ the whole feasible edge from $(3,2)$ to $(6,1)$ is optimal; both value formulas agree. These dictionaries explicitly carry out both phases rather than inferring the answer solely from a feasible-region sketch.