Introduction to the Simplex Algorithm | Baeldung on Computer Science

1. Introduction

In this tutorial, we’ll show how the Simplex algorithm works.

It’s widely used to solve real-world optimization challenges whose mathematical formulations include linear equalities or inequalities, e.g., in logistics, finance, engineering, and the like.

2. Background on Linear Programming

Linear programming (LP) is about finding the optimal solution to a problem within given constraints. It has three main components: the objective function, constraints, and the feasible region.

The objective function is the linear function we want to optimize:

$Z = c_1x_1 + c_2x_2 + \dots + c_nx_n$

where $Z$ is the result value, $c_1, c_2, \dots, c_n$ are the coefficients, and $x_1, x_2, \dots, x_n$ are decision variables.

Next, we have constraints—the rules and limits expressed as linear inequalities that define our feasible region. These constraints usually reflect real-world limitations like labor hours, materials, or machine capacity. They can take two forms: ≤ and ≥ inequalities.

A ≤ constraint ensures we don’t exceed a resource limit, such as:

$a_1x_1 + a_2x_2 + \dots + a_nx_n \leq b$

On the other hand, a ≥ constraint sets a minimum requirement to meet, like:

$a_1x_1 + a_2x_2 + \dots + a_nx_n \geq b$

Both types shape the boundaries of our feasible region, determining which solutions are valid.

Finally, the feasible region is the geometric space of decision variables where every condition is satisfied. Our job is to find the point within this region that optimizes the objective function.

3. The Basics of Simplex Algorithm

Now that we understand linear programming and its key components, the question is: how do we find the optimal solution in the feasible region? This is where the Simplex algorithm comes in.

3.1. The Steps

The Simplex algorithm navigates the feasible region of a linear programming problem, moving from one corner to another to find the best solution.

Instead of checking every point, it checks only the region’s corners, where the optimal solution is guaranteed to be:

We start at a corner point we get by solving the system of constraints. From there, we evaluate the objective function
Next, we determine the best direction to move. The edges from the current corner represent possible paths, and the algorithm selects the one offering the largest improvement of the objective function (whether maximizing or minimizing)
We move to the corner along the chosen edge, updating our solution and repeating the process
Eventually, we reach a point where no further improvement is possible, and that point is the optimal solution

The Simplex algorithm finds the best result without unnecessary calculations by focusing on corners.

3.2. Why Is the Optimal Solution Always at a Corner Point?

Think of the feasible region as a flat terrain surrounded by walls (the constraints), with the objective function as a sliding straight ramp leaning over it. Since the ramp is straight and flat walls define the terrain, the farthest the ramp can extend will always be at one of the sharpest points—the corners. These corners, where the boundaries meet, give the ramp something firm to “lean against.”

If the ramp stops at any interior point, it can slide further to a nearby edge or corner. This happens because the objective function and constraints are linear, so they guide the ramp straight to a corner. Therefore, the optimal solution is always at these corner points:

3.3. Slack, Surplus, and Artificial Variables

To apply the Simplex algorithm, we transform our constraint inequalities into equalities by introducing additional variables.

Slack variables handle ≤ constraints by adding unused resources.

For instance:

$a_1x_1 + a_2x_2 \leq b$

becomes:

$a_1x_1 + a_2x_2 + s_1 = b, \quad s_1 \geq 0$

where $s_1$ accounts for the leftover capacity.

For ≥ constraints, we use surplus variables to subtract the excess beyond a minimum requirement.

A constraint like:

$a_1x_1 + a_2x_2 \geq b$

rewrites as:

$a_1x_1 + a_2x_2 - s_1 = b, \quad s_1 \geq 0$

where $s_1$ represents the surplus over $b$ .

However, surplus variables alone don’t guarantee a feasible starting solution, so we introduce artificial variables acting as placeholders to form the initial tableau.

For example:

$a_1x_1 + a_2x_2 - s_1 = b$

becomes:

$a_1x_1 + a_2x_2 - s_1 + p_1 = b, \quad s_1, p_1 \geq 0$

Although artificial variable $p_1$ helps in the initial steps, it doesn’t represent any actual resources. Therefore, we must remove it as soon as possible using the Big M or Two-Phase methods.

3.4. Basic and Non-basic Variables

In the Simplex algorithm, variables are basic or non-basic. Basic variables take non-zero values and anchor the current solution, while non-basic ones are zero.

As we move between corners of the feasible region, non-basic variables can become basic and vice versa, depending on their effect on the objective function. This dynamic swapping lets the algorithm efficiently explore and optimize solutions.

3.5. Pivoting

Pivoting is the key step in the Simplex algorithm, where we exchange variables to improve the solution.

At each step, we pick a non-basic variable to enter the basis to enhance the objective function and a basic variable to leave to maintain feasibility. This keeps the solution in the feasible region. The pivot operation updates these variables, refining the solution and moving us closer to the optimum.

With systematic pivoting, the algorithm efficiently advances from one corner to the next.

4. A Working Example

4.1. Jane’s Optimization Problem

Jane balances two part-time jobs, Job I and Job II, and wants to maximize her weekly income. While doing so, she faces two constraints:

She can work up to 12 hours weekly
She has 16 hours for job preparation each week. Each hour at Job I requires 2 hours of preparation, while each hour at Job II requires 1

Furthermore, her earning potential differs between these jobs: she earns $40 per hour at Job I and $30 per hour at Job II.

So, how should Jane allocate her working hours between the two jobs to maximize her income? What will her total earnings be?

Let’s solve Jane’s problem step by step using the Simplex algorithm.

4.2. Step 1: Convert the Linear Program to Standard Form

To prepare for the Simplex algorithm, we ensure the objective function is in the maximization form.

Let $x_1$ be the hours worked at Job I, and $x_2$ be the hours worked at Job II. The total income is:

$Z = 40x_1 + 30x_2$

which we want to maximize. If the goal were minimization, e.g., of costs, we’d multiply the objective function by -1.

Then, we convert all $\leq$ constraints into equalities by adding slack variables.

Jane can work no more than 12 hours in total:

$x_1 + x_2 \leq 12$

Each hour at Job I requires 2 hours of preparation, and each hour at Job II requires 1 hour of preparation, with a maximum of 16 hours:

$2x_1 + x_2 \leq 16$

Additionally, both $x_1$ and $x_2$ must be non-negative:

$x_1, x_2 \geq 0$

We introduce slack variables (except for the non-negativity constraints) to convert the inequalities into equalities:

$x_1 + x_2 + s_1 = 12 \quad \text{where} \quad s_1 \geq 0$

$2x_1 + x_2 + s_2 = 16 \quad \text{where} \quad s_2 \geq 0$

Finally, we write the objective function as an equality:

$Z - 40x_1 - 30x_2 = 0$

Thus, we converted our problem into the standard form, and we set up our initial tableau:

x1	x2	s1	s2	Z	Right-hand side (RHS)
1	1	1	0	0	12
2	1	0	1	0	16
-40	-30	0	0	1	0

4.3. Step 2: Initialize the Basic Feasible Solution

Once the linear program is in standard form, the next step is to identify the initial basic feasible solution. We designate the slack variables from Step 1 as the basic variables and set all non-basic variables to zero. From the equality constraints, we compute the values of the basic variables, establishing the starting solution.

In our example, we choose $s_1$ and $s_2$ as basic variables, so we set $x_1$ and $x_2$ to zero. Then, we solve the resulting system for the basic variables $s_1$ and $s_2$ .

From the first constraint, $x_1 + x_2 + s_1 = 12$ , we substitute $x_1 = 0$ and $x_2 = 0$ to find:

$s_1 = 12$

Similarly, from the second constraint, we get:

$s_2 = 16$

Thus, the initial basic feasible solution is:

$x_1 = 0, x_2 = 0, s_1 = 12, s_2 = 16$

Next, we compute the value of the objective function:

$Z = 40x_1 + 30x_2 = 0 + 0 = 0$

4.4. Step 3: Identify the Entering Variable (Pivot Column)

Next, we identify the entering variable—the non-basic variable that moves into the basis to improve the solution. It guides us toward a better objective value—increasing it for maximization or decreasing it for minimization.

To choose the entering variable, we examine the objective row in the simplex tableau. For maximization, we select the variable with the “most negative” coefficient because increasing it yields the steepest ascent in $Z$ . Since each coefficient represents the rate of change of $Z$ , the most negative one ensures the fastest improvement. In minimization, we pick the largest positive coefficient instead. This step ensures we always move in the best possible direction.

Our example is a maximization problem. Looking at the coefficients of $x_1$ and $x_2$ in our initial tableau, we see that -40 is the most negative coefficient. So, $x_1$ will be the entering variable, and its column becomes the pivot column:

x1	x2	s1	s2	Z	Right-Hand Side (RHS)
1	1	1	0	0	12
2	1	0	1	0	16
-40	-30	0	0	1	0

4.5. Step 4: Identify the Leaving Variable and Pivot Element

In the Simplex algorithm, the leaving variable is the basic variable that exits the basis during an iteration.

To determine the leaving variable, we compute the ratio of the RHS to the positive coefficients in the pivot column. We choose the row with the smallest positive ratio because increasing the entering variable beyond this point would violate a constraint. This selection ensures the solution stays within the feasible region.

The pivot element is the intersection of the pivot row and pivot column, serving as the key value used to update the tableau. This step ensures a smooth transition to a new corner.

In Jane’s optimization problem, the pivot column is $x_1$ , and the ratios of the RHS to the positive coefficients in the $x_1$ column are:

for Row1: $\frac{12}{1} = 12$
for Row2: $\frac{16}{2} = 8$

Since Row2 has the smallest positive ratio, $s_2$ is the leaving variable. This makes the pivot element the one in the first column of Row2:

x1	x2	s1	s2	Z	RHS	Ratio = (RHS / x1)
1	1	1	0	0	12	12/1 = 12
2	1	0	1	0	16	16/2 = 8
-40	-30	0	0	1	0

4.6. Step 5: Perform the Pivot Operation

Once we identify the pivot element, we perform the pivot operation to update the tableau.

We do that by normalizing the pivot row (dividing it by the pivot element to make it 1) and adjusting all other rows, including the Z-row, to make every other entry in the pivot column zero. This ensures the basic variable associated with the pivot column is correctly incorporated into the solution.

In Jane’s problem, the pivot element is 2 in the first column of Row2. So, we normalize Row2 by dividing it by 2 so the pivot element becomes 1:

x1	x2	s1	s2	Z	RHS	Row Operation
1	1	1	0	0	12
1	1/2	0	1/2	0	8	New Row2 = Row2/2
-40	-30	0	0	1	0

Next, we adjust Row1 to make the pivot column entry zero using this operation:

$\text{New Row1} = \ \text{Row1} - 1 \times \text{New Row2} \quad \rightarrow \quad [0, 0.5, 1, -0.5, 0, 4]$

Finally, we update the Z-row (Row3) to eliminate the pivot column coefficient, ensuring alignment with the objective function:

$\text{New Row3} = Z + 40 \times \text{New Row2} \quad \rightarrow \quad [0, -10, 0, 20, 1, 320]$

Here’s the updated tableau:

x1	x2	s1	s2	Z	RHS	Row Operation
0	1/2	1	-1/2	0	4	New Row1 = Row1 – New Row2
1	1/2	0	1/2	0	8
0	-10	0	20	1	320	New Row3 = Z + 40 New Row2

4.7. Step 6: Repeat Until Optimality

We repeat steps 3 to 5 until all the coefficients in the objective row (Z-row) are non-negative. That will indicate we’ve found the optimal solution.

In our current tableau for Jane’s optimization problem, the Z-row still contains a negative value, $-10$ , so we must return to step 3 to start the next iteration.

The most negative number in the bottom row is $-10$ , which identifies the pivot column. So, we calculate the ratios of the RHS to the pivot column for each row:

$\frac{4}{\frac{1}{2}} = 4 \div \frac{1}{2} = 4 \times 2 = 8$

$\frac{8}{\frac{1}{2}} = 8 \div \frac{1}{2} = 8 \times 2 = 16$

Since 8 is the smallest positive quotient, it determines the pivot row.

The new tableau becomes:

x1	x2	s1	s2	Z	RHS	Ratio = (RHS / x2)
0	1/2	1	-1/2	0	4	4/(1/2) = 8
1	1/2	0	1/2	0	8	8/(1/2) = 16
0	-10	0	20	1	320

Therefore, $\frac{1}{2}$ in Row1 (yellow box) is the pivot element. We need to convert this to 1 and all entries below to 0. To change the pivot entry to 1, we multiply Row1 by $\frac{2}{1} = 2$ .

Here’s the updated tableau:

x1	x2	s1	s2	Z	RHS	Row Operations
0	1	2	-1	0	8	New Row2 = 2 Row1
1	1/2	0	1/2	0	8
0	-10	0	20	1	320

To get zeroes below the pivot entry, we replace Row2 with Row2 – (1/2)Row1 and Row3 with Row3 + 10 Row1:

x1	x2	s1	s2	Z	RHS	Row Operations
0	1	2	-1	0	8
1	0	-1	1	0	4	Row2 = Row2 – (1/2) Row1
0	0	20	10	1	400	New Row3 = Row3 + 10 Row1

We no longer have negative entries in the final row. So, we got the solution!

4.8. Step 7: Interpret the Solution

Now that we have the final tableau, the basic variables—those whose columns have 1 and all other entries 0—give us their values directly from the RHS. Meanwhile, non-basic variables are zero, meaning they don’t contribute directly to forming a feasible solution.

From our final tableau, we get:

$x_1 = 4, \quad x_2 = 8, \quad \text{and} \quad Z = 400$

This tells us Jane should work 4 hours at Job I and 8 hours at Job II to maximize her income, resulting in a total of $400.

4.9. Special Cases

In Step 4 of the Simplex algorithm, if no valid pivot row exists, the objective function is unbounded.

If multiple rows tie during the ratio test, one is selected arbitrarily, but caution is needed as this can lead to cycling.

If the initial tableau has negative RHS values and no valid pivot operations can be performed, the problem is infeasible.

5. Pseudocode for the Simplex Algorithm

Here’s the pseudocode for the Simplex algorithm:

algorithm SimplexAlgorithm(tableau):
    // INPUT
    //    tableau = the initial simplex tableau
    // OUTPUT
    //    optimal solution (if it exists)

    // Step 1: Repeat until the solution is optimal
    while there exists a negative coefficient in the objective row:
        
        // Step 2: Identify the pivot column (entering variable)
        pivotColumn <- index of the most negative coefficient in the objective row
        
        // Step 3: Identify the pivot row (leaving variable)
        // Calculate the ratio of the right-hand side (RHS) to the pivot column value
        // Consider only rows with positive pivot column values
        smallestRatio <- infinity
        for each row i in the tableau:
            if value in pivotColumn at row i > 0:
                ratio <- RHS[i] / value in pivotColumn at row i
                if ratio < smallestRatio:
                    smallestRatio <- ratio
                    pivotRow <- i

        // Step 4: Perform the pivot operation
        // Normalize the pivot row
        pivotElement <- value at (pivotRow, pivotColumn)
        for each column j in the tableau:
            tableau[pivotRow][j] <- tableau[pivotRow][j] / pivotElement

        // Make all other entries in the pivot column zero
        for each row k in the tableau (k != pivotRow):
            factor <- tableau[k][pivotColumn]
            for each column j in the tableau:
                tableau[k][j] <- tableau[k][j] - factor * tableau[pivotRow][j]

    // Step 5: Extract the solution
    solution <- array of zeros with length equal to number of variables
    for each column corresponding to a basic variable:
        if column has a single 1 and all other entries are 0:
            solution[variableIndex] <- value in RHS of corresponding row
    return solution

6. Implementations and Alternatives

Libraries such as SciPy in Python, MATLAB’s linprog, and R’s lpSolve package provide efficient implementations of Simplex.

However, the Simplex algorithm can struggle with extremely large problems due to its exponential time complexity. In such cases, metaheuristics like Particle Swarm optimization or Genetic Algorithms offer faster, albeit approximate, solutions.

Additionally, approximation algorithms, such as interior-point methods, guarantee near-optimal results within a specific range (e.g., 10% of the optimal value) and can handle large datasets more efficiently.

7. Conclusion

In this article, we explored how the Simplex algorithm finds the optimal solution to a linear problem. It’s always at a corner point of the feasible region, and the Simplex algorithm finds it iteratively.

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex

Full Archive

About Baeldung