Consider the linear programme: maximise $Z=6x+9y$ subject to $2x+y\le 30$, $x+3y\le 36$, $x,y\ge 0$. The optimal solution is $x=9$, $y=4$. Find the range of permissible change in the right‑hand side of the first constraint (i.e., in the constant 30) so that the current basis remains optimal.

Step-by-step solution

1. Identify the binding constraints at the optimal point $(9,4)$. Substituting, $2(9)+4=22\le 30$ (non‑binding) and $9+3(4)=21\le 36$ (non‑binding). Both constraints are slack; however, the basis corresponds to the non‑negativity constraints $x\ge 0$, $y\ge 0$.
2. Form the simplex tableau for the given LP and note the basic variables at optimality (here $x$ and $y$ are basic).
3. Compute the shadow price (dual value) for the first constraint: solve the dual or use the final tableau; the dual coefficient for the first constraint is ${\lambda }_1=0$ because the constraint is non‑binding.
4. When a dual coefficient is zero, the RHS can change without affecting optimality as long as the constraint does not become binding.
5. Find the values of the RHS that would make the first constraint binding at the current solution: set $2x+y=RHS$, substitute $x=9$, $y=4$ to get $2(9)+4=22$. Hence RHS can be reduced to $22$ before the constraint becomes active.
6. Similarly, increase RHS until another constraint becomes limiting. The second constraint becomes binding when $x+3y=RH{S}_2$, which at $(9,4)$ equals $21$ (already less than 36), so increasing the first RHS does not affect feasibility until the first constraint reaches $2(9)+4=22$ plus the slack originally present ($30-22=8$). Thus the RHS can increase by the existing slack, i.e., up to $30+8=38$, but the second constraint will bind first at $x+3y=36$ when $y$ grows; solving with $x=9$ gives $y=9$, which would require the first constraint to be $2(9)+9=27$. Hence the upper limit is $33$ to keep $y$ ≤4.
7. Combining lower and upper limits, the permissible range is $27\le RHS\le 33$.
8. State the final range.

Concept tested: Sensitivity analysis of RHS

Published 8 September 2026 · How this solution was prepared and checked