Introduction to Graphical Linear Programming
Welcome to one of the most practical parts of Discrete Mathematics! Linear Programming (LP) is a fancy name for a simple goal: finding the best possible outcome (like maximum profit or minimum cost) given a set of limitations.
Imagine you are running a small bakery. You want to make as much money as possible, but you only have a certain amount of flour, a limited number of oven hours, and you can't bake a negative number of cakes! Linear Programming helps us balance these rules to find the "sweet spot" for success.
1. Formulating the Problem: The Ingredients
Before we can draw anything, we need to turn a real-world story into math. This is called formulation. There are four main parts to any LP problem:
A. Decision Variables
These are the things you can control. We usually call them \(x\) and \(y\). Always define what they represent and include their units.
Example: Let \(x\) be the number of standard cupcakes produced and \(y\) be the number of deluxe cupcakes produced.
B. The Objective Function
This is what you want to achieve. Are you trying to maximise profit or minimise waste? It is written as an equation, usually starting with \(P\) (for profit) or \(C\) (for cost).
Example: If a standard cupcake makes £2 profit and a deluxe one makes £3, your objective is to maximise \(P = 2x + 3y\).
C. The Constraints
Constraints are the "rules" or limits. We write these as inequalities (using symbols like \(\le\) or \(\ge\)).
- Resource limits: "You only have 500g of sugar." If \(x\) uses 10g and \(y\) uses 20g, then \(10x + 20y \le 500\).
- Ratio constraints: "You must make at least twice as many standard cakes as deluxe ones." This means \(x \ge 2y\).
D. Trivial Constraints
In the real world, you can't have a negative amount of items. We must always include \(x \ge 0\) and \(y \ge 0\). Don't forget these; they keep our graph in the top-right quadrant!
Quick Review: To formulate, identify your variables, write your "goal" (Objective), and list your "rules" (Constraints).
2. The Feasible Region: Mapping the Rules
Now we move to the graph. We need to find the Feasible Region—the area on the graph where all the rules are satisfied at the same time.
How to Draw the Lines
For each constraint (like \(2x + 3y \le 12\)), first treat it as an equation (\(2x + 3y = 12\)) to draw a straight line. A quick trick is the Cover-Up Method:
- Set \(x = 0\) and solve for \(y\). (In our example: \(3y = 12\), so \(y = 4\)). Plot point \((0, 4)\).
- Set \(y = 0\) and solve for \(x\). (In our example: \(2x = 12\), so \(x = 6\)). Plot point \((6, 0)\).
- Connect the two points with a straight line.
The Shading Rule (Crucial for OCR!)
In this syllabus, we use a specific convention: Shade the region that is NOT satisfied.
If your rule is \(x + y \le 10\), any point above the line is "bad" (doesn't fit the rule). Shade the area above the line. After you do this for every constraint, you will be left with a clear, unshaded area. This clear area is the Feasible Region.
Did you know? Using this "shading out" method makes the allowed area jump out at you, making it much easier to see where your solution might be!
3. Finding the Optimal Solution
Once you have your clear Feasible Region, how do you find the exact point that gives the maximum profit? There are two main methods:
Method 1: Vertex Testing (Checking the Corners)
The "best" solution will always occur at one of the vertices (corners) of the Feasible Region.
- Find the coordinates of every corner of your unshaded region.
- Plug those \((x, y)\) values into your Objective Function.
- The one that gives the highest value (for maximise) or lowest value (for minimise) is your winner!
Method 2: The Objective Line (The "Sliding Line")
If there are many corners, this method is faster:
- Pick a random value for your objective (e.g., if \(P = 2x + 3y\), try \(2x + 3y = 6\)).
- Draw this line on your graph (usually as a dashed line).
- Using a ruler, slide the line parallel to itself across the feasible region.
- For Maximising: The last point the line touches before leaving the feasible region is the maximum.
- For Minimising: The first point the line touches within the feasible region is the minimum.
Key Takeaway: The "best" answer is almost always at a corner! Use a ruler to find which corner is the furthest in the direction you want to go.
4. Dealing with Integer Solutions
Don't worry if this seems tricky at first, but sometimes the math gives an answer like "make 4.7 cars." You can't make 0.7 of a car! If the question asks for integer solutions, you must find the best whole-number coordinates.
Common Mistake to Avoid: Don't just round your answer to the nearest whole number! That rounded point might be outside your feasible region (breaking the rules).
The Fix: Look at the whole-number points \((x, y)\) that are closest to your optimal vertex but still inside the unshaded region. Test these points in your Objective Function to see which one is best.
Summary Checklist
- Formulate: Identify variables (\(x, y\)), write the Objective (\(P = ...\)), and list Constraints.
- Graph: Draw lines using intercepts.
- Shade: Shade the "wrong" side of the lines. Keep the Feasible Region clear.
- Solve: Test the corners or use a sliding objective line.
- Check: Does the answer need to be a whole number? Does it make sense in context?
Top Tip: Always use a sharp pencil and a long ruler. Accuracy in your drawing makes finding the correct "last point touched" by the objective line much easier!