Linear Programming (Graphical Method)

Linear programming (LP) is a method for optimising a linear objective function subject to linear constraints. The graphical method solves LP problems with two decision variables by plotting the constraints on a graph and finding the optimal point.

---

Formulating the Problem

An LP problem has three components:

Component	Description
Decision variables	The quantities to determine (e.g., $x$x, $y$y)
Objective function	The linear function to maximise or minimise (e.g., $P = 3x + 5y$P=3x+5y)
Constraints	Linear inequalities that the variables must satisfy

Non-negativity constraints

$x \geq 0$x≥0, $y \geq 0$y≥0 (unless stated otherwise).

Worked Example: Formulation

A factory makes chairs ($x$x) and tables ($y$y). Each chair requires 2 hours of carpentry and 1 hour of finishing. Each table requires 3 hours of carpentry and 2 hours of finishing. Available: 120 hours of carpentry, 80 hours of finishing. Profit: \pounds 30 per chair, \pounds 50 per table.

Objective: Maximise $P = 30x + 50y$P=30x+50y

Constraints:

• $2x + 3y \leq 120$2x+3y≤120 (carpentry)
• $x + 2y \leq 80$x+2y≤80 (finishing)
• $x \geq 0$x≥0, $y \geq 0$y≥0

---

The Graphical Method

Step 1: Plot each constraint as an equality (a straight line).

For $2x + 3y = 120$2x+3y=120: when $x = 0$x=0, $y = 40$y=40; when $y = 0$y=0, $x = 60$x=60.

For $x + 2y = 80$x+2y=80: when $x = 0$x=0, $y = 40$y=40; when $y = 0$y=0, $x = 80$x=80.

Step 2: Shade the feasible region.

The feasible region is the set of all points $(x, y)$(x,y) that satisfy all constraints simultaneously. For "≤" constraints, shade below/left of the line.

Step 3: Identify the vertices (corner points) of the feasible region.

Solve pairs of constraint equations simultaneously to find intersection points.

Vertex	Coordinates
O	(0, 0)
A	(60, 0)
B	intersection of $2x + 3y = 120$2x+3y=120 and $x + 2y = 80$x+2y=80
C	(0, 40)

For B: from $x + 2y = 80$x+2y=80, $x = 80 - 2y$x=80−2y. Substitute: $2(80 - 2y) + 3y = 120$2(80−2y)+3y=120, $160 - 4y + 3y = 120$160−4y+3y=120, $y = 40$y=40. Then $x = 0$x=0. Hmm, that gives the same as C.