= Solution
Continue the <simplex algorithm> using dictionaries, with nonbasic variables zero at the current vertex. The given basis has payoff
$$
f=\frac{116}{9}+\frac{17}{9}x_2-\frac{121}{9}x_3-\frac49z_3.
$$
Thus $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,
$$
\begin{aligned}x_2&=11+11x_3-z_1,\\z_2&=11-11x_3+\tfrac43z_1-\tfrac13z_3,\\x_1&=\tfrac{17}3+\tfrac43x_3-\tfrac29z_1-\tfrac19z_3,\\f&=\tfrac{101}3+\tfrac{22}3x_3-\tfrac{17}9z_1-\tfrac49z_3.\end{aligned}
$$
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 is
$$
\boxed{\begin{aligned}x_1&=7-\tfrac2{33}z_1-\tfrac4{33}z_2-\tfrac5{33}z_3,\\x_2&=22+\tfrac13z_1-z_2-\tfrac13z_3,\\x_3&=1+\tfrac4{33}z_1-\tfrac1{11}z_2-\tfrac1{33}z_3,\\f&=41-z_1-\tfrac23z_2-\tfrac23z_3.\end{aligned}}
$$
All reduced payoff coefficients are nonpositive. Since the slacks must be nonnegative, $f\leq41$, attained with $z=0$. Hence $\boxed{x^*=(7,22,1),\quad f^*=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.
Back to article page
