Explanation
Welcome to The Factory Floor
A factory has limited machines, hours and money. How many of each product should it make to earn the most?
Linear programming turns that question into lines on a graph, and the best answer always sits at a corner.
Objective Z = ax + by (maximise or minimise) ·…
A linear programming problem has three parts: an objective Z to maximise or minimise, a few linear constraints, and the rule that x and y can't be negative.
Objective Z = ax + by (maximise or minimise) · linear constraints · x ≥ 0, y ≥ 0
Each constraint is a half-plane
Each inequality cuts the plane in half. Draw its boundary line, then test the origin.
If the origin satisfies the inequality, shade its side; if not, shade the other side.
Each constraint is a half-plane: draw the line, test (0, 0), shade the side that works
Feasible region = where all the constraints overlap
The feasible region is where every shaded half overlaps. Any point inside is a plan the factory can actually carry out.
Feasible region = where all the constraints overlap
Corner-point method
Here's the key fact: the best value of Z is always at a corner of the feasible region. So list every corner, put each into Z, and pick the largest or smallest.
Corner-point method: the optimum of a bounded region is at a corner · find all corners, evaluate Z
Two corners tie
If two corners give the same best value, every point on the edge joining them is also best. And if the region runs off to infinity, a minimum may still exist, but a maximum might not.
Two corners tie → every point on the edge between them is optimal · unbounded region → a maximum may not exist
Worked example
Maximise Z = 2x + 5y with x + y ≤ 5, x ≤ 3, x, y ≥ 0. The corners are (0, 0), (3, 0), (3, 2) and (0, 5), giving Z = 0, 6, 16 and 25.
The maximum is 25 at (0, 5).