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

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.