Welcome to the Simplex Algorithm!
In your previous studies, you probably solved optimization problems using Graphical Linear Programming. That works great when you only have two variables (\(x\) and \(y\)), but what happens when a factory needs to decide how much of 10 different products to make? You can't draw a 10-dimensional graph!
That is where the Simplex Algorithm comes in. It is a step-by-step mathematical "recipe" used to find the best possible outcome (like maximum profit) in systems with many variables. Don't worry if it seems like a lot of numbers at first—it’s just a logical process of moving from one corner of a shape to a better one until you reach the top!
1. Setting the Stage: Terminology
Before we build our first table, we need to understand the language of Simplex. This is often where students get confused, so let’s break it down simply.
Basic and Non-Basic Variables
In any specific step of the algorithm, we split our variables into two camps:
- Non-basic variables: These are variables that we "turn off" by setting them to zero.
- Basic variables: These are the variables that currently have a value. In a simplex tableau (our big table of numbers), a basic variable is easy to spot because its column will consist of all zeros except for a single 1.
- Basic Feasible Solution (BFS): This is just a fancy name for the coordinates of a "corner point" on our 3D (or many-D) shape that satisfies all our constraints.
Slack Variables
The Simplex Algorithm doesn't like inequalities (like \(\le\)). It prefers equations (\(=\)). To fix this, we add a slack variable (\(s\)) to each constraint. Analogy: Imagine you have £10 to spend. You spend \(x\). The "slack" is the change left in your pocket. Spending \(x \le 10\) is the same as saying \(x + s = 10\), where \(s\) is your leftover change.
Quick Review: Key Terms
Slack Variable: Added to turn \(\le\) into \(=\).
Basic Variable: A variable that is "in the solution" (column has one '1' and the rest '0').
Non-Basic Variable: A variable set to zero.
2. Building the Initial Tableau
To start, we put everything into a tableau (a table). The syllabus requires a standard format:
- The Objective Row: Usually the top row. It shows the profit or value you want to maximize. If your objective is \(P = 3x + 2y\), you must rearrange it to \(P - 3x - 2y = 0\) before putting it in the table.
- Constraint Rows: These follow the objective row. Each row represents one of your constraints after you've added the slack variables.
- RHS Column: The "Right Hand Side" column, which shows the values at the end of your equations.
Did you know? We always start the Simplex Algorithm at the origin \((0, 0)\). This means our initial non-basic variables are our decision variables (\(x, y\)), and our basic variables are our slack variables (\(s_1, s_2\)). We are currently making nothing and have all our resources left over!
3. The Iteration: Improving the Solution
An iteration is just one full cycle of the algorithm. Each iteration moves us along an edge of our multi-dimensional shape to a new corner (BFS) that has a better value for our objective.
Step-by-Step: How to Perform an Iteration
1. Choose the Pivot Column: Look at the objective row. Find the most negative value. This column tells us which variable will give us the biggest boost in profit. This is now our entering variable.
2. Choose the Pivot Row (The Ratio Test): For every row (except the objective row), divide the RHS value by the value in the pivot column.
Rule: Ignore zero or negative values in the pivot column!
The row with the smallest positive ratio is your pivot row. This variable is our leaving variable.
3. Pivot! This is the algebraic part. You must use row operations to:
- Make the pivot element (where the pivot row and column meet) equal to 1.
- Make every other entry in that column equal to 0.
Don't worry if this seems tricky at first! It’s just like the simultaneous equation methods you've used before. You are just transforming the table so a new variable becomes "Basic" (gets that single 1).
4. Knowing When to Stop
You keep performing iterations until you look at the objective row and there are no more negative values in the variable columns. This means there is no way to increase the objective value any further. You have reached the optimum!
Interpreting the Final Table
To read your final answer:
- Look for the columns that have a single '1' and the rest '0' (the basic variables).
- The value of that variable is the number in the RHS column for the row where the '1' appears.
- Any variable that isn't a basic variable (its column is messy) is zero.
Common Mistake to Avoid
The Sign Trap: When moving your objective function into the table (e.g., \(P = 5x + 4y\)), students often forget to flip the signs to \(-5\) and \(-4\). If you don't have negatives in your first objective row, you can't start the algorithm!
5. Graphical and Algebraic Interpretation
It’s important to visualize what is happening. The feasible region of a Linear Programming problem is a convex polygon (in 2D) or a polyhedron (in 3D).
Each iteration of the Simplex Algorithm is simply a jump from one vertex (corner) to an adjacent vertex along the edges of that shape. We are "climbing" the shape until we reach the highest point.
Takeaway: Simplex is just an algebraic way of doing what you did graphically, but it can handle 100 variables just as easily as 2!
Summary Checklist
• Slack Variables: Used to turn \(\le\) into \(=\).
• Tableau Layout: Obj row (with flipped signs), then constraints, then RHS.
• Pivot Column: Most negative in the top row.
• Pivot Row: Smallest positive RHS/Pivot Ratio.
• Stopping Condition: No negatives in the top row.
• Interpretation: Basic variables = RHS values; Non-basic = 0.