Recipe

Run the simplex method to completion

Use when: you have a maximize-form LP already in canonical form (every constraint reduced to an equation with a slack variable) and an all-slack starting basic feasible solution

Goal: the optimal basic feasible solution and objective value, reached by walking from vertex to adjacent vertex

Taught in The simplex method: the ratio test and pivoting · a later section extends this recipe with more cases

1. 1

   Write one row per constraint (decision-variable coefficients, then slack coefficients, then the right-hand side), plus an objective row built from z-c_1x_1-\cdots-c_nx_n=0: coefficient -c_j under each decision variable, 0 under each slack, current z=0. The starting basis is every slack variable.

   Example

   Rossi Woodworks: \max\ 5x_1+4x_2 s.t. 6x_1+4x_2+s_1=24,\ x_1+2x_2+s_2=6.

   basis	x_1	x_2	s_1	s_2	RHS
   s_1	6	4	1	0	24
   s_2	1	2	0	1	6
   z-row	-5	-4	0	0	0

   • Not yet: a \ge or = constraint with no obvious all-slack start — covered in Two-phase simplex

   Why: the all-slack basis is automatically feasible whenever every right-hand side is nonnegative — it's literally the origin, and the origin always satisfies \mathbf x\ge\mathbf0.

2. 2

   Scan the z-row for negative entries. If none exist, STOP — the tableau is already optimal. Otherwise bring in the column with the most negative entry (Bland's rule breaks a tie by the lowest-indexed column — see Section 10).

   Example

   Both x_1 (-5) and x_2 (-4) are negative; -5 is more negative. x_1\text{ enters.}

   Why: a negative reduced cost means increasing that variable would raise z; the most negative one raises it fastest per unit (Section 6).

3. 3

   For every row with a POSITIVE entry in the entering column, divide that row's RHS by its entering-column entry. The leaving variable is the row with the SMALLEST such ratio. A row whose entering-column entry is \le0 is not eligible at all.

   Example

   Row s_1: 24/6=4. Row s_2: 6/1=6. The smaller ratio is 4. s_1\text{ leaves.}

   • no row has a positive entry in the entering column — the objective is UNBOUNDED on this feasible region; stop, there is no optimal solution.
   • two or more rows tie for the smallest ratio — apply Bland's rule, breaking the tie by the lowest-indexed basic variable (Section 10 shows why this exact tie-break matters).

   Why: the ratio is exactly how far the entering variable can grow before some currently-basic variable is forced to 0; the smallest one is the first constraint that binds.

4. 4

   Divide the ENTIRE leaving row by its entry in the entering column, so that entry becomes exactly 1. Then, for every OTHER row (including the z-row), subtract the right multiple of the new pivot row to zero out that row's entry in the entering column.

   Example

   Pivot element is 6 (row s_1, column x_1). Divide row s_1 by 6: [1,\ \tfrac23,\ \tfrac16,\ 0\mid 4]. Subtract 1\times this from row s_2: [0,\ \tfrac43,\ -\tfrac16,\ 1\mid 2]. Add 5\times this to the z-row: [0,\ -\tfrac23,\ \tfrac56,\ 0\mid 20].

   Why: this is ordinary Gauss-Jordan elimination — the unique row-operation sequence that keeps the system's solution set unchanged while making the entering column read off a clean 0/1 pattern for the new basis.

5. 5

   Go back to Step 2 with the new tableau. Stop exactly when EVERY z-row entry is \ge0; read the optimal solution and objective value directly off the final RHS column (basic variables take their RHS value, nonbasic variables are 0).

   Example

   The z-row still has -\tfrac23 under x_2 — not done. One more pivot (entering x_2, leaving s_2, pivot element \tfrac43) reaches x_1=3,\quad x_2=1.5,\quad z=21, with every z-row entry now \ge0 — optimal, matching Section 1's graphical answer exactly.

   Why: each pivot strictly improves (or, at a degenerate vertex, at least never worsens) the objective and moves to an adjacent vertex; a polyhedron has only finitely many vertices, so the loop is guaranteed to terminate (Section 10 covers the one subtlety — degenerate cycling — and Bland's rule's fix).