Past exam of the mathematics course of the University of Cambridge / 2019 / ib / Paper 3 / 21H (Optimisation)

Choose a set $B$ of $m$ column indices for which the square matrix $A_B$ is invertible. The associated basic solution sets $x_j=0$ for $j\notin B$ and solves $A_B{x}_B=b$. It is a basic feasible solution when all its coordinates are nonnegative.

Let $x$ be a basic feasible solution with basis $B$. If $x=(y+z)/2$ for $y,z\in X(b)$, then $x_j=0$ and nonnegativity force $y_j=z_j=0$ for every $j\notin B$. Since $A_B{y}_B=A_B{z}_B=b$ and $A_B$ is invertible, $y=z=x$. Thus $x$ is an extreme point.

Conversely, let $x$ be extreme and let $S=\{j:x_j>0\}$. If $|S|>m$, the corresponding columns are linearly dependent, so there is a nonzero vector $d$ supported on $S$ with $Ad=0$. For sufficiently small $\epsilon >0$, both $x+\epsilon d$ and $x-\epsilon d$ remain nonnegative and feasible, contradicting extremality. Hence $|S|\le m$. Enlarge $S$ to a set $B$ of $m$ indices. By the hypotheses $A_B$ is invertible, and $x$ is the resulting basic feasible solution. Therefore

Introduce slack variables $s_1,s_2,s_3\ge 0$ after rewriting the third inequality as $x_1-x_2+x_3\le 2$. The initial dictionary isIn the simplex method, $x_3$ enters first because it has the largest positive objective coefficient. The ratio test makes $s_3$ leave, and substitution givesNext $x_2$ enters and $s_2$ leaves. Solving for $x_2$ produces the final objective rowAll reduced costs are now nonpositive, so the dictionary is optimal at the nonbasic values $x_1=s_2=s_3=0$. ThereforeThe first constraint has slack $s_1=56/5$, while the second and third constraints are active.