Past exam of the mathematics course of the University of Cambridge / 2006 / ib / Paper 4 / 20C / Solution

Use two-phase simplex to handle the constraint of the opposite inequality direction. Introduce nonnegative slack variables $s_1,s_2$, a surplus variable $s_3$, and an artificial variable $a$. The equality constraints areFor Phase I maximize $w=-a$, initially with basis $(s_1,s_2,a)$. Its initial simplex dictionary isChoose $x_1$ to enter. The simplex ratio test compares $30$, $35/2$ and $40$, so $s_2$ leaves. The new dictionary isSince $w=-45/2+(5/2)x_2-x_3-s_2/2-s_3$, choose $x_2$ to enter. Its limiting ratios are $25/3$ from $s_1$ and $9$ from $a$, so $s_1$ leaves. This givesNow $w=-5/3-(8/3)x_3+s_2/3-(5/3)s_1-s_3$, so let $s_2$ enter. Its limiting ratios are $65$ from $x_1$ and $5$ from $a$; the artificial variable leaves. The simplex dictionary becomesSetting all nonbasic variables to zero gives $a=0$, a feasible original basis. Since $-a\le 0$, Phase I is optimal with value zero; delete $a$.

For Phase II the original objective in this basis isAll nonbasic reduced costs are strictly negative, so no further improving simplex pivot exists. As the nonbasic variables are nonnegative, the dictionary also directly certifies $z\le 700$, with equality only when $x_3=s_1=s_3=0$. ThereforeThe second original constraint has slack five and the other two are tight. As an independent linear programming optimality certificate, multiply the first constraint by $130$ and the third, after reversing it, by $80$. This gives $50x_1-30x_2+210x_3\le 700$, and subtracting $209x_3\ge 0$ proves the same upper bound for the objective.