Simplex in 3D

Visualizing the Simplex Method traversing a 3D Polyhedron

Simplex Method in Three Dimensions

In two dimensions, the feasible region of a Linear Program (LP) is a polygon, and the Simplex method moves along its boundary edges. In three dimensions, the feasible region is a polyhedron (a 3D solid bounded by flat polygon faces).

We trace the Simplex method on the following 3D LP:

\[ \begin{aligned} & \text{maximize} && z = 3x_1 + x_2 + 2x_3 \\ & \text{subject to} && x_1 \leq 4 && \text{(Constraint 1, slack } s_1\text{)} \\ & && x_2 \leq 4 && \text{(Constraint 2, slack } s_2\text{)} \\ & && x_3 \leq 4 && \text{(Constraint 3, slack } s_3\text{)} \\ & && x_1 + x_2 + x_3 \leq 6 && \text{(Constraint 4, slack } s_4\text{)} \\ & && x_1, x_2, x_3 \geq 0 \end{aligned} \]

The Simplex Iteration: Column Exchange & Reduced Costs

At its core, the Simplex method is a column exchange algorithm (often described as “one column in, one column out”). Mathematically, the system of constraints is represented in matrix form as \(Ax = b\) (with \(x \geq 0\)). We partition the columns of the constraint matrix \(A\) into: * Basic columns \(B = A_{\mathcal{B}}\), forming an invertible matrix of size \(m \times m\). The corresponding variables \(x_{\mathcal{B}}\) are the basic variables. * Non-basic columns \(N = A_{\mathcal{N}}\), containing the remaining \(n - m\) columns. The corresponding non-basic variables \(x_{\mathcal{N}}\) are set to zero in the current Basic Feasible Solution (BFS).

Each iteration of the Simplex method swaps exactly one column from the non-basic set into the basis (the entering column), and in turn, drops one column from the basic set (the leaving column). Geometrically, this column swap corresponds to moving along an edge of the 3D feasible polyhedron from the current vertex (BFS) to an adjacent vertex.

1. Reduced Costs: The Criteria to Let a Column In

To determine which column to let in, we look at the reduced costs. By solving the constraint system for the basic variables (\(x_{\mathcal{B}} = B^{-1}b - B^{-1}Nx_{\mathcal{N}}\)) and substituting this into the objective function \(z = c^{\top}x\), we rewrite the objective solely in terms of the non-basic variables: \[z = \bar{z} + \sum_{j \in \mathcal{N}} \hat{c}_j x_j\] where \(\hat{c}_j\) is the reduced cost of the non-basic variable \(x_j\), defined as: \[\hat{c}_j = c_j - c_{\mathcal{B}}^{\top} B^{-1} A_j\]

The reduced cost \(\hat{c}_j\) represents the rate of change of the objective value \(z\) per unit increase of the non-basic variable \(x_j\) (i.e. letting its column \(A_j\) enter the basis). * Optimality Check: If the reduced costs of all non-basic columns are non-positive (\(\hat{c}_j \leq 0\) for all \(j \in \mathcal{N}\)), the current BFS is optimal. No column can enter the basis to improve the objective. We stop. * If at least one column has a positive reduced cost \(\hat{c}_j > 0\), the solution can be improved, and we must select an entering column.

2. Rules to Decide What Column to Let In

If multiple non-basic columns have positive reduced costs, we must choose which one enters the basis. Different selection rules exist:

Dantzig’s Rule (Largest Coefficient): \[j^* = \arg\max_{j \in \mathcal{N}} \hat{c}_j\] We select the column with the largest positive reduced cost to enter the basis. This rule chooses the direction that provides the steepest rate of improvement per unit increase of the entering variable.
Bland’s Rule (Smallest Index): \[j^* = \min \{ j \in \mathcal{N} : \hat{c}_j > 0 \}\] We select the column with the smallest variable index among all columns that have a positive reduced cost. This rule is crucial because it is mathematically guaranteed to prevent cycling (getting stuck in a loop of degenerate pivots) and ensures the algorithm will terminate.

3. Ratio Test: Deciding What Column Leaves

Once the entering column is selected, we must determine which basic column must leave the basis. We increase the entering variable \(x_{j^*}\) from zero while keeping all other non-basic variables at zero. This causes the basic variables to change according to: \[x_{\mathcal{B}(i)} = \bar{b}_i - \bar{a}_{i, j^*} x_{j^*}\] To maintain feasibility (\(x \geq 0\)), we cannot let any basic variable become negative. The maximum step we can take is given by the bottleneck threshold \(\theta^*\): \[\theta^* = \min_{i : \bar{a}_{i, j^*} > 0} \frac{\bar{b}_i}{\bar{a}_{i, j^*}}\] The basic variable that reaches zero first at this threshold becomes the leaving variable, and its corresponding column leaves the basis. This completes the column exchange (one column in, one out).

Interactive 3D Walkthrough

Use the stepper controls to walk through each pivot iteration of the Simplex method. Drag the 3D plot to rotate, and hover or click on vertices to inspect their basic/non-basic variables.

Feasible Polytope & Simplex Path

Drag to rotate | Scroll to zoom

viewof stepSlider = Inputs.range([0, 3], {value: 0, step: 1, label: "Simplex Step:"})

Iteration 0: Start

BFS Vertex: (0, 0, 0)Objective: z = 0

Basis \(\mathcal{B}\): s1, s2, s3, s4 | Non-Basis \(\mathcal{N}\): x1, x2, x3

Basic variables expressed in terms of non-basic variables (the dictionary representation):

{
  if (window.goToStep) {
    window.goToStep(stepSlider);
  }
}