Past exam of the mathematics course of the University of Cambridge / 2021 / ib / Paper 4 / 18H / c / iii / Solution

Let $(y,t)$ be a basic feasible solution of $R$. Part (ii) gives $t>0$, and put $x=y/t$. We already know that $x$ is feasible for $P$.

Suppose the columns $A_i$ with $y_i>0$ were linearly dependent. Then some nonzero $h$, supported on those indices, would satisfy $Ah=0$. PutSince $d^{T}y=1$ and $Ay=bt$,The vector $(\delta y,\delta t)$ is nonzero and is supported only on positive variables of $(y,t)$. It is therefore a linear dependence among the active constraint columns of $R$, contradicting that $(y,t)$ is basic. Hence the active columns $A_i$ are linearly independent, and

By the Fundamental theorem of linear programming, $R$ has an optimal basic feasible solution. Its image $x\in \mathcal{B}$ has the same objective ratio, by part (ii). Conversely, every $x\in \mathcal{B}$ is feasible for $Q$ and maps to a feasible point of $R$. Since $x^{\ast }$ solves $Q$,

Solved by gpt-5.6-sol high.