Linear Programming and Optimization
This domain tests formulation and solution of constrained optimisation problems. You must translate words into an objective and inequalities, then solve graphically or interpret slack and shadow prices.
Core rules
- Define decision variables with units.
- Objective: maximise contribution or minimise cost, written as a linear function.
- Constraints: resource limits, minimum requirements, and non-negativity x, y ≥ 0.
- Plot each constraint as an equality; the feasible region satisfies all inequalities.
- The optimal solution of a linear programme lies at a corner of the feasible region; evaluate the objective at each corner.
- Slack is unused resource in a ≤ constraint; surplus is excess in a ≥ constraint. A binding constraint has zero slack.
- The shadow price is the change in the objective from a one-unit increase in a binding constraint's right-hand side, valid within its range.
Worked example
Maximise 30x + 40y subject to 2x + y ≤ 100, x + 2y ≤ 80, x, y ≥ 0. Intercepts give corners (0,0), (50,0), (0,40), and the intersection of 2x + y = 100 and x + 2y = 80. Solving: y = 100 − 2x; x + 2(100 − 2x) = 80 → −3x = −120 → x = 40, y = 20. Objective values: 0, 1,500, 1,600, and 30×40 + 40×20 = 2,000. Maximum is 2,000 at (40, 20). Both constraints are binding because 2(40) + 20 = 100 and 40 + 2(20) = 80.
Traps
- Reversing an inequality when reading the feasible side.
- Forgetting non-negativity.
- Testing only intercepts and missing the intersection.
- Treating a shadow price as valid for any size of change.
- Using graphical solutions with three variables.