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

The feasible point $x=(8/5,0,1/5)$ makes the second and third constraints tight; the first has left side two. Its objective is $27/5$.

To prove optimality from first principles, multiply each of the second and third inequalities by $3/5$ and add. For every nonnegative feasible $x$,This is an explicit weak duality bound, proved here simply by adding inequalities. The displayed point attains it, soEquality forces $x_2=0$ and both contributing constraints tight, proving uniqueness as well.

The same weak duality certificate gives the upper bound $(27+3{ϵ}_2+3{ϵ}_3)/5$ for every feasible point. Keep $x_2=0$ and solve the tight second and third constraints:These are nonnegative precisely when their numerators are nonnegative. The remaining first-constraint slack is $4+{ϵ}_1-{ϵ}_3/2$. All three are positive for sufficiently small perturbations, so the point is feasible and attains the bound. This illustrates linear programming sensitivity within a fixed optimal basis:More generally this expression is valid throughout the region specified by those three feasibility inequalities.

With ${ϵ}_1={ϵ}_2=0$, the conditions reduce toThe endpoints are included. Outside this interval the bound cannot be attained: its equality conditions require exactly the point above, which then has a negative $x_3$ or violates the first constraint. Whenever feasible, the problem attains a maximum because the first constraint and nonnegativity bound all coordinates, so its value is strictly smaller outside the interval. For ${ϵ}_3<-4$ it is infeasible. Thus the range is exact, not just a sufficient neighborhood.