Past exam of the mathematics course of the University of Cambridge / 2021 / ib / Paper 4 / 18H (Optimisation)

A vector $x$ is a basic feasible solution whenand the columns $A_i$ for which $x_i>0$ are linearly independent. Equivalently, after extending those columns to a basis of the column space of $A$, one sets all nonbasic variables to zero and solves for the basic variables, obtaining a nonnegative vector.

Choose an optimal feasible vector $x$ having as few positive coordinates as possible, and letIf the columns $(A_i{)}_{i\in S}$ were linearly dependent, there would be a nonzero vector $h$, supported on $S$, such that $Ah=0$. For all sufficiently small positive $\epsilon$, bothwould remain feasible.

If $c^{T}h\ne 0$, one of these two perturbations would increase the objective, contradicting optimality. Hence $c^{T}h=0$. We may then increase $\epsilon$ in one of the two directions until at least one positive coordinate first becomes zero. The resulting vector is still feasible and optimal but has smaller positive support, contradicting the choice of $x$.

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