Skip to content

Lesson 4: The Simplex Method I: Theory

4.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Define basic solution, basic feasible solution (BFS) and basis.
  2. State and use the theorem that BFS ⟺ extreme point.
  3. Count the maximum number of basic solutions and explain why enumeration is hopeless.
  4. Derive the optimality criterion (\(z_j - c_j\)) and the feasibility criterion (minimum ratio).
  5. State the simplex algorithm and explain why it terminates.

4.2 From Geometry to Algebra

L03 established that an optimum, if it exists, occurs at a corner. But in \(n\) dimensions you cannot draw the region. The simplex method's achievement is to characterise corners algebraically and to move between them systematically.

\[ \boxed{\ \textbf{Corner point (geometry)} \ \Longleftrightarrow\ \textbf{basic feasible solution (algebra)}\ } \]

4.3 Basic Solutions

Work in standard form: \(A\vec x = \vec b\) with \(\vec x \ge 0\), where \(A\) is \(m\times n\) with \(m < n\) and \(\mathrm{rank}(A) = m\).

The system is underdetermined — \(m\) equations, \(n\) unknowns — so it has infinitely many solutions. Simplex picks out a special finite subset.

Definition (Basic solution). Choose \(m\) of the \(n\) variables to be basic; set the remaining \(n - m\) non-basic variables to zero. If the resulting \(m\times m\) submatrix \(B\) (the basis matrix) is non-singular, solve

\[ B\vec x_B = \vec b \qquad\Longrightarrow\qquad \vec x_B = B^{-1}\vec b \]

The resulting \(\vec x\) is a basic solution.

Definition (Basic feasible solution, BFS). A basic solution with \(\vec x_B \ge \vec 0\).

Definition (Degenerate BFS). A BFS in which at least one basic variable equals zero.

The counting

The number of ways to choose which \(m\) variables are basic is

\[ \binom{n}{m} = \frac{n!}{m!\,(n-m)!} \]
\(m\) \(n\) \(\binom{n}{m}\)
2 4 6
3 6 20
5 10 252
10 20 184 756
20 40 \(1.4\times10^{11}\)
50 100 \(1.0\times10^{29}\)

Total enumeration is hopeless. At \(10^{9}\) solutions per second, the \(m=50\), \(n=100\) case would take \(3\times10^{12}\) years. Yet such problems are solved in milliseconds.

\[ \boxed{\ \textbf{The simplex method's genius is visiting only a tiny fraction of the corners — typically } O(m) \textbf{ of them.}\ } \]

4.4 The Central Theorem

Theorem. \(\vec x\) is a basic feasible solution of \(A\vec x = \vec b,\ \vec x\ge0\) if and only if \(\vec x\) is an extreme point of the feasible region.

Proof sketch (⟸). Let \(\vec x\) be an extreme point with positive components \(x_{j_1},\ldots,x_{j_k}\). If the corresponding columns \(\vec a_{j_1},\ldots,\vec a_{j_k}\) were linearly dependent, there would exist non-zero \(\vec d\) with \(A\vec d = 0\) supported on those indices; then \(\vec x \pm \epsilon\vec d\) would both be feasible for small \(\epsilon\), expressing \(\vec x\) as a midpoint — contradicting extremality. So the columns are independent, \(k \le m\), and they extend to a basis. \(\blacksquare\)

Corollary (the algorithm's licence). Since an optimum occurs at an extreme point (L03) and extreme points are exactly BFSs, it suffices to search over basic feasible solutions — a finite set.

4.5 The Simplex Tableau

Represent the system as a tableau. With \(c_B\) the objective coefficients of the basic variables:

Basis \(c_B\) \(x_1\) \(\cdots\) \(x_n\) RHS
\(x_{B_1}\) \(c_{B_1}\) \(a_{11}\) \(\cdots\) \(a_{1n}\) \(b_1\)
\(\vdots\)
\(x_{B_m}\) \(c_{B_m}\) \(a_{m1}\) \(\cdots\) \(a_{mn}\) \(b_m\)
\(z_j - c_j\) \(Z\)

Definition (the \(z_j\) row).

\[ z_j = \sum_{i=1}^{m} c_{B_i}\,a_{ij} = \vec c_B^{T}B^{-1}\vec a_j \]

Definition (reduced cost / net evaluation).

\[ \Delta_j = z_j - c_j \]

The economic meaning of z_j - c_j

Increasing a non-basic variable \(x_j\) by one unit:

  • Gains \(c_j\) directly from the objective.
  • Costs \(z_j\), because bringing in one unit of \(x_j\) forces the basic variables to adjust by \(-a_{ij}\) each, changing the objective by \(-\sum_i c_{B_i}a_{ij} = -z_j\).
\[ \boxed{\ \text{Net change in } Z \text{ per unit of } x_j \ =\ c_j - z_j \ =\ -\Delta_j\ } \]

So \(\Delta_j < 0\) means bringing \(x_j\) in improves \(Z\).

4.6 The Two Criteria

Optimality criterion (for maximisation)

\[ \boxed{\ \text{The current BFS is optimal} \iff z_j - c_j \ \ge\ 0 \ \text{ for all } j\ } \]

If any \(\Delta_j < 0\), the solution can be improved.

Entering variable rule (Dantzig's rule). Choose

\[ j^{*} = \arg\min_j\ (z_j - c_j) \]

— the most negative \(\Delta_j\), giving the steepest per-unit improvement.

(For minimisation, either convert to maximisation, or reverse: optimal when all \(z_j - c_j \le 0\), and enter the most positive.)

Feasibility criterion (the minimum-ratio test)

Once \(x_{j^*}\) is chosen to enter, how far can it increase? Basic variable \(x_{B_i}\) changes as

\[ x_{B_i} = b_i - a_{ij^*}\,x_{j^*} \]

which stays non-negative only while

\[ x_{j^*} \le \frac{b_i}{a_{ij^*}} \qquad \text{for every } i \text{ with } a_{ij^*} > 0 \]
\[ \boxed{\ \theta = \min_{i\,:\,a_{ij^*}>0} \ \frac{b_i}{a_{ij^*}}\ } \]

The row \(r\) achieving the minimum determines the leaving variable \(x_{B_r}\), and \(a_{rj^*}\) is the pivot element.

Three rules that follow immediately.

  1. Ignore rows with \(a_{ij^*} \le 0\) — increasing \(x_{j^*}\) increases those basic variables, so they never become negative and impose no limit.
  2. If no \(a_{ij^*} > 0\) exists, the problem is UNBOUNDED — \(x_{j^*}\) can grow forever.
  3. A tie in the ratio test ⟹ degeneracy at the next iteration (some basic variable becomes 0).

The pivot operation

Gauss–Jordan elimination on the pivot column:

1. Divide the pivot row by the pivot element  ->  pivot becomes 1
2. For every other row i:   row_i  <-  row_i  -  a[i][pivcol] * (new pivot row)
3. Replace x_{B_r} by x_{j*} in the basis list
4. Recompute the z_j - c_j row

4.7 The Algorithm and Its Termination

SIMPLEX (maximisation, standard form)

1. Find an initial BFS (slacks form the basis if all constraints are <=)
2. Compute z_j - c_j for all j
3. If all z_j - c_j >= 0  ->  STOP, optimal
4. Choose entering column j* = argmin (z_j - c_j)
5. If no a[i][j*] > 0  ->  STOP, unbounded
6. Choose leaving row r by the minimum-ratio test
7. Pivot on a[r][j*]
8. Go to 2

Why it terminates. Each iteration moves to an adjacent BFS with a strictly better objective value (provided no degeneracy). There are finitely many BFSs, and no value repeats, so the algorithm must stop.

The degeneracy caveat. With a degenerate BFS, the ratio test can give \(\theta = 0\), so the objective does not improve; in principle the algorithm can cycle. Two safeguards exist:

  • Bland's rule — among candidates, always choose the one with the smallest index. Guarantees termination, but is slow.
  • Lexicographic (perturbation) rule — perturb \(\vec b\) slightly to break all ties.

In practice cycling is vanishingly rare, and commercial solvers use Bland's rule only as a fallback after detecting stalling.

Complexity — theory versus practice

Measure Result
Worst case exponential — the Klee–Minty cube (1972) forces \(2^{n}-1\) iterations
Average case \(O(m)\) to \(O(m\log n)\) pivots (Borgwardt, Smale; smoothed analysis by Spielman–Teng, 2004)
Practical rule of thumb \(2m\) to \(3m\) iterations
Guaranteed polynomial alternatives ellipsoid (Khachiyan 1979, impractical); interior point (Karmarkar 1984, practical)

A genuine paradox worth telling students. Simplex is exponential in the worst case yet is the algorithm of choice in practice, while the ellipsoid method is polynomial yet unusable. Worst-case complexity is not the same as practical performance.

4.8 Solved Problems

Problem 1 — Enumerating all basic solutions

For the system \(6x_1+4x_2+s_1 = 24\), \(x_1+2x_2+s_2 = 6\) (from L03), enumerate all basic solutions and identify which are feasible.

Solution.

\(m = 2\), \(n = 4\), so there are \(\binom{4}{2} = 6\) basic solutions.

Basis \(\{s_1, s_2\}\). Set \(x_1 = x_2 = 0\):

\[ s_1 = 24,\ s_2 = 6 \ \Rightarrow\ (x_1,x_2) = (0,0) \ \textbf{FEASIBLE} \]

Basis \(\{x_1, s_2\}\). Set \(x_2 = s_1 = 0\): \(6x_1 = 24 \Rightarrow x_1 = 4\); \(4 + s_2 = 6 \Rightarrow s_2 = 2\):

\[ (x_1,x_2) = (4,0) \ \textbf{FEASIBLE} \]

Basis \(\{x_2, s_2\}\). Set \(x_1 = s_1 = 0\): \(4x_2 = 24 \Rightarrow x_2 = 6\); \(12+s_2 = 6\Rightarrow s_2 = -6\):

\[ (0,6) \ \textbf{INFEASIBLE} \ (s_2 < 0) \]

Basis \(\{x_1, s_1\}\). Set \(x_2 = s_2 = 0\): \(x_1 = 6\); \(36 + s_1 = 24 \Rightarrow s_1 = -12\):

\[ (6,0) \ \textbf{INFEASIBLE} \]

Basis \(\{x_2, s_1\}\). Set \(x_1 = s_2 = 0\): \(2x_2 = 6\Rightarrow x_2 = 3\); \(12 + s_1 = 24\Rightarrow s_1 = 12\):

\[ (0,3) \ \textbf{FEASIBLE} \]

Basis \(\{x_1, x_2\}\). Set \(s_1 = s_2 = 0\): solve \(6x_1+4x_2 = 24\), \(x_1+2x_2 = 6\):

\[ x_1 = 3,\ x_2 = 1.5 \ \textbf{FEASIBLE} \]

Summary.

Basis \((x_1,x_2)\) Feasible? \(Z = 5x_1+4x_2\)
\(\{s_1,s_2\}\) \((0,0)\) ✓ 0
\(\{x_1,s_2\}\) \((4,0)\) ✓ 20
\(\{x_2,s_1\}\) \((0,3)\) ✓ 12
\(\{x_1,x_2\}\) \((3,1.5)\) ✓ 21
\(\{x_2,s_2\}\) \((0,6)\) ✗ —
\(\{x_1,s_1\}\) \((6,0)\) ✗ —

Exactly the 4 feasible ones are the 4 corners found graphically in L03 ✓, confirming the BFS ⟺ extreme-point theorem. The 2 infeasible basic solutions correspond to intersections of constraint lines outside the feasible region.

Problem 2 — Computing and interpreting z_j - c_j

For the tableau below with \(c = (5, 4, 0, 0)\), compute the \(z_j - c_j\) row and decide whether the solution is optimal.

Basis \(c_B\) \(x_1\) \(x_2\) \(s_1\) \(s_2\) RHS
\(x_1\) 5 1 2/3 1/6 0 4
\(s_2\) 0 0 4/3 −1/6 1 2

Solution.

\[ z_j = \sum_i c_{B_i}a_{ij} = 5a_{1j} + 0\cdot a_{2j} = 5a_{1j} \]
\(j\) \(a_{1j}\) \(z_j = 5a_{1j}\) \(c_j\) \(z_j - c_j\)
\(x_1\) 1 5 5 \(0\)
\(x_2\) 2/3 10/3 4 \(10/3 - 4 = \mathbf{-2/3}\)
\(s_1\) 1/6 5/6 0 \(\mathbf{5/6}\)
\(s_2\) 0 0 0 \(0\)

Current objective. \(Z = c_B^{T}\vec b = 5(4) + 0(2) = \mathbf{20}\).

Optimality check. \(z_2 - c_2 = -2/3 < 0\) ⟹ NOT optimal.

Interpretation of \(-2/3\). Bringing one unit of \(x_2\) into the solution changes \(Z\) by \(-(z_2-c_2) = +2/3\). Concretely: one unit of \(x_2\) earns \(c_2 = 4\) directly, but forces \(x_1\) down by \(2/3\) (its column entry), losing \(\frac23 \times 5 = \frac{10}{3}\). Net: \(4 - \frac{10}{3} = \frac{2}{3} > 0\) ✓ — an improvement.

Interpretation of \(z_{s_1} - c_{s_1} = 5/6\). This is the shadow price of resource 1: one extra unit of that resource is worth ₹5/6 of additional profit. Equivalently, forcing one unit of slack back in costs 5/6.

The minimum-ratio test. Entering \(x_2\) (column \(2/3\), \(4/3\)):

\[ \theta = \min\left\{\frac{4}{2/3},\ \frac{2}{4/3}\right\} = \min\{6,\ 1.5\} = \mathbf{1.5}, \ \text{ in row 2} \]

So \(s_2\) leaves, \(x_2\) enters, and \(x_2\) will take the value \(1.5\) — matching the graphical optimum \((3, 1.5)\) of L03 ✓.

Problem 3 — Detecting unboundedness algebraically

A tableau has entering column \(x_2\) with entries \((-2, -3)\) and RHS \((5, 8)\). What happens?

Solution.

No entry in the pivot column is positive, so the minimum-ratio test has no candidates.

Why this means unbounded. The basic variables update as

\[ x_{B_1} = 5 - (-2)x_2 = 5 + 2x_2, \qquad x_{B_2} = 8 - (-3)x_2 = 8 + 3x_2 \]

Both increase as \(x_2\) grows, so feasibility is never violated:

\[ x_2 \to \infty \ \Longrightarrow\ x_{B_1}, x_{B_2} \to \infty, \ \text{ all still } \ge 0 . \]

And since \(z_2 - c_2 < 0\) (that is why \(x_2\) was chosen), \(Z\) increases without bound.

\[ \boxed{\ \textbf{UNBOUNDED: no positive entry in the pivot column.}\ } \]

The direction of unboundedness. The ray is

\[ \vec x(t) = \vec x^{(0)} + t\,\vec d, \qquad \vec d = (\ldots,\ \underbrace{1}_{x_2},\ldots,\ 2,\ 3,\ldots) \]

— i.e. increase \(x_2\) by 1 and the two basic variables by 2 and 3 respectively.

What to do in practice. Report the ray to the modeller. It shows exactly which activity can grow without limit, which almost always identifies the missing constraint. If the model says you can make infinite profit by producing more of product 2, you forgot product 2's capacity limit.

Problem 4 — Degeneracy and its consequences

A minimum-ratio test gives ratios \(\{6, 4, 4\}\). Explain the consequence and the risk.

Solution.

A tie at \(\theta = 4\) between two rows. Either may be chosen to leave.

Consequence. Suppose row 2 leaves. Then row 3 had ratio \(4\) as well, so after pivoting:

\[ x_{B_3}^{\text{new}} = 4 - 4\times1 = \mathbf{0} \]

The new BFS has a basic variable equal to zero — it is degenerate.

Geometric meaning. Three or more constraints pass through the same corner (in 2-D, more lines meet at a point than the two needed). The same geometric corner corresponds to several different bases.

The risk — stalling and cycling. At a degenerate vertex the next minimum ratio may be \(\theta = 0\), so the pivot changes the basis but not the solution or the objective. If a sequence of such pivots returns to a previously visited basis, the algorithm cycles forever.

The classic example (Beale, 1955).

\[ \max\ \tfrac{3}{4}x_1 - 150x_2 + \tfrac{1}{50}x_3 - 6x_4 \]
\[ \text{s.t. } \tfrac14x_1 - 60x_2 - \tfrac{1}{25}x_3 + 9x_4 \le 0, \quad \tfrac12x_1 - 90x_2 - \tfrac{1}{50}x_3 + 3x_4 \le 0, \quad x_3 \le 1 \]

With Dantzig's rule this cycles after 6 pivots, returning to the starting basis.

Two remedies.

Rule Statement Cost
Bland's rule among eligible entering columns, take the smallest index; among tied leaving rows, take the variable with the smallest index provably terminates, but often many more pivots
Lexicographic rule perturb \(b_i \to b_i + \epsilon^{i}\), making all ratios distinct provably terminates, more bookkeeping

Practical reality. Degeneracy is common (especially in transportation and assignment problems) but cycling is essentially never observed on real data — floating-point noise breaks the exact ties. Solvers monitor for stalling and switch to Bland's rule if the objective fails to improve for many iterations.

Problem 5 — Why simplex beats enumeration

An LP has \(m = 30\) constraints and \(n = 80\) variables (after adding slacks). Compare complete enumeration of basic solutions with the expected simplex effort.

Solution.

Complete enumeration.

\[ \binom{80}{30} = \frac{80!}{30!\,50!} \approx 8.87\times10^{21} \]

Each candidate requires solving a \(30\times30\) system, roughly \(\frac{2}{3}(30)^3 \approx 18{,}000\) floating-point operations. Total:

\[ 8.87\times10^{21}\times1.8\times10^{4} = 1.6\times10^{26}\ \text{flops} \]

At \(10^{12}\) flops/second (a fast workstation):

\[ t = 1.6\times10^{14}\ \mathrm{s} \approx \mathbf{5\ \text{million years}} \]

Simplex.

Empirically simplex needs about \(2m\) to \(3m\) pivots:

\[ \approx 2.5\times30 = \mathbf{75\ \text{iterations}} \]

Each pivot is a Gauss–Jordan elimination over the tableau: \(O(mn) = 30\times80 = 2400\) operations.

\[ \text{Total} = 75\times2400 = 1.8\times10^{5}\ \text{flops} \ \Longrightarrow\ t \approx \mathbf{0.18\ \mu s} \]

The comparison.

\[ \frac{5\times10^{6}\ \text{years}}{1.8\times10^{-7}\ \text{s}} \approx \mathbf{10^{21}\times\ \text{faster}} \]
\[ \boxed{\ \textbf{Simplex visits about 75 of } 8.9\times10^{21} \textbf{ corners — a fraction of } 10^{-20}.\ } \]

How can it possibly be right? Because of convexity. The optimality criterion \(z_j - c_j \ge 0\) is a local test — it examines only the corners adjacent to the current one. Convexity guarantees that a corner better than all its neighbours is better than every corner in the region. Simplex never needs to look further.

\[ \boxed{\ \textbf{Convexity converts a global search into a local one. That is the whole trick.}\ } \]

(This is also why the same idea fails for integer programming (L16–L18) and non-convex non-linear programming (Unit IV): without convexity, local optimality does not imply global optimality, and the search really can require exponential effort.)

4.9 Practice Problems

  1. How many basic solutions for \(m=3\), \(n=7\)? [Ans: 35]
  2. Given \(c_B = (3,5)\) and column \(\vec a_j = (2,1)^T\) with \(c_j = 8\), compute \(z_j - c_j\). [Ans: \(11-8=3\)]
  3. Ratios are \(\{8, 3, 12\}\) — which row leaves, and what is \(\theta\)? [Ans: row 2, \(\theta=3\)]
  4. Pivot column \((-1, 0, -4)^T\): what do you conclude? [Ans: unbounded]
  5. State the optimality criterion for a minimisation problem in simplex form.
  6. Prove that increasing a non-basic variable changes \(Z\) at rate \(c_j - z_j\).
  7. Explain, in two sentences, why convexity lets a local test certify global optimality.

4.10 Summary

  • Standard form has \(m\) equations and \(n > m\) variables. Choosing \(m\) basic variables and setting the rest to zero gives a basic solution; if it is non-negative it is a BFS.
  • BFS ⟺ extreme point — this theorem is what licenses an algebraic search for a geometric optimum.
  • There are up to \(\binom{n}{m}\) basic solutions — astronomically many, so enumeration is impossible.
  • \(z_j - c_j\) is the net rate at which \(Z\) worsens per unit of \(x_j\); the solution is optimal (for max) when all \(z_j - c_j \ge 0\). The entering variable is the most negative.
  • Minimum-ratio test \(\theta = \min_i \{b_i/a_{ij^*} : a_{ij^*}>0\}\) picks the leaving variable and preserves feasibility. No positive entry ⟹ unbounded; a tie ⟹ degeneracy.
  • Simplex terminates because each pivot strictly improves \(Z\) over a finite set of BFSs; degeneracy can cause stalling, cured by Bland's or the lexicographic rule.
  • Worst case is exponential (Klee–Minty) but practice is \(2m\)–\(3m\) pivots — around \(10^{21}\times\) faster than enumeration on a modest problem.
  • Convexity is why a local optimality test certifies a global optimum. Losing convexity (integer or non-convex problems) destroys this and is why those problems are hard.

Next lesson: L05 — The simplex tableau algorithm, worked in full.

Practise now: unit1-lp-lab.html → Basic Solutions Explorer: pick any two variables to be basic and see the resulting point plotted, with feasibility flagged.