Past exam of the Probability, statistics and options II course of the University of Oxford / 2007 / T / 2 / b

Introduce nonnegative slack variables $s_1,s_2$ and use a simplex tableau with the last row representing $z-c^{\mathsf{T}}x=0$. The starting tableau isEnter $x_3$ and let $s_2$ leave. Dividing the second row by three and eliminating its column givesEnter $x_1$ and let $s_1$ leave. The next simplex tableau isThusThe pivot choices and the optimality certificate are justified in the following parts.

For this tableau sign convention, a negative coefficient in the objective row means the corresponding nonbasic variable can increase profit. Initially $x_3$ has the most negative coefficient. The simplex ratio test gives $33/5$ in row one and $18/3=6$ in row two, so row two leaves to preserve feasibility. Next $x_1$ is the only column with a negative objective coefficient. The ratios are $3/(1/3)=9$ and $6/(1/3)=18$, so row one leaves. All resulting basic variables remain nonnegative.

The last objective row is $z+x_2+s_1+s_2=51$. Every feasible solution has nonnegative $x_2,s_1,s_2$, so $z\le 51$. The displayed basic feasible solution has all three zero and attains 51, proving optimality. Equivalently, the resource dual prices $(1,1)$ give the same upper bound $33+18=51$ and satisfy complementary slackness.