Welcome to Linear Programming!
Ever wondered how a factory decides exactly how many of two different products to make to get the highest profit? Or how a delivery company finds the cheapest way to transport goods? That is exactly what Linear Programming (LP) is all about! It is a mathematical way of making the best possible decisions when you have limited resources.
In this chapter, we will learn how to turn real-life problems into math equations and then solve them using graphs. Don't worry if it sounds a bit heavy—we will take it one step at a time!
1. Prerequisites: What you need to know first
Before we dive in, make sure you are comfortable with these two ideas from your earlier math studies:
• Plotting Straight Lines: You should know how to draw lines like \( y = 3x + 2 \) or \( 2x + 5y = 20 \).
• Inequalities: Remember that \( y \leqslant 5 \) means "\( y \) is less than or equal to 5." On a graph, this represents a whole region, not just a line.
2. Forming a Linear Programming Model
The first step in any LP problem is "Formulation." This is just a fancy word for translating a story into math symbols. Every model needs four parts:
A. Decision Variables
These represent the things you are trying to decide. We usually call them \( x \) and \( y \).
Example: Let \( x \) be the number of standard cakes and \( y \) be the number of deluxe cakes.
B. The Objective Function
This is your goal. Are you trying to maximize profit or minimize cost? It is always written as an equation.
Example: To maximize profit \( P \), where each standard cake makes \$2 and deluxe makes \$3: Maximize \( P = 2x + 3y \).
C. Constraints
These are the "rules" or limits you must follow (like having only 10kg of flour). These are written as inequalities (\( \leqslant \) or \( \geqslant \)).
Example: If each cake takes 2 hours and you only have 40 hours: \( 2x + 2y \leqslant 40 \).
D. Non-negativity Constraints
In the real world, you can't make "negative" cakes! So, we almost always include:
\( x \geqslant 0, y \geqslant 0 \)
Quick Review: Every LP model needs variables (\( x, y \)), a goal (Maximize/Minimize), and rules (Inequalities).
3. The Graphical Method
Since we only work with two variables (\( x \) and \( y \)) in D1, we can solve these problems by drawing them. Here is how:
Step 1: Draw the Constraint Lines
Treat each inequality as an equals sign to draw the line.
Top Tip: To draw \( 2x + 5y = 20 \), use the "cover-up" method:
1. Set \( x = 0 \), then \( 5y = 20 \), so \( y = 4 \). Plot (0, 4).
2. Set \( y = 0 \), then \( 2x = 20 \), so \( x = 10 \). Plot (10, 0).
3. Join the dots!
Step 2: Find the Feasible Region (R)
The Feasible Region is the area on the graph where all the constraints are true at the same time.
Important Note: In Edexcel D1 exams, the convention is usually to shade out the regions you DO NOT want. This leaves the Feasible Region (R) clear and unshaded in the middle. Always check the question instructions to see which side to shade!
Step 3: Finding the Optimal Solution
Once you have your clear region \( R \), the "best" answer (the optimal point) will usually be at one of the vertices (the corners) of that region. There are two ways to find it:
Method 1: The Vertex Method
1. Identify the coordinates of every corner of the region \( R \).
2. Plug each \( (x, y) \) pair into your Objective Function.
3. The one that gives the highest value (for Max) or lowest (for Min) is your winner!
Method 2: The Objective Line (The Ruler Method)
1. Pick a random "target" for your objective, e.g., if your objective is \( P = 2x + 3y \), draw the line \( 2x + 3y = 12 \).
2. Place your ruler on this line.
3. Slide the ruler (keeping the same angle!) across the feasible region.
4. For a Maximization problem, the last point the ruler touches before leaving the region is the optimal solution.
5. For a Minimization problem, the first point it touches is the optimal solution.
Did you know? The "Objective Line" method is often faster than calculating every single corner, especially if the coordinates are messy decimals!
Key Takeaway: The optimal solution is always found on the boundary of the feasible region, usually at a corner.
4. Dealing with Integer Solutions
Sometimes, the answer \( x = 4.2, y = 3.8 \) doesn't make sense. If you are selling cars, you can't sell 0.2 of a car! In these cases, we need integer values (whole numbers).
Common Mistake to Avoid: Don't just round your answer to the nearest whole number! The nearest whole number point might actually be outside the feasible region or might not be the actual maximum.
How to do it correctly:
1. Find the exact optimal point (even if it's a decimal).
2. Look at the whole-number coordinates near that point that are inside the feasible region.
3. Test these nearby integer points in the objective function to see which one is best.
Summary Checklist for Success
• Read carefully: Is it a Maximize or Minimize problem?
• Be precise: Use a sharp pencil and a ruler for your graphs. A small slip in a line can lead to the wrong corner!
• Label clearly: Always label your axes, your lines, and the feasible region \( R \).
• Check your shading: Did the question ask you to shade the feasible region or the unwanted region? (Usually, it's the unwanted region in D1).
• Non-negativity: Don't forget \( x \geqslant 0 \) and \( y \geqslant 0 \). They are the "walls" of your graph on the \( x \) and \( y \) axes.
Don't worry if this seems tricky at first. With a little practice in drawing the lines, you'll be an expert at finding the "sweet spot" in no time!