How do I solve linear programming?

How it works

A linear program asks for the largest (maximize) or smallest (minimize) value of z = c₁x₁ + c₂x₂ + … over every point that meets the constraints aᵢ₁x₁ + aᵢ₂x₂ + … (≤, ≥ or =) bᵢ, with every variable ≥ 0.

Corner points (two variables). The page takes every pair of boundary lines (each constraint as an equation, plus x = 0 and y = 0), solves the pair, and keeps the point if it meets every constraint. Those are the corners of the feasible region, listed from left to right (by x, then by y). It shows z at each one; the optimum is the largest (or smallest) of them.

The answer itself comes from the two-phase simplex method (the same steps the simplex method page shows), which also covers three or more variables and tells an unbounded problem from a bounded one:

1. Make every right side 0 or more (multiplying a row by −1 flips ≤ and ≥). Add a slack variable to each ≤ row, a surplus variable (subtracted) to each ≥ row, and an artificial variable to each ≥ and = row.
2. Phase 1 (only with artificial variables): maximize −(sum of the artificial variables). If the best is not 0, no point meets every constraint: the problem is infeasible. Otherwise drop the artificial variables.
3. Phase 2: maximize z (or −z to minimize). Pivot on the most negative entry of the bottom row and, in its column, the row with the smallest ratio of right side to a positive entry. When no bottom entry is negative, the tableau is optimal. A pivot column with no positive entry means the objective has no limit: the problem is unbounded.

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₂). 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.
• Ties in the pivot column go to the first column; ties in the ratio test go to the row whose basic variable comes first. After 50 pivots the first negative column is used, so the method cannot cycle.

Output format. Every value is read and computed exactly as a fraction. The optimal value shows to 10 significant figures; each variable shows as a decimal when its decimal ends, or as a fraction p/q with its decimal to 10 significant figures (4/3 ≈ 1.333333333). 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. Corners (0, 0): 0; (0, 12): 360; (4, 8): 400; (8, 0): 320. Maximum 400 at x = 4, y = 8.

Maximize 20x + 30y; x + y ≤ 7, x + 2y ≤ 12, 2x + y ≤ 12. Corners (0, 0): 0; (0, 6): 180; (2, 5): 190; (5, 2): 160; (6, 0): 120. Maximum 190 at (2, 5).

Maximize 10x + 15y; x + y ≥ 1, x + 2y ≤ 6, 2x + y ≤ 6. Corners (0, 1): 15; (0, 3): 45; (1, 0): 10; (2, 2): 50; (3, 0): 30. Maximum 50 at (2, 2).

Minimize 15x + 25y; x ≥ 1, y ≥ 1, 20x + 30y ≥ 110. The region is unbounded upward, but z only grows there. Corners (1, 3): 90; (4, 1): 85. Minimum 85 at (4, 1).

Minimize 60x + 50y; 8x + 16y ≥ 200, 60x + 40y ≥ 960, 2x + 2y ≥ 40. Corners (0, 24): 1200; (8, 12): 1080; (15, 5): 1150; (25, 0): 1500. Minimum 1080 at (8, 12).