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

---