Simplex Tableau
What's Happening
◆ THE BLUEPRINT
The Simplex Tableau

The tableau stores the current linear system in a compact form. Each row corresponds to a constraint. The bottom row (z-row) holds the reduced costs.

Reduced Costs

The reduced cost for nonbasic variable \(j\) is:

\(\bar{c}_j = c_j - \mathbf{c}_B^\top B^{-1} \mathbf{A}_j\)

The vector \(B^{-1}\mathbf{A}_j\) is the entering column in the tableau. It tells us how the basic variables change when we increase \(x_j\). The reduced cost measures the net change in the objective per unit increase.

When Does the Algorithm Stop?

The simplex method pivots as long as some \(\bar{c}_j < 0\). A negative reduced cost means moving along that edge of the polytope improves the objective.

When all \(\bar{c}_j \geq 0\), no neighboring vertex is better. The current BFS is optimal.

Connection to Duality

Define \(\mathbf{p} = \mathbf{c}_B^\top B^{-1}\). These are the dual variables (shadow prices). Then:

\(\bar{c}_j = c_j - \mathbf{p}^\top \mathbf{A}_j\)

At optimality, \(\bar{c}_j \geq 0\) for all \(j\) means \(\mathbf{p}^\top A \leq \mathbf{c}^\top\). This is dual feasibility. The simplex method builds toward both primal optimality and dual feasibility at the same time.

Pivot Rules (Dantzig)

Entering variable: choose the most negative reduced cost. Leaving variable: minimum ratio test (smallest \(b_i / a_{ij}\) for \(a_{ij} > 0\)).

Special Cases

Unbounded: All entries in the entering column are \(\leq 0\). No leaving variable exists.
Degenerate: \(\theta^* = 0\). The basis changes but the BFS stays the same. Risk of cycling.
Infeasible: Big-M artificial variable remains positive at optimality.

Reference

Bertsimas & Tsitsiklis, Introduction to Linear Optimization , Chapter 3.

Feasible Directions at Selected Vertex
Direction Details
◆ THE BLUEPRINT
Basic Feasible Solutions

A BFS corresponds to a vertex of the polytope. At each vertex, the number of active (tight) constraints equals the number of variables.

Basic Feasible Directions

At a BFS with basis \(B\), each nonbasic variable \(j\) defines a basic feasible direction:

\(\mathbf{d}_B = -B^{-1}\mathbf{A}_j, \quad d_j = 1, \quad d_k = 0 \text{ (other nonbasic)}\)
Step Size

The maximum step \(\theta^*\) keeps us feasible:

\(\theta^* = \min_{i: d_{B(i)} < 0} \frac{x_{B(i)}}{|d_{B(i)}|}\)

Geometrically, this is the distance along the polytope edge to the next vertex.

Reduced Costs

The reduced cost \(\bar{c}_j\) gives the rate of change of the objective along direction \(\mathbf{d}_j\). Negative reduced cost means moving along that direction improves the objective.

Why Simplex Moves Along Edges

Each basic direction corresponds to an edge of the polytope. The simplex method picks the most improving edge and moves to the adjacent vertex.

Reference

Bertsimas & Tsitsiklis, Introduction to Linear Optimization , Chapter 3.

Primal Problem (x-space)
Shadow Prices
Complementary Slackness
◆ THE BLUEPRINT
The Dual Problem

For the primal: min \(\mathbf{c}^\top\mathbf{x}\) s.t. \(A\mathbf{x} = \mathbf{b}\), \(\mathbf{x} \geq 0\), the dual is:

\(\max \; \mathbf{p}^\top\mathbf{b} \quad \text{s.t.} \; \mathbf{p}^\top A \leq \mathbf{c}^\top\)
Shadow Prices

The optimal dual variables \(\mathbf{p}^* = \mathbf{c}_B^\top B^{-1}\) are shadow prices. The shadow price \(p_i\) gives the rate of change of the optimal objective with respect to \(b_i\).

Weak Duality

For any primal feasible \(\mathbf{x}\) and dual feasible \(\mathbf{p}\): \(\mathbf{c}^\top\mathbf{x} \geq \mathbf{p}^\top\mathbf{b}\). The primal objective always bounds the dual from above.

Strong Duality

At optimality: \(\mathbf{c}^\top\mathbf{x}^* = \mathbf{p}^{*\top}\mathbf{b}\). The gap closes completely.

Complementary Slackness

At optimality, for every variable \(j\): \(x_j \cdot \bar{c}_j = 0\). A variable is either zero or its reduced cost is zero. This connects primal and dual optimality.

Reference

Bertsimas & Tsitsiklis, Introduction to Linear Optimization , Chapter 4.