What Is Linear Programming?
Linear programming (LP) is a method for finding the maximum or minimum value of a linear function when the variables must satisfy a set of linear inequalities. The function being optimised is the objective function, the inequalities are the constraints, and the region of all points that satisfy every constraint is the feasible region. "Linear" means every relationship is a straight line or plane — no squares, no products of variables.
Every linear programming problem has three parts:
Decision variables — the quantities you control, such as how many units of each product to make ($x$ and $y$).
Objective function — the linear expression to maximise or minimise, for example $Z = 8x + y$.
Constraints — the linear inequalities that limit the variables, plus the non-negativity constraints $x \geq 0$, $y \geq 0$.
Key Terms in Linear Programming
Define each term before using it, because the graphical method leans on all of them at once.
Feasible region: the set of all points $(x, y)$ that satisfy every constraint simultaneously, i.e. the overlap of all the shaded half-planes.
Feasible solution: any point inside or on the boundary of the feasible region.
Corner point (vertex): a point where two boundary lines of the feasible region meet.
Optimal solution: the feasible point that gives the best (largest or smallest) value of the objective function.
Bounded / unbounded region: a feasible region enclosed on all sides is bounded; one that stretches to infinity in some direction is unbounded.
The single most important fact: the optimal solution, when it exists, always occurs at a corner point of the feasible region. This is why the graphical method only tests corners, not every point inside the region.
How to Solve a Linear Programming Problem Graphically
The graphical method works when there are exactly two decision variables, so the feasible region can be drawn on a plane.
Write the objective function and list all constraints, including non-negativity.
Convert each constraint inequality to a line and plot it.
Shade the half-plane each inequality allows; the overlap is the feasible region.
Find the coordinates of every corner point (solve pairs of boundary lines where needed).
Evaluate the objective function at each corner point.
Pick the corner with the best value — the largest for a maximisation, the smallest for a minimisation.
Building the feasible region correctly depends on plotting the boundary lines accurately — the same skill as graphing linear equations.
Examples of Linear Programming
Example 1
Maximise $Z = 8x + y$ subject to $x + y \leq 40$, $2x + y \leq 60$, $x \geq 0$, $y \geq 0$.
Find the corner points of the feasible region:
$$(0, 0), \quad (0, 40), \quad (30, 0)$$
The intersection of $x + y = 40$ and $2x + y = 60$: subtract to get $x = 20$, $y = 20$, giving $(20, 20)$.
Evaluate $Z = 8x + y$ at each corner:
$$Z(0,0) = 0$$ $$Z(0,40) = 40$$ $$Z(20,20) = 160 + 20 = 180$$ $$Z(30,0) = 240 + 0 = 240$$
The largest value is at $(30, 0)$.
Final answer: Maximum $Z = 240$ at $(30, 0)$.
Example 2
Minimise $Z = 3x + 5y$ subject to $x + y \geq 4$, $x + 3y \geq 6$, $x \geq 0$, $y \geq 0$ (with a wrong path shown first).
The tempting shortcut is to test the origin $(0, 0)$ because it gives the smallest objective value, $Z = 0$. Watch how that goes wrong: $(0,0)$ does not satisfy $x + y \geq 4$, so it is not in the feasible region. A point that breaks a constraint cannot be the answer, no matter how small its $Z$ value.
Now the correct way — find the feasible corner points:
$$(6, 0), \quad (0, 4)$$
The intersection of $x + y = 4$ and $x + 3y = 6$: subtract to get $2y = 2$, so $y = 1$, $x = 3$, giving $(3, 1)$.
Evaluate $Z = 3x + 5y$ at each feasible corner:
$$Z(6,0) = 18$$ $$Z(3,1) = 9 + 5 = 14$$ $$Z(0,4) = 20$$
Final answer: Minimum $Z = 14$ at $(3, 1)$.
Example 3
A bakery makes cakes ($x$) and pastries ($y$). Each cake needs 2 hours, each pastry 1 hour, with 8 hours available; material limits give $x + y \leq 5$. Profit is $Z = 30x + 20y$. Maximise profit.
Constraints: $2x + y \leq 8$, $x + y \leq 5$, $x \geq 0$, $y \geq 0$.
Corner points: $(0,0)$, $(4,0)$, $(0,5)$, and the intersection of $2x + y = 8$ with $x + y = 5$, which gives $x = 3$, $y = 2$, i.e. $(3,2)$.
Evaluate $Z = 30x + 20y$:
$$Z(0,0) = 0$$ $$Z(4,0) = 120$$ $$Z(3,2) = 90 + 40 = 130$$ $$Z(0,5) = 100$$
Final answer: Maximum profit $Z = 130$ at $(3, 2)$, i.e. three cakes and two pastries.
Example 4
Check whether the point $(2, 3)$ is feasible for the constraints $x + y \leq 4$, $x \geq 0$, $y \geq 0$.
Test the point in each constraint:
$$x + y = 2 + 3 = 5 \not\leq 4$$
The point fails the first constraint, so it is not feasible.
Final answer: $(2, 3)$ is not a feasible solution.
Example 5
Maximise $Z = x + 2y$ subject to only $x \geq 0$, $y \geq 0$ (no upper bound).
With no upper limit on $x$ or $y$, the feasible region stretches to infinity, and $Z$ can grow without bound.
Final answer: The problem is unbounded — no finite maximum exists.
Example 6
Find the corner point where $3x + 2y = 12$ meets $x + 2y = 8$.
Subtract the second equation from the first:
$$(3x + 2y) - (x + 2y) = 12 - 8$$ $$2x = 4 \implies x = 2$$
Substitute back into $x + 2y = 8$:
$$2 + 2y = 8 \implies y = 3$$
Final answer: The corner point is $(2, 3)$.
Why Linear Programming Matters: "The best plan lives at a corner"
Linear programming was developed in the 1940s to plan the movement of supplies and troops — problems with too many possible allocations to check by hand. The breakthrough was proving that the optimum of a linear objective over a convex feasible region always sits at a vertex, so a computer need only test the corners.
Business uses LP to maximise profit or minimise cost under limited labour, material, and budget.
Logistics uses it to route deliveries and schedule shipments at least cost.
Diet and nutrition planning uses it to meet nutrient requirements at minimum price.
The destination is the same corner-point guarantee applied to problems with dozens of variables, solved by the simplex algorithm. The two-variable graphical method you learn here is the picture that explains why the algorithm works — see inequalities for the half-plane idea it rests on.
What Are the Most Common Mistakes With Linear Programming?
Mistake 1: Testing points that are not corners of the feasible region
Where it slips in: Evaluating the objective function at any line intersection, feasible or not.
Don't do this: Using the intersection of two constraint lines that lies outside the feasible region as a candidate.
The correct way: Only intersections that satisfy every constraint are corner points. Check each candidate against all constraints before evaluating $Z$. Students first solving LP problems tend to plug in every intersection they find; verifying feasibility first fixes it.
Mistake 2: Forgetting the non-negativity constraints
Where it slips in: Formulating the feasible region without $x \geq 0$, $y \geq 0$.
Don't do this: Allowing negative quantities, which produces corner points in the wrong quadrant.
The correct way: Real quantities — units produced, hours worked — cannot be negative, so always include $x \geq 0$ and $y \geq 0$. These lines are part of the feasible-region boundary.
Mistake 3: Missing an unbounded or infeasible case
Where it slips in: Assuming every problem has a single finite answer.
Don't do this: Reporting a maximum for a region that stretches to infinity, or a solution when the constraints have no common region.
The correct way: If the feasible region is unbounded in the direction the objective grows, the problem has no finite optimum; if no point satisfies all constraints, the problem is infeasible.
This is the same failure that stalled early wartime supply-planning models before the theory was complete — a plan that looked optimal on paper turned out to violate a resource limit that had been left out of the feasible region entirely. Always confirm the region is bounded and non-empty first.
Conclusion
Linear programming optimises a linear objective function under linear constraints.
The feasible region is the overlap of all constraints, including non-negativity.
The optimum always occurs at a corner point of the feasible region.
The graphical method (two variables): plot constraints, find corners, evaluate $Z$ at each, pick the best.
Watch for unbounded and infeasible problems, and always keep the non-negativity constraints.
To work through formulating and solving LP problems with a teacher, explore Bhanzu's algebra tutor or a high school math tutor, supported by structured math classes online.
Read More
Was this article helpful?
Your feedback helps us write better content