Welcome to the World of Linear Programming!
In this chapter of Modelling with Algorithms, you are going to learn how to make the "best" decisions possible. Whether it is a factory trying to maximize profit while using limited materials, or a delivery company trying to minimize fuel costs, Linear Programming (LP) is the mathematical tool they use. Don't worry if it seems like a lot of jargon at first—at its heart, LP is just about finding the best way to use what you've got!
1. Formulating the Problem
Before we can solve a problem, we have to translate it from "English" into "Maths." This process is called formulation.
The Ingredients of an LP
- Decision Variables: These represent the things you can control. Example: Let \(x\) be the number of standard bikes produced and \(y\) be the number of pro bikes.
- Objective Function: This is your goal. You usually want to maximize (e.g., profit) or minimize (e.g., waste). It looks like this: \(P = 5x + 8y\).
- Constraints: These are your limits (money, time, materials). They are written as inequalities. Example: \(2x + 3y \le 60\) (hours of labor available).
- Non-negativity: In the real world, you can't produce negative bikes! So, we always include \(x \ge 0, y \ge 0\).
Standard Form
An LP is in standard form if you are maximizing a linear function, all your constraints are less-than-or-equal-to (\(\le\)) a constant, and all variables are non-negative.
Quick Review Box:
Variables: What are we choosing?
Objective: What is the goal?
Constraints: What are the rules?
Key Takeaway: Formulation is just turning a word problem into a set of equations and inequalities.
2. Slack Variables and Augmented Form
Inequalities are hard to solve directly. We prefer equations. To turn a \(\le\) inequality into an \(=\) equation, we add a slack variable.
Analogy: Imagine you have a budget of £50. You spend £x. The "slack" is the change in your pocket. Spending + Change = £50.
How it works:
If your constraint is \(2x + y \le 10\), you add a slack variable \(s_1\) to get:
\(2x + y + s_1 = 10\), where \(s_1 \ge 0\).
This is now in augmented form (also called slack form).
Common Mistake: Forgetting that slack variables must also be non-negative (\(s \ge 0\)).
3. Graphical Solutions (2-D Problems)
If you only have two variables (\(x\) and \(y\)), you can draw the problem on a graph!
Steps to solve:
- Draw the lines: Treat inequalities as equations (e.g., draw the line \(x + y = 10\)).
- Find the Feasible Region: This is the area on the graph where all the constraints are true at the same time. Think of this as the "OK Zone."
- Handle Infeasibility: If there is no area where all rules are met, the problem is infeasible—there is no solution!
- Find the Optimal Point: The best point is always at a vertex (a corner) of the feasible region. You can find it by:
- Vertex Testing (Enumeration): Checking the objective value at every corner.
- Objective Line Method: Drawing a line representing your objective and sliding it as far as possible while still touching the "OK Zone."
Integer Linear Programming (ILP)
Sometimes your variables must be whole numbers (you can't sell half a bike). This is an ILP.
Warning: The best integer solution might not be the closest whole number to the "maths" answer. You must check the nearby integer points within the feasible region.
Did you know? Even though we live in 3-D, you can visualize 3-D LPs where the feasible region is a solid shape like a crystal, and the constraints are flat planes!
4. The Simplex Method
What if you have 10 variables? You can't draw a 10-D graph! The Simplex Method is an algebraic algorithm that moves from one corner of the feasible region to a "better" one until it finds the best.
Key Terms:
- Tableau: A table used to organize the equations.
- Pivot: The specific number in the table we use to move from one corner to the next.
- Basic Variables: The variables currently "active" at a vertex.
- Non-basic Variables: Variables that are zero at the current vertex.
The Logic:
The algorithm looks at the bottom row of the tableau (the objective row). If there are negative numbers there (in a maximization problem), we can still improve the profit! We pick a pivot column and row, perform "row operations" to create a new tableau, and repeat until all numbers in the bottom row are positive or zero.
Don't worry if this seems tricky! Just think of it as a systematic way of checking the corners of a shape without having to draw it.
Quick Review: Simplex stops when no more improvement can be made to the objective value.
5. Non-Standard Forms
Sometimes the rules change. Here is how to handle them:
- Greater-than constraints (\(\ge\)): These require a Two-Stage Simplex method. In the first stage, you find a valid starting corner.
- Equality constraints (\(=\)): These can be replaced by two inequalities: \(x \le 4\) and \(x \ge 4\).
- Minimization: Most software and the Simplex method are set up to maximize. To minimize costs, you can maximize the negative of the costs!
6. Network Problems as LPs
One of the coolest things about Linear Programming is that it can solve other types of problems you've studied!
- Shortest Path: Finding the quickest route can be written as an LP where you minimize the total distance.
- Maximum Flow: Finding how much liquid can flow through pipes can be written as an LP where you maximize the flow variable.
- Matching/Allocation: Assigning workers to jobs to minimize total cost is a classic LP problem.
Key Takeaway: LP is a "unifying" tool—it can handle almost any problem that involves linear rules.
7. Using Software
In the real world, we use computers to solve LPs. You need to be able to interpret the output.
- Optimal Value: The final "best" result (e.g., Max Profit = £500).
- Variable Values: How much of each thing you should make (e.g., \(x=10, y=5\)).
- Slack: Tells you if a resource was fully used (slack = 0) or if there was leftover (slack > 0).
Summary Takeaway: Whether solving by hand, by graph, or by computer, Linear Programming is all about optimization under pressure (constraints). Master the formulation, and the rest is just following the algorithm steps!