Linear Programming
Linear Programming
The exam tests formulation of linear programming problems, graphical solution of two-variable problems, identification of the feasible region, and the corner point method for optimising an objective function.
Core rules
- Identify decision variables, the objective function Z = ax + by, and all constraints as linear inequalities, including non-negativity x ≥ 0, y ≥ 0.
- Graph each constraint; the feasible region is the intersection of all half-planes, usually a convex polygon.
- Corner point theorem: if the feasible region is bounded, the maximum and minimum of Z occur at corner points.
- Evaluate Z at every corner, then state the optimal point and value.
- For an unbounded feasible region, a maximum or minimum may not exist; check whether the objective can improve indefinitely.
Worked example
Maximise Z = 5x + 3y subject to x + y ≤ 4, x ≤ 3, x ≥ 0, y ≥ 0.
The corner points are (0,0), (3,0), (3,1) and (0,4). Values: Z(0,0)=0, Z(3,0)=15, Z(3,1)=15+3=18, Z(0,4)=12. The maximum is 18 at (3,1), which satisfies 3+1=4.
Traps
- Reversing an inequality when rearranging it.
- Omitting the non-negativity constraints and using points outside the first quadrant.
- Missing a corner where two boundary lines meet.
- Applying the corner point theorem without checking that the feasible region is bounded.
- Evaluating Z at an intersection that is not actually feasible.