Linear Programming: Objective, Constraints & Graph Method

TL;DR

Linear programming finds the best value of a linear objective function subject to linear constraints, and the optimum always sits at a corner (vertex) of the feasible region. This article defines each term, walks through formulating a problem, and solves a two-variable problem with the graphical corner-point method, plus common mistakes.

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 (xxx and yyy).
• 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≥0, y≥0.

Key Terms in Linear Programming

• Feasible region: the set of all points (x,y) that satisfy every constraint simultaneously.
• 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.

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.

1. Write the objective function and list all constraints, including non-negativity.
2. Convert each constraint inequality to a line and plot it.
3. Shade the half-plane each inequality allows; the overlap is the feasible region.
4. Find the coordinates of every corner point (solve pairs of boundary lines where needed).
5. Evaluate the objective function at each corner point.
6. 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.

Examples of Linear Programming

Example 1

Maximise Z=8x+y subject to x+y≤40, 2x+y≤60, x≥0, y≥0.

Find the corner points of the feasible region:

(0,0), (0,40), (30,0)

Evaluate Z at each corner:

Z(0,0)=0, Z(0,40)=40, Z(20,20)=180, Z(30,0)=240

Final answer: Maximum Z=240 at (30,0).

Example 2

Minimise Z=3x+5y subject to x+y≥4, x+3y≥6, x≥0, y≥0.

The correct way — find the feasible corner points:

(6,0), (0,4)

Evaluate Z at each feasible corner:

Z(6,0)=18, Z(3,1)=14, Z(0,4)=20

Final answer: Minimum Z=14 at (3,1).

Example 3

A bakery makes cakes (xxx) and pastries (yyy). Maximise profit Z=30x+20y subject to constraints.

Corner points: (0,0), (4,0), (0,5), (3,2)

Evaluate Z:

Z(0,0)=0, Z(4,0)=120, Z(3,2)=130, Z(0,5)=100

Final answer: Maximum profit Z=130 at (3,2).

Example 4

Check whether the point (2,3) is feasible for the constraints x+y≤4, x≥0, y≥0.

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≥0, y≥0.

Final answer: The problem is unbounded — no finite maximum exists.

Example 6

Find the corner point where 3x+2y=12 meets x+2y=8.

Final answer: The corner point is (2,3).

Why Linear Programming Matters: "The best plan lives at a corner"

Linear programming optimises a linear objective under linear constraints, relevant in business, logistics, and nutrition planning. The optimum generally occurs at a corner point of the feasible region.

What Are the Most Common Mistakes With Linear Programming?

1. Testing points that are not corners of the feasible region.
2. Forgetting the non-negativity constraints.
3. Missing an unbounded or infeasible case.

Conclusion

• Linear programming optimises a linear objective function under linear constraints.
• The feasible region is the overlap of all constraints.
• The optimum occurs at a corner point of the feasible region.
• The graphical method helps visualise these solutions for two-variable problems.