Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 35 / 2

Introduce nonnegative slack variables $s_1,s_2$ and let $z$ denote profit. We display each simplex tableau as coefficients of its row equation, with the coefficient of $z$ in the objective equation implicitly one. Thus a negative coefficient in the last row permits an improving entering variable. The initial simplex tableau isUse the simplex method with $x_2$ entering. The simplex ratio test gives ratios $6/2=3$ and $6/1=6$, so $s_1$ leaves. Divide its row by two and eliminate the other $x_2$ entries:Next $x_1$ enters. The positive-column ratios are $3/(1/2)=6$ and $3/(3/2)=2$, so $s_2$ leaves. After this pivot and a row reordering,The last row is $z=14-(5/3)s_1-(2/3)s_2$, so every nonnegative feasible solution has $z\le 14$. Setting the nonbasic variables to zero givesThe equality certificate also shows uniqueness, since both nonbasic objective coefficients are strictly unfavorable.

Add the slack variable $s_3$ for the forgotten constraint. In the optimal simplex tableau from part (a), $x_1+x_2=4-(s_1+s_2)/3$. Hence the new row in canonical form isAppending it givesThe objective row remains dual feasible, but $s_3=-1$ makes the basic solution infeasible. Apply the dual simplex algorithm: $s_3$ leaves, and the eligible columns are $s_1,s_2$, whose negative coefficients can repair this row. The dual ratio test comparesThus $s_2$ enters. Pivoting on $-4/3$ and eliminating its column givesAll basic values are nonnegative and the objective equation is $z=27/2-s_1-s_3/2$. ThereforeBoth binding constraints have zero slack, and the final objective row proves global optimality. The two nonbasic penalties are strictly positive, so this optimum is unique.

The old slack variable $s_3$ is exactly the amount now sold, so rename its column $y$. No further slack is added: the PDF specifies an equality. The feasible equations are otherwise unchanged. If $z_0$ is the old profit, the new profit is $z=z_0+y$. Substituting this into the old objective equation givesThis is the simplex objective update for a priced slack variable. The altered simplex tableau isThe coefficient $-1/2$ makes $y$ an improving entering variable. Its only positive constraint-row coefficient is $1/2$ in the $x_1$ row, whose ratio is $(3/2)/(1/2)=3$. Thus $x_1$ leaves. The simplex method pivot givesThe objective equation $z=15-x_1$ proves optimality. One optimal basic solution isThe zero reduced cost of $s_1$ permits alternative optima. In fact all optimal solutions areThese satisfy both remaining inequalities, and the equality then makes their profit exactly fifteen.