Welcome to Linear Programming!
Ever wondered how a delivery company finds the cheapest route, or how a factory decides exactly how many products to make to get the highest profit? That is exactly what Linear Programming (LP) is all about! It’s the mathematical art of making the best possible choice when you have limited resources. In the "Modelling with Algorithms" section, we use LP to turn real-world "word problems" into math that a computer (or a clever student) can solve.
1. The Building Blocks: Formulating the Problem
Before we can solve anything, we need to speak the language of LP. Every problem has three main parts:
Decision Variables
These are the things you can control. For example, if you're running a bakery, your variables might be:
Let \(x\) = the number of chocolate cakes made.
Let \(y\) = the number of vanilla cakes made.
Important: In LP, variables must represent numerical values and are usually non-negative (you can't bake -5 cakes!).
The Objective Function
This is your goal. Are you trying to get the most (Maximisation) or spend the least (Minimisation)?
Example: If each chocolate cake gives £5 profit and each vanilla gives £3, your objective is to maximise \(P = 5x + 3y\).
Constraints
These are your limits (the "rules"). You might only have 10kg of flour or 8 hours of oven time.
Example: If a chocolate cake uses 2kg of flour and vanilla uses 1kg, and you have 10kg total:
\(2x + 1y \le 10\)
Standard Form
An LP is in Standard Form when:
1. You are maximising a linear function.
2. All constraints are written as "less than or equal to" (\(\le\)) a constant.
3. All variables are non-negative (\(x, y \ge 0\)) and continuous (you can have 2.5 cakes for now).
Quick Review:
• Variables: What am I deciding? (Must be numbers!)
• Objective: What am I aiming for? (Max or Min)
• Constraints: What are my limits?
2. Slack Variables & Augmented Form
Algorithms like to work with equations (\(=\)) rather than inequalities (\(\le\)). To fix this, we use Slack Variables.
Think of a "Slack Variable" as the "leftover" resource. If you have 10kg of flour and use some to bake, the slack variable \(s\) is whatever flour is sitting unused on the shelf.
So, \(2x + y \le 10\) becomes \(2x + y + s = 10\).
When we add these slack variables to all our constraints, we call it the Augmented Form. This is the first step toward using the Simplex Method!
3. Solving Graphically (2-D Problems)
If you only have two variables (\(x\) and \(y\)), you can draw the problem on a graph. Don't worry if your drawing skills are rusty; it's all about the regions!
The Feasible Region
When you shade all your constraints on a graph, the area where all the rules are satisfied is called the Feasible Region. Any point inside this shape is a possible solution.
Infeasibility: If your constraints are so strict that there is no area where they all overlap, the problem is infeasible (you literally can't satisfy all the rules at once).
Finding the Optimal Point
The "best" point is usually at one of the vertices (corners) of the feasible region. You can find it in two ways:
1. Objective Line Method: Draw a line representing your objective (e.g., \(5x + 3y = 15\)). Use a ruler to slide this line parallel across the graph in the direction of improvement. The last corner it touches before leaving the feasible region is your winner!
2. Enumeration: Test the coordinates of every corner in your objective function and see which one gives the highest/lowest value.
What about Integer Solutions?
Sometimes you can't have 2.5 cakes; you need whole numbers. This is Integer Linear Programming (ILP).
Common Mistake: Just rounding your decimal answer to the nearest whole number might give you a point outside the feasible region! Instead, you should check the "lattice points" (whole number coordinates) near the decimal solution.
4. The Simplex Method
When you have three or more variables, a graph won't work (unless you can see in 4-D!). The Simplex Method is an algebraic "walk" around the corners of the feasible region until it finds the best one.
The Tableau
We organise the numbers into a grid called a tableau.
• Basic Variables: These are the variables that currently "own" a constraint (usually the slacks at the start).
• Non-Basic Variables: These are set to zero.
• The Pivot: To move to a better corner, we choose a pivot element. We pick a column (usually the one with the most negative number in the profit row) and then use a "ratio test" to pick the row.
Geometric Basis
Each row operation in the Simplex Method is actually moving you from one corner of the feasible region to an adjacent, better corner. If you can't find a negative number in the objective row of a maximisation problem, you've reached the top of the mountain—you've found the optimal solution!
Non-Standard Problems (The Two-Stage Simplex)
What if a constraint is "greater than or equal to" (\(\ge\)) or an "equal to" (\(=\))? Standard Simplex struggles here.
We use the Two-Stage Simplex Method. We create "Artificial Variables" to find a starting point (Stage 1) and then solve the actual problem once we are inside the feasible region (Stage 2).
Note: You don't need to know the "Big-M" method for this syllabus—just the Two-Stage approach!
5. LP in the Real World: Networks
LP is a "Master Algorithm." Many other problems you study in this course can be written as LPs:
• Shortest Path: Minimising the sum of weights on a path.
• Maximum Flow: Maximising the amount of "stuff" moving from source to sink.
• Critical Path: Finding the longest path in a project network.
• Transportation: Minimising the cost of moving goods from multiple factories to multiple shops.
6. Using Software
In the real world, LPs have thousands of variables. We use spreadsheet "Solvers."
Your Task: You need to be able to look at the computer output and interpret it.
• Which variables are "basic"?
• Is there any slack left (unused resources)?
• What is the final objective value?
Summary & Key Takeaways
• Formulation is Key: If you define your variables or constraints wrong, the math won't save you! Always check: "Does \(x\) represent a number?"
• Feasible Region: The "Allowed Zone" on a graph.
• Slack: The "Leftovers."
• Simplex: An algebraic way to jump from corner to corner to find the best profit or lowest cost.
• Integer Problems: Be careful with rounding; check the nearby whole-number points!
Don't worry if the Simplex Tableaux seem like a lot of numbers at first. Just remember: each step is just a fancy way of saying "Let's try a different corner of the shape!"