Past exam of the mathematics course of the University of Cambridge 2005 ib Paper 3 20D c Solution Created 2026-09-24 Updated 2026-10-14
The dual constraints and objective coefficients on are unchanged, so remains dual feasible. Since every component of is positive, complementary slackness forces every constraint of any primal optimum paired with it to bind. Let be the original three-by-three constraint matrix and . It is invertible, and the only possible paired primal point isIf this point is nonnegative, it is primal feasible with zero slacks and , proving optimal. Conversely, if is optimal, linear programming duality supplies a paired primal optimum, and complementary slackness forces it to be exactly this point. This proves the strictly positive dual certificate and right-hand-side sensitivity criterion:Non-strict inequalities are essential: boundary cases can be degenerate but retain the same optimal dual vector. This is the complete range, not just a small-perturbation sufficient condition for linear programming sensitivity within a fixed optimal basis.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 37 2 b Solution Created 2026-10-03 Updated 2026-10-06
The same weak duality certificate gives the upper bound for every feasible point. Keep and solve the tight second and third constraints:These are nonnegative precisely when their numerators are nonnegative. The remaining first-constraint slack is . 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 , 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 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 it is infeasible. Thus the range is exact, not just a sufficient neighborhood.
In the usual linear programming sensitivity within a fixed optimal basis, retain the optimal basis while allowing its values to adjust. If the second resource amount is , thenThe dual prices remain , so optimality persists exactly while both basic variables are nonnegative:The optimal profit on that range is . At the endpoints the basis is degenerate but remains optimal. If the wording is instead read as requiring the exact numerical production vector to remain unchanged and optimal, only does so; the standard allowable range concerns the basis and its adjusted solution.