Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 38 ยท Simplex Method

The Simplex Method by Hand: Tableaux

Learn the simplex method with tableaux: entering variable, ratio test, pivoting and optimality, working the bakery example step by step with Python tableaux.

The simplex method (George Dantzig, 1947) solves an LP by walking from vertex to adjacent vertex, always improving the objective, until no neighbour is better. This lesson teaches it the classic way, with a tableau: a table you update with simple row operations. You will follow the bakery problem all the way to the optimum and check every step with code.

Setup: maximize with <= constraints

We start with the easiest case: maximize c . x subject to Ax <= b, x >= 0, and b >= 0. Adding slack variables gives the starting basic solution x = 0, slacks = b. This origin is feasible because b >= 0, so no search for a starting vertex is needed.

For the bakery, the initial tableau (columns x, y, s1, s2, s3 | rhs) is

TEXT
basis |  x    y   s1  s2  s3 | rhs
 s1   |  2    1    1   0   0 | 100
 s2   |  1    1    0   1   0 |  80
 s3   |  1    0    0   0   1 |  40
 z    | -40 -30    0   0   0 |   0

The bottom row, the objective row, contains -c (written as z - 40x - 30y = 0). Reading it: a negative entry means increasing that variable would increase z.

The three-step iteration

  1. Choose the entering variable. Pick a column with a negative entry in the objective row (Dantzig's rule: the most negative). If there is none, the current solution is optimal.
  2. Ratio test: choose the leaving variable. For each row with a positive entry a_ik in the entering column k, compute rhs_i / a_ik. The smallest ratio's row leaves. This is how far you can increase the entering variable before some basic variable hits zero. If no entry is positive, the LP is unbounded.
  3. Pivot. Divide the pivot row by the pivot element, then subtract multiples of it from every other row (including the objective row) so the entering column becomes a unit vector.

Step by step on the bakery: the most negative objective entry is -40 (variable x). Ratios: 100/2 = 50, 80/1 = 80, 40/1 = 40. The minimum is 40, so s3 leaves and x enters. After pivoting we are at (40, 0) with profit 1600. Next y enters (entry -30), the ratios pick s1, and we reach (40, 20). One more pivot reaches (20, 60).

The tableau in code

Python Watch the simplex pivots

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You can read the final tableau directly:

  • The right-hand column holds the values of the basic variables.
  • The bottom-right entry is the optimal profit, 2600.
  • The objective-row entries under the slack columns are the shadow prices (10 for oven, 20 for labor, 0 for flour). The simplex tableau computes duals as a by-product; we prove that in the dual problem.

Why it works

Each pivot replaces one basic variable by another. Algebraically, the tableau always expresses the basic variables and the objective in terms of the non-basic variables, which are all zero at the current vertex. The objective row entry for a non-basic variable is its reduced cost: the rate at which z changes if you raise that variable from zero while keeping the equations satisfied. If all reduced costs are non-negative (in the sign convention above), no direction improves z, and we are at an optimum.

The ratio test guarantees that the new solution is still feasible: it stops as soon as one basic variable reaches 0, so every pivot lands exactly on a neighbouring vertex.

A minimization example

For minimization, either negate the objective (maximize -c . x) or flip the rule: choose a column with a positive reduced cost. The easiest habit is to negate and reuse the maximization code, as long as you remember to flip the sign of the final answer.

Python A second problem: maximize 3x + 2y + 4z

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last lines use the pattern from solving LPs with SciPy to confirm the hand-made tableau.

Reading a final tableau: a checklist

  1. All objective-row entries >= 0? Then optimal.
  2. Basic variables: read their values from the right-hand column; non-basic variables are 0.
  3. Any non-basic variable with objective-row entry exactly 0? There may be alternative optima: pivot on it and the objective stays the same.
  4. Slack columns of the objective row: shadow prices of the constraints.
flowchart TD
  S["Start: BFS (origin)"] --> Q{"Any negative entry in objective row?"}
  Q -- "No" --> OPT["Optimal"]
  Q -- "Yes" --> E["Choose entering column"]
  E --> R{"Any positive entry in column?"}
  R -- "No" --> UNB["Unbounded"]
  R -- "Yes" --> L["Ratio test: leaving row"]
  L --> P["Pivot"]
  P --> Q

The whole simplex method in one picture.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the max-form tableau, which column enters the basis under Dantzig's rule?

    A negative objective-row entry means increasing that variable raises z; the most negative gives the steepest rate.
  2. 2. What does the ratio test compute, and why?

    The smallest ratio is how far the entering variable can rise before a basic variable reaches zero.
  3. 3. The entering column has no positive entries. The LP is

    Nothing stops the entering variable from increasing forever while improving z.
  4. 4. At the optimum, the objective-row entry under a slack column gives

    Slack reduced costs equal the dual values (shadow prices).

Summary

  • Simplex moves between adjacent vertices, improving the objective each time.
  • Tableau: constraint rows plus an objective row of -c; the right-hand column holds basic values.
  • Iteration: entering variable (negative entry), ratio test (leaving row), pivot (row operations).
  • Optimal when no negative objective-row entries remain; unbounded if the entering column has no positive entry.
  • Slack columns of the final objective row are shadow prices.

Next: Implementing Simplex in Python