Past exam of the probability, statistics and options I course of the University of Oxford / 2009 / T / 1 (T1)

The entries in the two slack columns give the inverse basis matrixThus the ordered basic variables are $x_3,x_1$. Multiplying the original coefficient matrix and right-hand side by $B^{-1}$ gives the completed constraint rows. With the bottom row defined as reduced costs $c^T-c_B^T{B}^{-1}A$ and right-hand entry $-c_B^T{B}^{-1}b$, the complete tableau isThis bottom-right entry is the negative of the optimal objective under this row-operation convention. If a tableau records the positive objective value separately in that position, it is $26/3$; the completed constraint rows and reduced costs are the same.

Set the nonbasic variables $x_2,x_4,x_5$ to zero. The two constraint rows giveAll nonbasic reduced costs are negative, so increasing any of them would decrease the objective. The basic solution is feasible and therefore optimal.

The basis and reduced costs stay unchanged when only the right-hand side changes. Its new basic values areThus for small $|\alpha |$,

The unchanged reduced costs remain optimal for a maximization problem. The new basic solution is feasible exactly when $2-\alpha \ge 0$ and $14+2\alpha \ge 0$. ThereforeThe endpoints are included: one basic variable then vanishes, but feasibility and the reduced-cost certificate remain valid.

Suppose the unique optimum $x^{\ast }$ were $(1-t)u+tv$ for distinct feasible points $u,v$ and $0<t<1$. Feasibility is preserved by convex combinations. Optimality gives $c^{T}u\le c^T{x}^{\ast }$ and $c^{T}v\le c^T{x}^{\ast }$, while linearity gives their strictly weighted average equal to $c^T{x}^{\ast }$. Both inequalities must therefore be equalities. Then $u$ and $v$ are also optimal, contradicting uniqueness. Hence the unique optimum is an extreme point of the feasible set.