Welcome to Linear Programming!
Hi there! Welcome to one of the most practical chapters in Decision Mathematics. Linear Programming is essentially the art of "making the best choice." Imagine you are running a business: you want to make the most profit, but you only have a certain amount of money, time, and raw materials. How do you decide exactly how much of each product to make? That is what we are going to solve!
In this unit, we will learn how to turn real-world "word problems" into mathematical models and use graphs to find the perfect solution. Don't worry if it seems like a lot of steps at first—once you learn the rhythm, it becomes very logical.
Quick Review of Prerequisite Skills: Before we start, make sure you are comfortable with:
- Drawing straight-line graphs (e.g., \(y = 2x + 3\)).
- Understanding inequalities like \(x + y \le 10\) (this means the sum can be 10 or anything smaller).
1. Formulating a Problem
Before we can solve a problem, we have to "translate" it from English into Math. This process is called Formulation.
The Three Building Blocks
Every Linear Programming (LP) model needs three things:
- Decision Variables: These are the things you are trying to decide. Usually, we call them \(x\) and \(y\).
Example: Let \(x\) be the number of standard chairs and \(y\) be the number of deluxe chairs. - Objective Function: This is your goal. Do you want to Maximize profit or Minimize cost?
Example: Maximize \(P = 10x + 15y\) (where $10 and $15 are the profits per chair). - Constraints: These are the "rules" or limits. You can't make infinite chairs! You are limited by labor hours, wood, or machine time.
Example: \(2x + 3y \le 60\) (meaning you only have 60 hours of labor).
Did you know?
The "Linear" in Linear Programming means that all our variables (\(x\) and \(y\)) are only to the power of 1. You won't see any \(x^2\) or \(xy\) here!
The "Non-Negativity" Constraint
In the real world, you can't make -5 chairs. Therefore, almost every problem must include:
\(x \ge 0, y \ge 0\)
Don't forget these! Examiners often award a mark just for writing these down.
Summary Takeaway: Formulation is just turning words into a goal (Objective) and a set of rules (Constraints) using variables (\(x\) and \(y\)).
2. Graphical Solutions
Once we have our inequalities, we plot them on a graph to find the "Safe Zone" where all the rules are satisfied. This zone is called the Feasible Region.
Step-by-Step: Drawing the Feasible Region
- Treat inequalities as equations: To draw the line for \(x + y \le 10\), first draw the line \(x + y = 10\).
- Find two points: The easiest way is to let \(x = 0\) to find the \(y\)-intercept, and let \(y = 0\) to find the \(x\)-intercept.
- Shade the UNWANTED region: In Edexcel D1, the convention is usually to shade out the side of the line that does not satisfy the inequality. This leaves the Feasible Region (R) clean and white in the middle.
- Label the Region: Always mark your final unshaded area with a big letter R.
Analogy: The Bouncer at a Club
Think of each constraint as a bouncer. One bouncer says "You must be over 18," another says "You must wear a tie." The Feasible Region is the dance floor where everyone has followed all the rules. If you break even one rule, you're shaded out!
Quick Review:
- \(\le\) means we want the area below or to the left of the line.
- \(\ge\) means we want the area above or to the right of the line.
3. Finding the Optimal Point
The "best" solution (the Optimal Solution) will always be located at one of the "corners" (vertices) of the Feasible Region. There are two main ways to find it:
Method A: The Vertex Method
This is the "brute force" method.
1. Find the coordinates of every corner of your Feasible Region R.
2. Plug each \((x, y)\) coordinate into your Objective Function.
3. The one that gives the highest value (for Maximization) or lowest value (for Minimization) is your winner!
Method B: The Objective Line (Ruler) Method
This is often faster and shows you understand the math deeply!
1. Pick a "random" target value (\(k\)) for your objective. If your objective is \(P = 10x + 20y\), try drawing the line \(10x + 20y = 200\).
2. Use a ruler to draw this "search line" (usually as a dashed line).
3. Slide your ruler parallel to this line across the graph:
- For Maximize: The last point the ruler touches before leaving the Feasible Region is the optimum.
- For Minimize: The first point the ruler touches as it enters the Feasible Region is the optimum.
Common Mistake to Avoid
When using the Ruler Method, make sure your ruler stays perfectly parallel to your original dashed line. If it tilts even a little, you might point to the wrong corner!
Summary Takeaway: You don't need to check every point in the region, just the corners. The "Objective Line" acts like a scanner finding the best corner.
4. Integer Solutions
Sometimes, the "perfect" math answer might be \(x = 5.2, y = 3.8\). But if \(x\) and \(y\) are people or cars, you can't have 0.2 of a person! This is where we need Integer Solutions.
How to find them:
- Find the exact (decimal) optimal point using the methods above.
- Look at the whole numbers (integers) immediately surrounding that point.
- Crucial Rule: You must check which of these nearby integer points are actually inside the Feasible Region. A point might be close, but if it breaks a constraint, it's not allowed!
- Test the valid integer points in the Objective Function to see which is best.
Example:
If your optimum is \((2.9, 4.1)\), you might check \((2, 4)\), \((3, 4)\), \((3, 5)\), etc. If \((3, 4)\) is outside the shaded region, you throw it away and try the next closest one.
Summary Takeaway: If you need whole numbers, find the "math" answer first, then "scout" the nearby grid-crossings that are inside the allowed zone.
Chapter Summary Checklist
Before you move on to the practice questions, make sure you can:
- Identify Decision Variables, Objective Functions, and Constraints from a paragraph of text.
- Always include non-negativity (\(x, y \ge 0\)).
- Draw lines accurately and shade the rejected side.
- Label the Feasible Region with an R.
- Use the Objective Line (ruler) to find the best vertex.
- Check integer points if the context requires whole numbers.
Don't worry if it feels tricky at first! The more graphs you draw, the more "natural" the Feasible Region starts to look. You've got this!