Welcome to Linear Programming!
In this chapter of Discrete Mathematics, you are going to learn how to make the best possible decisions when you have limited resources. Imagine you are running a business: you want to maximise your profit, but you only have a certain amount of staff, time, and raw materials. These limits are your constraints.
Linear Programming (LP) is the mathematical toolkit used by everyone from airline schedulers to factory managers to find that "sweet spot" where efficiency is at its highest. Don't worry if it looks like a lot of steps at first—we'll break it down into simple, logical chunks.
1. Formulating the Problem (DD1)
Before we can solve a problem, we have to "translate" it from English into Mathematics. This is called formulation.
Every LP problem has three main ingredients:
1. Decision Variables: These are the things you can control. We usually call them \(x\), \(y\), or \(x_1\), \(x_2\). (Example: How many chocolate cakes should I bake? How many vanilla cakes?)
2. The Objective Function: This is your goal. You usually want to maximise something (like profit) or minimise something (like cost or waste). It looks like this: \( \text{Maximise } P = 5x + 3y \).
3. Constraints: These are the rules or limits you must follow. They are written as inequalities. (Example: You only have 10kg of flour, and each cake uses a certain amount.)
Non-negativity: In the real world, you can’t bake -5 cakes! So, we almost always include the constraint \(x \ge 0, y \ge 0\).
Quick Review: The Recipe for Formulation
• Identify what needs to be decided (Variables).
• Write down the goal (Objective Function).
• List the limits (Constraints).
• Don't forget \(x, y \ge 0\)!
2. Graphical Solutions (DD2)
If you only have two variables (\(x\) and \(y\)), you can solve the problem by drawing it! This is the most visual way to understand what's happening.
Steps to Solve Graphically:
1. Draw the constraints: Treat the inequalities as equations (lines) and plot them on a graph.
2. Find the Feasible Region: This is the area on the graph where all the constraints are satisfied. Usually, we shade out the regions we don't want to leave the "allowed" space clear.
3. Find the Optimal Point: The best solution will always be at one of the vertices (corners) of the feasible region.
How to find the best corner?
You can use the Objective Line Method (also called the Isoprofit line):
• Pick a random value for your objective, e.g., \(5x + 3y = 15\).
• Draw this line on your graph.
• Use a ruler to slide this line parallel across the feasible region.
• The last point the line touches as it leaves the feasible region is your maximum point.
Common Mistake: Be very careful with \( \le \) and \( \ge \). If the constraint is \(x + y \le 10\), you want the area below the line. If you shade the wrong side, your feasible region will be wrong!
3. The Simplex Algorithm: The Basics (DD3)
What if you have 10 variables? You can't draw a 10D graph! This is where the Simplex Algorithm comes in. It is a step-by-step "recipe" that moves from one corner of the feasible region to a better one, until it finds the best one.
Slack Variables
The Simplex method hates inequalities (\( \le \)). It prefers equations (\( = \)). To fix this, we add a Slack Variable (\(s\)) to each \( \le \) constraint.
Analogy: If you have a budget of £10 and you spend £7, your "slack" is £3.
So, \(x + y \le 10\) becomes \(x + y + s = 10\), where \(s \ge 0\).
The Initial Tableau
We put all our equations into a table called a tableau. A typical row in the table represents one constraint. The bottom row is usually the Objective Row (or the \(P\) row).
Important: When you move the objective function into the tableau, you must rearrange it so it equals zero.
Example: \(P = 5x + 3y\) becomes \(P - 5x - 3y = 0\). This is why the \(x\) and \(y\) values in the bottom row often start as negative.
4. How to "Pivot" (DD3 & DD4)
Pivoting is how we move from an okay solution to a better one. Don't worry if this seems tricky at first; it's just a set of rules.
Step 1: Choose the Pivot Column
Look at the objective row (bottom row). Pick the most negative number. This column tells us which variable will help increase our profit the most.
Step 2: Choose the Pivot Row (The Ratio Test)
For each row (except the bottom one), divide the "Value" (the right-hand side) by the number in the pivot column.
• Rule: Pick the row with the smallest positive ratio.
• Why? This ensures we don't accidentally "break" our constraints and leave the feasible region.
Step 3: Row Operations
Now, you use the same "row reduction" techniques you learned in the Matrices chapter:
1. Turn the pivot element (where the column and row meet) into a 1 by dividing the whole row.
2. Turn all other numbers in that column into 0 by adding or subtracting multiples of your pivot row.
Did you know? Computers use the Simplex algorithm millions of times a day to solve massive problems that save companies billions of pounds!
5. Interpreting the Final Tableau (DD4)
How do you know when you're finished? You stop when there are no negative numbers in the objective row.
Reading the Solution:
• Basic Variables: These are the columns that look like identity matrix columns (lots of zeros and one "1"). Their value is found in the "Value" column.
• Non-basic Variables: These are the columns that are messy (lots of different numbers). We set these to zero.
• The Objective Value: The number in the bottom-right corner is your maximum profit (or minimum cost).
Key Takeaway: If a slack variable (\(s\)) has a value in the final tableau, it means you have "leftover" resources for that constraint. If \(s = 0\), you used exactly everything available!
Summary Checklist
• Formulate: Define variables, goal, and limits.
• Graphical: Use for 2 variables; find the feasible region corners.
• Slack: Add them to turn \( \le \) into \( = \).
• Pivot Column: Most negative in the bottom row.
• Pivot Row: Smallest positive ratio (Value / Column).
• Finish: No negatives in the bottom row means you've found the best answer!