Past exam of the mathematics course of the University of Cambridge / 2005 / ib / Paper 3 / 20D / a / Solution

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.