Welcome to Graphical Linear Programming!
Have you ever had to make a choice where you wanted to get the most out of something but were limited by time, money, or resources? Maybe you were deciding how many hours to study for different subjects to get the best grades, or how a bakery decides how many cupcakes vs. brownies to bake to make the most profit.
That’s exactly what Linear Programming (LP) is! In this chapter, we use graphs to find the "perfect" answer to these real-world puzzles. Whether you are aiming for a top grade or just want to pass, these notes will guide you through the process step-by-step.
1. Formulating the Problem
Before we can draw anything, we need to turn a word problem into math. This is called formulation. Think of it as translating English into "Math-ish."
The Three Ingredients of an LP Problem:
- Decision Variables: These are the things you are choosing. We usually call them \(x\) and \(y\). Example: Let \(x\) be the number of standard cakes and \(y\) be the number of deluxe cakes.
- Constraints: These are the "rules" or limits. You might have a limited amount of flour or a limited number of oven hours.
Quick Review: Inequalities use signs like \( \leq \) (less than or equal to) or \( \geq \) (greater than or equal to). - The Objective Function: This is your goal. Are you trying to maximise profit or minimise cost? Example: Maximise \(P = 5x + 8y\) (where £5 and £8 are the profits for each type of cake).
Special Case: Ratio Constraints
Sometimes the problem says something like "you must bake at least twice as many standard cakes as deluxe cakes."
Don't panic! Just write it as it sounds: \(x \geq 2y\). Then, rearrange it so the variables are on one side: \(x - 2y \geq 0\).
Trivial Constraints
In the real world, you can't bake -5 cakes. So, we almost always include trivial constraints: \(x \geq 0\) and \(y \geq 0\). These just keep our graph in the top-right quadrant.
Key Takeaway: Always define your variables clearly with units (e.g., "number of cakes") before writing your inequalities!
2. The Graphical Solution
Once we have our inequalities, we plot them on a coordinate grid.
Step-by-Step: Drawing the Region
- Draw the lines: Treat each inequality as an equation (use \(=\)) to draw the boundary line. Tip: To draw \(2x + 3y = 12\), find where it hits the axes. If \(x=0, y=4\). If \(y=0, x=6\). Join (0,4) and (6,0).
- Shade the "Unwanted" Region: OCR A Level rules usually ask you to shade the region that does NOT satisfy the inequality. Common Mistake: Don't shade the "good" bit! The Feasible Region should be the clear, unshaded part in the middle.
- The Feasible Region: This unshaded area represents every possible combination of \(x\) and \(y\) that obeys all the rules.
Did you know? The feasible region is always a convex polygon. This just means it's a shape with straight sides and no "caved-in" corners.
3. Finding the Optimal Point
Now that we have our clear "feasible region," where is the best point? The "perfect" answer is almost always at one of the vertices (the corners) of the unshaded region.
Method A: The Objective Line (The "Sliding Ruler" Trick)
1. Pick a random value for your objective (e.g., if your goal is \(5x + 8y\), try \(5x + 8y = 40\)).
2. Draw this line on your graph (usually as a dashed line).
3. Use a ruler to slide this line parallel across the feasible region.
4. For maximising, the last point the ruler touches before leaving the region is the winner. For minimising, it’s the first point it hits.
Method B: Vertex Testing
Simply find the coordinates of every corner of the unshaded region and plug them into your objective function. The one that gives the biggest (or smallest) number is your answer!
Key Takeaway: The optimal solution occurs at a vertex. If the objective line is parallel to a boundary, every point on that boundary line could be optimal!
4. Slack Variables (Stage 2 Learners)
Sometimes we want to turn an inequality into an equation. We do this by adding a slack variable.
Imagine you have 10 hours of labor (\(x + y \leq 10\)). If you only use 8 hours, you have 2 hours "slack" left over.
We write this as: \(x + y + s_1 = 10\), where \(s_1 \geq 0\).
Memory Aid: Slack is "leftover" space. You add it to the "smaller" side of a \(\leq\) sign to make it equal.
5. Integer Programming
What if \(x\) and \(y\) have to be whole numbers? (You can't sell 2.37 cars!).
If your optimal vertex is not a whole number (e.g., \(2.4, 5.8\)), you can't just round it! Rounding might take you outside the feasible region.
The Branch-and-Bound Method
Don't worry if this seems tricky; it’s just a "divide and conquer" strategy:
- Find the non-integer optimal solution (e.g., \(x = 3.5\)).
- Branch it into two new problems: one where \(x \leq 3\) and one where \(x \geq 4\).
- Solve these new regions graphically.
- Keep branching until you find the best integer (whole number) point.
6. Sensitivity Analysis
What happens if the profit for a "standard cake" changes from £5 to £6?
Changing the coefficients in the objective function changes the gradient of the objective line. If the line gets steep enough, it might "tip over" a corner, making a different vertex the new optimal solution.
Quick Review Box:
- Feasible Region: The unshaded "safe zone."
- Vertex: A corner where two boundary lines meet.
- Integer: A whole number.
- Objective: Your goal (Maximise/Minimise).
Final Summary Checklist
- Formulate: Write your variables, objective, and constraints.
- Graph: Draw lines and shade the unwanted side.
- Optimize: Use a sliding objective line or test the vertices.
- Integers: If required, check whole-number points near the vertex using Branch and Bound.