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

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.

The feasible triangle has verticesThese come from the three pairs of active boundary lines and satisfy the remaining inequalities. Its denominator $3x_1+x_2+2$ is positive at each vertex, with minimum $12/5$, so is positive throughout the triangle because it is an affine function.

For a direct linear programming optimality certificate, add twice the second inequality to the third to get $-x_1-3x_2\le 2$. Thus $x_1+3x_2+2\ge 0$, equivalently $2(x_1-x_2)\le 3x_1+x_2+2$. Division by the positive denominator gives an objective at most $1/2$. Both inequalities used in the bound are equalities at $v_3$, where the first inequality is also satisfied. ThereforeEquality requires the two bounding inequalities to be tight, so this optimizer is unique.