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

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$.

Let $(y,t)$ be feasible for $R$. Since $d_i>0$ and $d^{T}y=1$, the vector $y$ is nonzero. Every entry of $A$ is strictly positive and $y\ge 0$, so every component of $Ay$ is strictly positive. The relationtherefore forces $t>0$.

Set $x=y/t$. Thenso $x$ is feasible for $Q$, andThus every feasible value of $R$ is a feasible value of the linear-fractional program $Q$. Together with part (i), this proves

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$,