Welcome to Linear Programming!
Ever wondered how a factory decides exactly how many products to make to get the most profit? Or how a delivery company finds the cheapest way to send parcels? That is exactly what Linear Programming is all about! It is a branch of Discrete Mathematics used to find the "best" outcome (like maximum profit or minimum cost) in a situation where you have limited resources (like time, money, or materials).
Don't worry if this seems a bit abstract right now. We are going to break it down into simple steps that will make you a problem-solving pro!
1. Building the Model: Formulating the Problem
Before we can solve a problem, we have to turn "real-world words" into "mathematical symbols." This is called formulation. Think of it like translating a story into the language of math.
The Three Ingredients of a Linear Program
Every problem needs three things:
1. Decision Variables: These represent what you are trying to decide. Usually, we call them \(x\) and \(y\). Example: \(x\) = number of cupcakes to bake, \(y\) = number of brownies to bake.
2. The Objective Function: This is your goal. Are you trying to maximize profit or minimize cost? We usually use the letter \(P\) for profit or \(C\) for cost. Example: If every cupcake earns £2 and every brownie earns £3, your objective is to maximize \(P = 2x + 3y\).
3. Constraints: These are your limits or "rules." You only have so much flour, so much time, or so much oven space. We write these as inequalities (using symbols like \(\le\) or \(\ge\)).
Step-by-Step: How to Formulate
Follow these steps every time:
Step A: Define your variables clearly (e.g., "Let \(x\) be...").
Step B: Write down the objective function.
Step C: List the constraints as inequalities.
Step D: Don't forget the Non-negativity Constraints! In the real world, you can't bake -5 cupcakes. So, we almost always include \(x \ge 0\) and \(y \ge 0\).
Quick Review: To formulate, identify what you want to decide (\(x, y\)), what your goal is (\(P\)), and what is stopping you (inequalities).
2. The Graphical Method: Drawing Your Limits
Once we have our inequalities, we need to see them on a graph. This helps us find the "sweet spot" where all our rules are satisfied.
Drawing the Lines
To draw an inequality like \(2x + 3y \le 12\), first treat it as an equation: \(2x + 3y = 12\).
Trick: Use the "Cover-up Method" to find where the line hits the axes!
- To find the \(y\)-intercept, cover \(x\) (set \(x=0\)): \(3y = 12\), so \(y = 4\).
- To find the \(x\)-intercept, cover \(y\) (set \(y=0\)): \(2x = 12\), so \(x = 6\).
Connect (0, 4) and (6, 0) with a straight line!
Shading the Feasible Region
The Feasible Region (often labeled R) is the area on the graph where all the inequalities are true at the same time. It’s like the only area on a map where you’re allowed to walk.
Top Tip: Always read the question carefully about shading. Some examiners want you to shade the area you want, while others want you to shade the area you don't want (leaving the feasible region white). AQA usually prefers you to label the feasible region clearly with an R.
Did you know? The Feasible Region is always a "convex" shape in linear programming, meaning it doesn't have any caves or dents pushed into it.
3. Finding the Winning Answer
Now that you have your region R, the best answer (the optimal solution) will almost always be at one of the vertices (the corners) of that region.
Method 1: The Vertex Testing Method
This is the most "fail-safe" method for beginners!
1. Find the coordinates of every corner (vertex) of your feasible region.
2. Plug each pair of \((x, y)\) values into your Objective Function.
3. See which one gives you the highest (for profit) or lowest (for cost) result.
Method 2: The Objective Line (Sliding Line) Method
Imagine your objective function is a ruler that you slide across the graph.
1. Draw a line for a random value of your objective (e.g., if \(P = 2x + 3y\), draw \(2x + 3y = 6\)).
2. Use a ruler to slide this line parallel across the graph away from the origin (for maximization).
3. The last point the line touches before leaving the feasible region is your maximum!
4. For minimization, the first point the line touches as it enters the region (moving from the origin) is your minimum.
Common Mistake: Students often stop as soon as they find a vertex. Make sure you check all corners or use the sliding line to be certain it's the absolute best one!
4. Dealing with "Whole Numbers" (Integer Programming)
Sometimes, the math might tell you that the best solution is to buy \(3.7\) buses. Obviously, you can't do that! This is called a Discrete constraint.
If your answer must be a whole number (an integer):
1. Find the optimal point on the graph (even if it has decimals).
2. Look at the whole-number coordinates inside the feasible region that are closest to that point.
3. Test these nearby integer points in your objective function to see which one is best.
Key Takeaway: The "best" decimal answer isn't always the "best" whole-number answer when you round it. Always test the nearby points!
Summary Checklist
- Can I define \(x\) and \(y\)?
- Have I written the objective function (\(P = ...\))?
- Did I include all constraints, including \(x, y \ge 0\)?
- Is my feasible region marked clearly?
- Have I tested the corners (vertices) to find the max/min?
Don't worry if the graphs feel messy at first. With a sharp pencil and a steady ruler, you'll find that Linear Programming is one of the most logical and rewarding parts of Further Maths!