How do I use the simplex method?

How it works

The problem: maximize (or minimize) z = c₁x₁ + c₂x₂ + … subject to constraints aᵢ₁x₁ + aᵢ₂x₂ + … (≤, ≥ or =) bᵢ, with every variable ≥ 0.

1. Standard form. A row with a negative right side is multiplied by −1 (≤ and ≥ swap). Each ≤ row gets a slack variable s (+1), each ≥ row a surplus variable s (−1); the slack and surplus variables are numbered s1, s2, … in row order. Each ≥ and = row also gets an artificial variable a1, a2, …
2. Tableau. One row per constraint, [coefficients | right side], and a bottom row. The starting basic variables are the slack variable of each ≤ row and the artificial variable of each other row.
3. Phase 1 (only with artificial variables): the bottom row maximizes −(a1 + a2 + …). It starts with 1 under each artificial column and 0 elsewhere; each artificial row is then subtracted from it, so it reads 0 under the basic variables. Pivot as in step 5 until no bottom entry is negative. If the bottom-right value is not 0, the problem is infeasible. Otherwise any artificial variable still basic (at 0) is pivoted out on the first nonzero entry of its row in a non-artificial column (or its row, now redundant, is dropped), and the artificial columns are removed.
4. Phase 2 bottom row: −cⱼ under each main variable to maximize z, or +cⱼ to minimize (maximizing −z); then each basic variable's row times its bottom entry is subtracted, so the bottom row reads 0 under the basic variables.
5. Pivot. The pivot column is the most negative bottom entry (ties: the first column). In that column, each row with a positive entry gives the ratio right side ÷ entry; the smallest ratio picks the pivot row (ties: the row whose basic variable comes first). If the column has no positive entry, the objective has no limit: the problem is unbounded. Divide the pivot row by the pivot, and subtract multiples of it to clear the rest of the column, bottom row included. After 50 pivots in a phase, the first negative bottom entry is used instead, so the method cannot cycle.
6. Optimal. When no bottom entry is negative, each basic variable equals its row's right side and every other variable is 0. The bottom-right value is the maximum of z (or −z when minimizing, so the minimum is minus that value).

Rules

• Type the objective as a sum of terms such as 40x, −2.5y, 1/2z or a constant. The words maximize or minimize (or max, min) at the start, or a name such as "P =", may be typed; a typed word sets the goal.
• One constraint per line (or separated by ;), each with one ≤ (typed <=), ≥ (typed >=) or = sign. A strict < or > is read as ≤ or ≥. Lines such as x ≥ 0 or x, y ≥ 0 are accepted and change nothing.
• A constant term in the objective (such as the 5 in 2x + 3y + 5) does not move the optimum; it is added to the optimal value.
• The steps call the objective z, or the first of P, w and Z that is not a variable name.
• Variable names start with a letter and may hold digits (x1, x₂). The columns are in order of first appearance, objective first. Up to 8 variables and 12 constraints.
• Numbers may be decimals or fractions a/b; a comma only separates thousands in groups of three (1,200), so 1,5 is refused. A number has at most 15 digits, and scientific notation such as 2e5 is refused (type 200000).
• An optimal value too large for a double-precision number gives no answer.

Output format. Every tableau entry and ratio is an exact fraction, shown as a whole number or as p/q in lowest terms. Tableaus are numbered within each phase. The optimal value shows to 10 significant figures; each variable shows as a decimal when its decimal ends, or as p/q with its decimal to 10 significant figures. A decimal that ends shows every digit, in the exact optimal value and the working too (1/1024 is 0.0009765625).

Worked examples by hand

Maximize 40x + 30y; x + y ≤ 12, 2x + y ≤ 16. Tableau 1 (x, y, s1, s2 | RHS): [1, 1, 1, 0 | 12], [2, 1, 0, 1 | 16], bottom [−40, −30, 0, 0 | 0]. Pivot column x (−40); ratios 12 and 8, so pivot on the 2 in row 2. Tableau 2: [0, 1/2, 1, −1/2 | 4], [1, 1/2, 0, 1/2 | 8], bottom [0, −10, 0, 20 | 320]. Pivot column y (−10); ratios 8 and 16, so pivot on the 1/2 in row 1. Tableau 3: [0, 1, 2, −1 | 8], [1, 0, −1, 1 | 4], bottom [0, 0, 20, 10 | 400]. No negative entry: x = 4, y = 8, z = 400.

Maximize 2x + 3y + 4z; 3x + 2y + z ≤ 10, 2x + 5y + 3z ≤ 15. The bottom row is [−2, −3, −4, 0, 0 | 0]; the pivot column is z (−4), with ratios 10 and 5, so pivot on the 3 in row 2. The new bottom row is [2/3, 11/3, 0, 0, 4/3 | 20], with no negative entry: x = 0, y = 0, z = 5, value 20.

Minimize 60x + 50y; 8x + 16y ≥ 200, 60x + 40y ≥ 960, 2x + 2y ≥ 40. Three artificial variables; phase 1 reaches 0, and phase 2 ends at x = 8, y = 12, minimum 1080.

Maximize x + y; x + 3y ≤ 4, 3x + y ≤ 4. The corners (0, 4/3), (1, 1) and (4/3, 0) give 4/3, 2 and 4/3, so the maximum is 2 at (1, 1).

Maximize x + 2y; 3x + 3y ≤ 4. y = 4/3 and x = 0, so z = 8/3 ≈ 2.666666667.