Welcome to Linear Programming
Imagine you run a small business making two types of custom skateboards: standard boards and pro boards. You want to make as much profit as possible, but you only have a set amount of wood, a limited number of wheels, and a fixed number of hours each week. How do you decide exactly how many of each board to produce?
This is where Linear Programming comes in! It is a powerful mathematical method used in business, engineering, and logistics to find the best possible outcome (such as maximising profit or minimising cost) under a given set of restrictions.
In Unit 4 (Discrete and Decision Mathematics) of CCEA GCSE Further Mathematics, you will learn how to turn word problems into algebraic inequalities, plot them on a graph, identify the valid region, and pinpoint the optimal solution.
1. Key Terminology & Definitions
Before jumping into solving problems, let us look at the fundamental building blocks of linear programming:
• Decision Variables: The unknown quantities you want to find. In this unit, these are usually represented by \(x\) and \(y\) (for example, \(x = \text{number of standard boards}\) and \(y = \text{number of pro boards}\)).
• Objective Function: The linear expression that you want to optimise. If you want to maximise profit, it might look like \(P = ax + by\). If you want to minimise cost, it is often written as \(C = ax + by\), where \(a\) and \(b\) are given numerical values.
• Constraints: The limitations or restrictions on resources (such as time, materials, or budget). These are expressed algebraically as a system of linear inequalities (e.g. \(2x + 3y \le 60\)).
• Non-Negativity Constraints: Real-world physical items cannot exist in negative amounts. Therefore, almost every practical problem includes the conditions \(x \ge 0\) and \(y \ge 0\). These restrict our working area to the first quadrant of the Cartesian plane.
• Feasible Region (FR): The region on the graph containing all points \((x, y)\) that satisfy all the constraints at the same time. In CCEA exams, this region is usually labelled \(R\) or \(\text{FR}\).
• Optimal Solution: The coordinate pair \((x, y)\) within or on the boundary of the feasible region that gives the absolute maximum (or minimum) value of the objective function.
Quick Review: The goal of linear programming is to find the best point in the feasible region that makes the objective function as large (or small) as possible while obeying all constraints.
2. Formulating a Problem from Words
Don't worry if word problems feel overwhelming at first. You can always break the formulation process down into three manageable steps:
Step-by-Step Formulation Process
Step 1: Define the Decision Variables
Always write down clearly what \(x\) and \(y\) stand for. For example:
"Let \(x\) be the number of standard units made."
"Let \(y\) be the number of deluxe units made."
Step 2: Write the Objective Function
Identify what is being maximised or minimised, and state whether it is a profit or a cost. For example:
\(\text{Maximise } P = 40x + 30y\)
Step 3: Write Down the Constraints
Translate the limits given in the question into inequalities. Look out for the non-negativity conditions (\(x \ge 0, y \ge 0\)) as well as resource limits.
Decoding Word Clues into Inequality Signs
Misreading words is one of the most common mistakes in exams. Use this translation guide:
• "At least" or "not less than" means: \(\ge\)
• "At most" or "no more than" means: \(\le\)
• "A maximum of" means: \(\le\)
• "A minimum of" means: \(\ge\)
• "Must exceed" or "strictly greater than" means: \(>\)
Worked Example: Formulation
A baker makes two types of cakes: Sponge cakes (\(x\)) and Fruit cakes (\(y\)).
- Each sponge cake requires \(200\text{ g}\) of flour and takes \(1\) hour to bake.
- Each fruit cake requires \(400\text{ g}\) of flour and takes \(3\) hours to bake.
- The baker has \(2400\text{ g}\) of flour and \(15\) hours of baking time available.
- The profit is £\(4\) on a sponge cake and £\(7\) on a fruit cake.
1. Decision Variables:
\(x = \text{number of sponge cakes}\)
\(y = \text{number of fruit cakes}\)
2. Objective Function:
\(\text{Maximise } P = 4x + 7y\)
3. Constraints:
• Flour constraint: \(200x + 400y \le 2400\) (which simplifies to \(x + 2y \le 12\))
• Time constraint: \(x + 3y \le 15\)
• Non-negativity constraints: \(x \ge 0\) and \(y \ge 0\)
Key Takeaway: Always simplify constraint equations where possible, and never forget to state \(x \ge 0\) and \(y \ge 0\)!
3. Graphing Constraints and the Feasible Region
Once you have your inequalities, you plot them on a Cartesian grid to visually locate the Feasible Region (FR).
Step-by-Step Graphing Method
1. Draw the Boundary Lines:
Replace the inequality sign with an equals sign (\(=\)). For example, convert \(x + 2y \le 12\) to the straight line \(x + 2y = 12\).
2. Find the Intercepts:
The easiest way to plot a straight line is to find where it crosses the axes:
• Set \(x = 0\) and solve for \(y\) to find the \(y\)-intercept.
• Set \(y = 0\) and solve for \(x\) to find the \(x\)-intercept.
For \(x + 2y = 12\):
When \(x = 0\), \(2y = 12 \implies y = 6\), giving the point \((0, 6)\).
When \(y = 0\), \(x = 12\), giving the point \((12, 0)\).
Join these two points with a straight line.
3. Solid vs Broken Lines:
• Use a solid line for inclusive inequalities (\(\le\) or \(\ge\)).
• Use a broken (dashed) line for strict inequalities (\(<\) or \(>\)).
4. Determine Which Side to Keep (Test Point Method):
Pick a test point not on the line, usually the origin \((0,0)\):
Substitute \((0,0)\) into the original inequality \(x + 2y \le 12\):
\(0 + 2(0) = 0 \le 12\) (This statement is true!)
Since it is true, the side containing \((0,0)\) is the valid side.
5. CCEA Shading Convention:
In CCEA examinations, unless a question explicitly directs you to "shade the unwanted regions", clearly identify and outline the region containing all feasible points and label it \(R\) or \(\text{FR}\).
4. Finding the Optimal Solution
Under the CCEA specification, there are two approved methods for finding the optimal point within the feasible region:
Method 1: The Vertex (Corner-Point) Testing Method
The Fundamental Theorem of Linear Programming tells us that the maximum or minimum value will always occur at one of the vertices (corners) of the feasible region.
Procedure:
1. Find the coordinates of every vertex of the feasible region \(R\). If two boundary lines cross at a vertex, solve their equations simultaneously.
2. Substitute each coordinate pair \((x, y)\) into the objective function.
3. Compare the resulting values to find the largest (for maximisation) or smallest (for minimisation).
Method 2: The Objective Line (Ruler / Profit Line) Method
Procedure:
1. Pick an arbitrary, convenient constant value \(k\) and draw an initial objective line: \(ax + by = k\). (Choose a value of \(k\) that is easily divisible by \(a\) and \(b\)).
2. Place your ruler along this line to capture its gradient.
3. Slide your ruler parallel across the feasible region:
• For maximisation: Move in the direction of increasing value. The last point on or inside \(R\) that the ruler touches before leaving the region is the maximum solution.
• For minimisation: Move in the direction of decreasing value. The first point touched in the region is the minimum solution.
Full Worked Example: Finding the Optimum
Let us find the maximum profit for our baker from Section 2:
Objective: \(\text{Maximise } P = 4x + 7y\)
Subject to:
\(x + 2y \le 12\)
\(x + 3y \le 15\)
\(x \ge 0, y \ge 0\)
Step 1: Find the Vertices of the Feasible Region:
• Vertex A: Origin \((0, 0)\)
• Vertex B: \(y\)-intercept of \(x + 3y = 15 \implies (0, 5)\)
• Vertex C: \(x\)-intercept of \(x + 2y = 12 \implies (12, 0)\)
• Vertex D: Intersection of \(x + 2y = 12\) and \(x + 3y = 15\):
Subtract the first equation from the second:
\((x + 3y) - (x + 2y) = 15 - 12 \implies y = 3\)
Substitute \(y = 3\) back into \(x + 2y = 12\):
\(x + 2(3) = 12 \implies x = 6\)
So Vertex D is \((6, 3)\).
Step 2: Test Each Vertex in the Objective Function \(P = 4x + 7y\):
• At \((0, 0)\): \(P = 4(0) + 7(0) = £0\)
• At \((0, 5)\): \(P = 4(0) + 7(5) = £35\)
• At \((12, 0)\): \(P = 4(12) + 7(0) = £48\)
• At \((6, 3)\): \(P = 4(6) + 7(3) = 24 + 21 = £45\)
Conclusion:
The optimal solution is to bake \(12\) sponge cakes and \(0\) fruit cakes, giving a maximum profit of £\(48\).
5. Integer Solution Requirements
In many real-life applications, variables represent discrete objects that cannot be split into fractions (such as cakes, cars, machines, or people). When this happens, solutions must be whole numbers (integers).
Important Rule for Decimal Vertices:
If the optimal vertex gives non-integer values (e.g. \(x = 4.3, y = 2.7\)), DO NOT simply use standard rounding rules! Rounding \(4.3\) down and \(2.7\) up to \((4, 3)\) might create a point that lies outside the feasible region, violating the constraints.
What to do instead:
1. Identify the integer grid points close to the optimal non-integer vertex.
2. Check that each integer candidate point satisfies all constraint inequalities (i.e. it lies strictly inside or on the boundary of \(R\)).
3. Substitute the valid integer points into the objective function to see which one gives the best outcome.
6. Common Pitfalls & Examiner Warnings
Make sure to review these common errors identified in examiner reports:
• Reversing Inequality Signs: Double check phrases like "at least \(10\)". Writing \(x \le 10\) instead of \(x \ge 10\) will ruin your graph!
• Forgetting Non-Negativity: Always state \(x \ge 0\) and \(y \ge 0\) when writing down constraints for real-life problems.
• Plotting Intercept Inaccuracies: Take care when calculating intercepts. For \(3x + 4y = 24\), the \(x\)-intercept is \((8, 0)\) and the \(y\)-intercept is \((0, 6)\). Do not swap them around!
• Plotting the Objective Function as a Constraint: Remember that \(P = ax + by\) is not a boundary that limits your feasible region; it is the formula used to evaluate points within the region.
• Blind Rounding: Never round non-integer coordinates without verifying that the rounded point actually lies inside the feasible region.
Chapter Summary
• Formulate: Define variables \(x\) and \(y\), write the objective function (\(P\) or \(C\)), and list all constraints including \(x \ge 0, y \ge 0\).
• Graph: Draw boundary lines using intercepts, use solid lines for \(\le, \ge\) and broken lines for \(<, >\), test \((0,0)\), and clearly label the feasible region \(R\).
• Solve: Find the coordinates of all vertices and substitute them into the objective function (or use the parallel objective line method) to identify the optimal value.
• Check: Ensure discrete items have integer solutions that lie strictly inside or on the boundary of \(R\).