Maximise (or minimise) a linear objective subject to linear inequality constraints. The optimum sits at a corner of the feasible region.
Graph
y = 4 - x
Solving a linear program
- Graph each constraint as a line; the feasible region is where all the shaded half-planes overlap.
- The plotted line y = 4 − x is the constraint x + y ≤ 4 — feasible points lie on or below it (and with x, y ≥ 0).
- The optimum of a linear objective always sits at a corner of the feasible region.
- Evaluate the objective at every corner and pick the best.
Your turn
Maximise z = 3x + 2y over x + y ≤ 4, x ≥ 0, y ≥ 0.
Recap
- Objective and constraints are all linear.
- Feasible region = intersection of the constraint half-planes.
- Test the corners — one of them is optimal.
Try it
Maximise z = 3x + 2y subject to x+y ≤ 4, x,y ≥ 0
Corners: (0,0), (4,0), (0,4). z values: 0, 12, 8. Max at (4, 0): z = 12.