Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 37 / 1 / a

Use the Charnes-Cooper transformation on the positive-denominator region:It gives $Ay\le bt$, $d^{T}y+\beta t=1$ and $c^{T}y+\alpha t=(c^{T}x+\alpha )/(d^{T}x+\beta )$.

We must check that allowing $t=0$ introduces no false feasible solution. If $t=0$, then $Ay\le 0$. The recession cone of the nonempty linear polyhedron $P=\{x:Ax\le b\}$ is $\{y:Ay\le 0\}$. Indeed for $x_0\in P$, $x_0+uy\in P$ for every $u\ge 0$. Boundedness of $P$ therefore forces $y=0$, contradicting $d^{T}y=1$. Thus every transformed feasible point has $t>0$.

Conversely set $x=y/t$. The constraints give $x\in P$ and $d^{T}x+\beta =1/t>0$, with the same objective value. The assumed original optimizer with positive denominator supplies a transformed feasible point. Every transformed point corresponds to an original point and has objective at most that optimizer's value. Hence the transformed linear program attains the original optimum, and its optimizer recovers $x=y/t$. Positivity on every point of $P$ is not needed here; the given positive-denominator optimum suffices.