From the free course Spring 2026 - Math 354 - Sections 02/04 on Lykke

The Simplex Method and Tableau Optimization

Key concepts: Simplex Tableau · Pivot Selection · Optimality Criterion · Entering and Leaving Variables · Iterative Improvement

The primary algorithmic approach for solving linear programming problems using iterative pivoting.

The Simplex Method and Tableau Optimization

The Simplex Method is arguably the most influential algorithm in the history of constrained optimization. Developed by George Dantzig in 1947, it provides a systematic, iterative procedure for navigating the vertices of a high-dimensional polytope to find the optimal value of a linear objective function. While modern interior-point methods offer better theoretical polynomial time complexity, the Simplex algorithm remains the workhorse of industrial solvers due to its efficiency in practice and its unique ability to perform "warm starts" after minor model modifications.

At its core, the Simplex method exploits a fundamental property of Linear Programming (LP): if an optimal solution exists, it must occur at an extreme point (vertex) of the feasible region. Instead of searching the infinite interior of the feasible set, the algorithm "hops" from one vertex to an adjacent one, ensuring that each move improves (or at least maintains) the value of the objective function.

Foundations: Standard and Canonical Forms

Before the Simplex method can be applied, a Linear Programming problem must be expressed in a specific mathematical structure. In academic and professional practice, we distinguish between Standard Form and Canonical Form.

Standard Form

A maximization problem is in Standard Form if:

  1. The objective function is to be maximized.
  2. All variables are non-negative ($x_i \ge 0$).
  3. All constraints are expressed as "less-than-or-equal-to" inequalities ($\sum a_{ij}x_j \le b_i$).
  4. All right-hand side constants are non-negative ($b_i \ge 0$).

Canonical Form

To perform the algebraic manipulations required by the Simplex method, we must convert inequalities into equalities. This is achieved by introducing Slack Variables. A problem is in Canonical Form if it consists of a system of linear equations $Ax = b$ where a subset of the columns of $A$ forms an identity matrix.

Definition: Slack Variable A non-negative variable $s_i$ added to a $\le$ constraint to convert it into an equality. For example, $2x + 3y \le 6$ becomes $2x + 3y + s_1 = 6$, where $s_1 \ge 0$.

Feature Standard Form Canonical Form
Constraint Type Inequalities ($\le$) Equalities ($=$)
Variable Count Original decision variables Decision + Slack/Artificial variables
Goal Geometric definition of the polytope Algebraic setup for Gauss-Jordan elimination
RHS ($b$) Must be non-negative Must be non-negative

The Simplex Tableau

The Simplex Tableau is a structured matrix used to organize the coefficients of the objective function and the constraints. It serves as a computational "dashboard" that tracks the current Basic Feasible Solution (BFS).

In any iteration, the variables are partitioned into two sets:

  1. Basic Variables (BV): Variables that currently form the basis (the identity matrix columns). Their values are determined by the right-hand side.
  2. Non-Basic Variables (NBV): Variables set to zero.

Tableau Anatomy

A typical maximization tableau is organized as follows:

  • The top row (often called the z-row) contains the coefficients of the objective function.
  • The remaining rows represent the constraints.
  • The last column (RHS) contains the current values of the basic variables.

The Simplex Algorithm: Iterative Improvement

The algorithm follows a rigorous cycle of selection and transformation. Each iteration represents a move from one vertex to an adjacent vertex with a better objective value.

1. Optimality Criterion

We examine the objective row (z-row). In a maximization problem, if all coefficients of the non-basic variables in the z-row are non-negative (assuming the form $z - \sum c_i x_i = 0$), the current solution is optimal. If any coefficients are negative, the objective can still be improved.

2. Pivot Selection: The Entering Variable

The non-basic variable with the most negative coefficient in the z-row is chosen as the Entering Variable. This variable will transition from zero to a positive value in the next iteration. This choice is a heuristic known as "Dantzig's Rule," aimed at increasing the objective function as steeply as possible.

3. The Minimum Ratio Test: The Leaving Variable

To maintain feasibility, we cannot increase the entering variable indefinitely. We must determine which basic variable hits zero first. For every row where the entering variable has a positive coefficient, we calculate the ratio: $$\text{Ratio} = \frac{\text{RHS Value}}{\text{Coefficient of Entering Variable}}$$ The row with the smallest non-negative ratio identifies the Leaving Variable. This row is called the Pivot Row.

4. Pivoting (Gauss-Jordan Elimination)

The intersection of the entering column and the leaving row is the Pivot Element. We perform row operations to:

  1. Turn the pivot element into a $1$.
  2. Turn all other elements in the entering column (including the z-row) into $0$.

Implementation: Low-Level Pivot Logic

The following Python implementation using NumPy demonstrates the core mechanics of a single Simplex iteration. Note the use of the minimum ratio test and row-wise transformations.

import numpy as np

def simplex_step(tableau):
    """
    Performs a single pivot iteration on a Simplex Tableau.
    Assumes maximization problem in the form: z - c1x1 - c2x2 ... = 0
    """
    n_rows, n_cols = tableau.shape
    z_row = tableau[0, :-1]
    
    # 1. Check Optimality / Select Entering Variable (Pivot Column)
    if np.all(z_row >= 0):
        return None, "Optimal"
    
    pivot_col = np.argmin(z_row)
    
    # 2. Minimum Ratio Test / Select Leaving Variable (Pivot Row)
    ratios = []
    for i in range(1, n_rows):
        val = tableau[i, pivot_col]
        rhs = tableau[i, -1]
        if val > 0:
            ratios.append(rhs / val)
        else:
            ratios.append(np.inf) # Cannot pivot on non-positive elements
            
    pivot_row = np.argmin(ratios) + 1 # +1 because we skipped z-row
    
    if ratios[pivot_row-1] == np.inf:
        return None, "Unbounded"

    # 3. Pivoting
    pivot_val = tableau[pivot_row, pivot_col]
    tableau[pivot_row, :] /= pivot_val
    
    for r in range(n_rows):
        if r != pivot_row:
            tableau[r, :] -= tableau[r, pivot_col] * tableau[pivot_row, :]
            
    return tableau, "Iterating"

# Example usage:
# Maximize z = 3x1 + 2x2 subject to 2x1 + x2 <= 4, 2x1 + 3x2 <= 6
# Tableau: [z, x1, x2, s1, s2, RHS]
example_tab = np.array([
    [1, -3, -2, 0, 0, 0],
    [0,  2,  1, 1, 0, 4],
    [0,  2,  3, 0, 1, 6]
], dtype=float)

new_tab, status = simplex_step(example_tab)
print(f"Status: {status}\nUpdated Tableau:\n{new_tab}")

Mathematical Derivation of the Pivot

To understand why the Simplex method works, we must look at the linear algebra of the basis. Let the constraints be $Ax = b$. We partition $A$ into $[B, N]$, where $B$ is the basis matrix (invertible) and $N$ represents non-basic columns.

The solution is given by: $$x_B = B^{-1}b - B^{-1}Nx_N$$ The objective function $z = c^T x$ becomes: $$z = c_B^T(B^{-1}b - B^{-1}Nx_N) + c_N^T x_N$$ $$z = c_B^T B^{-1}b + (c_N^T - c_B^T B^{-1}N)x_N$$

The term $(c_N^T - c_B^T B^{-1}N)$ is known as the Reduced Cost vector. If all reduced costs are non-positive (for maximization), then increasing any $x_N$ (which are currently 0) will decrease $z$. Thus, we are at the optimum.

\begin{aligned}
&\text{Algorithm: Simplex Method}\\
&\text{1: Identify initial BFS by setting } x_{non-basic} = 0 \\
&\text{2: } \mathbf{while} \ \exists \ \bar{c}_j < 0 \ \mathbf{do} \\
&\text{3: } \quad \text{Select } j \text{ such that } \bar{c}_j \text{ is most negative (Entering Variable)} \\
&\text{4: } \quad \mathbf{if} \ A_{ij} \le 0 \ \forall i \ \mathbf{then} \\
&\text{5: } \quad \quad \mathbf{return} \ \text{"Unbounded"} \\
&\text{6: } \quad \text{Select row } i \text{ such that } \frac{b_i}{A_{ij}} = \min_{k: A_{kj}>0} \frac{b_k}{A_{kj}} \text{ (Leaving Variable)} \\
&\text{7: } \quad \text{Perform pivot on } A_{ij} \text{ using Gauss-Jordan elimination} \\
&\text{8: } \mathbf{end \ while} \\
&\text{9: } \mathbf{return} \ \text{Current BFS}
\end{aligned}

Worked Example: Maximizing a Three-Variable System

Consider the following problem from Participation #4: Maximize: $z = 4x_1 + 2x_2 + 7x_3$ Subject to:

  1. $2x_1 - x_2 + 4x_3 \le 18$
  2. $4x_1 + 2x_2 + 5x_3 \le 10$
  3. $x_1, x_2, x_3 \ge 0$

Step 1: Convert to Canonical Form

Introduce slack variables $s_1, s_2$:

  1. $2x_1 - x_2 + 4x_3 + s_1 = 18$
  2. $4x_1 + 2x_2 + 5x_3 + s_2 = 10$ Objective: $z - 4x_1 - 2x_2 - 7x_3 = 0$

Step 2: Initial Tableau

Basis $z$ $x_1$ $x_2$ $x_3$ $s_1$ $s_2$ RHS
$z$ 1 -4 -2 -7 0 0 0
$s_1$ 0 2 -1 4 1 0 18
$s_2$ 0 4 2 5 0 1 10

Step 3: First Pivot

  • Entering: $x_3$ (most negative in z-row: -7).
  • Ratios:
    • Row 1 ($s_1$): $18 / 4 = 4.5$
    • Row 2 ($s_2$): $10 / 5 = 2$
  • Leaving: $s_2$ (smallest ratio).
  • Pivot Element: 5 (Row 2, Column $x_3$).

After pivoting on 5:

  1. Divide Row 2 by 5.
  2. $R_1 \leftarrow R_1 - 4R_2$
  3. $R_z \leftarrow R_z + 7R_2$

New Tableau:

Basis $z$ $x_1$ $x_2$ $x_3$ $s_1$ $s_2$ RHS
$z$ 1 1.6 0.8 0 0 1.4 14
$s_1$ 0 -1.2 -2.6 0 1 -0.8 10
$x_3$ 0 0.8 0.4 1 0 0.2 2

Result: All coefficients in the z-row are non-negative ($1.6, 0.8, 0, 0, 1.4$). The solution is optimal. Optimal Solution: $x_1=0, x_2=0, x_3=2, z=14$.

Advanced Scenarios and Pitfalls

While the Simplex method is robust, several edge cases can occur during the execution of the algorithm.

1. Degeneracy and Cycling

Degeneracy occurs when one or more basic variables have a value of zero. This happens when there is a tie in the Minimum Ratio Test.

  • The Risk: The algorithm might pivot without changing the objective value. In rare cases, it can enter an infinite loop (cycling).
  • The Solution: Use Bland’s Rule, which dictates choosing the variable with the lowest index in case of ties.

2. Unboundedness

If the entering variable has no positive coefficients in any constraint row, the ratio test fails.

  • Meaning: The feasible region is open in the direction of improvement. The objective function can be increased to infinity.

3. Infeasibility and the Two-Phase Method

If the origin $(0,0,...0)$ is not a feasible solution (e.g., if we have $\ge$ constraints), we cannot start the Simplex method directly.

  • Phase I: Introduce Artificial Variables and a new objective function to minimize the sum of these variables. If the minimum is 0, we have found a BFS for the original problem.
  • Phase II: Remove artificial variables and solve the original objective.
Problem State Tableau Indicator
Optimal All z-row coefficients $\ge 0$ (Max problem).
Unbounded Entering column has all entries $\le 0$.
Infeasible Phase I ends with a non-zero artificial variable.
Multiple Optima A non-basic variable has a 0 coefficient in the optimal z-row.

Real-World Usage: Large-Scale Solvers

In production environments, we rarely write our own Simplex solvers from scratch. Instead, we use high-performance libraries like Gurobi, CPLEX, or the open-source HiGHS. These solvers use the Revised Simplex Method, which maintains the basis inverse $B^{-1}$ explicitly or via LU factorization to save memory and computation time.

# Example: Solving an LP using the GLPK (GNU Linear Programming Kit)
# 1. Define the problem in a .mod or .lp file
cat <<EOF > problem.lp
Maximize
 obj: 4 x1 + 2 x2 + 7 x3
Subject To
 c1: 2 x1 - 1 x2 + 4 x3 <= 18
 c2: 4 x1 + 2 x2 + 5 x3 <= 10
Bounds
 x1 >= 0
 x2 >= 0
 x3 >= 0
End
EOF

# 2. Run the solver using the Simplex method
glpsol --lp problem.lp -o solution.txt

# 3. View the results
grep "Objective:" solution.txt

Summary of Key Insights

  1. Geometric Intuition: The Simplex method is a "greedy" walk along the edges of a polytope.
  2. Algebraic Engine: The tableau is a compact representation of Gauss-Jordan elimination tailored for optimization.
  3. The Ratio Test: This is the "safety valve" that prevents the algorithm from stepping outside the feasible region.
  4. Duality: Every Simplex step in the primal problem implicitly provides information about the dual problem (shadow prices), which are represented by the coefficients in the optimal z-row.

By mastering the tableau and the logic of pivots, one gains the ability to not only solve linear programs but to perform sensitivity analysis—understanding how changes in constraints or costs ripple through a complex system.

The Simplex Method and Tableau Optimization - Spring 2026 - Math 354 - Sections 02/04 - diagram 1
The Simplex Method and Tableau Optimization - Spring 2026 - Math 354 - Sections 02/04 - diagram 1

Source Materials

Study Spring 2026 - Math 354 - Sections 02/04 on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of Spring 2026 - Math 354 - Sections 02/04 · Browse more course pages

The Simplex Method and Tableau Optimization — Spring 2026 - Math 354 - Sections 02/04 | Lykke