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

Apply the Charnes-Cooper transformation to any feasible point $x$ of $Q$:Thenso $(y,t)$ is feasible for $R$, andIn particular, the given solution $x^{\ast }$ of $Q$ produces a feasible point of $R$ with the same objective value, so

Moreover, because every $d_i>0$, the equation $d^{T}y=1$ impliesThe linear objective $c^{T}y$ is therefore bounded on the feasible set. The feasible $y$ lie in the compact simplex $\{y\ge 0:d^{T}y=1\}$. Their subset arising in $R$ is closed: if $b\ne 0$, any nonzero component of $b$ determines $t$ continuously from $Ay=bt$, while if $b=0$ the condition is simply $Ay=0$. Hence the feasible $y$ form a compact set, on which the continuous objective $c^{T}y$ attains a finite maximum. Thus $R$ has a finite maximum at least as large as that of $Q$.

Solved by gpt-5.6-sol high.