Linear Programming & Simplex Reference Cheat Sheet

Key Facts

• A standard linear programming maximization problem can be written as maximize $P = c_1x_1 + c_2x_2 + \cdots + c_nx_n$ subject to linear constraints.
• A constraint such as $2x + 3y \le 12$ represents a half-plane, and the feasible region is the intersection of all constraint half-planes.
• For a two-variable linear programming problem, an optimum occurs at a vertex of the feasible region when the feasible region is bounded.
• To change $a_1x_1 + a_2x_2 \le b$ into an equation, add a slack variable: $a_1x_1 + a_2x_2 + s = b$, where $s \ge 0$.
• In a simplex tableau, the entering variable is usually chosen from the most negative coefficient in the objective row for a maximization problem.
• The leaving variable is found by the minimum positive ratio test $\frac{b_i}{a_{ij}}$ using positive entries in the entering column.
• A pivot operation makes the pivot entry equal to $1$ and all other entries in the pivot column equal to $0$.
• The simplex method stops for a maximization problem when all coefficients in the objective row are nonnegative.

Vocabulary

Objective function

The linear expression, such as $P = 4x + 7y$, that is maximized or minimized.

Constraint

A linear equation or inequality, such as $x + 2y \le 10$, that limits the possible values of the variables.

Feasible region

The set of all points that satisfy every constraint, including nonnegativity conditions such as $x \ge 0$ and $y \ge 0$.

Slack variable

A nonnegative variable added to a $\le$ constraint to convert it into an equation, such as $x + y + s = 8$.

Pivot

The selected tableau entry used to update rows so one variable enters the solution and another variable leaves.

Optimal solution

A feasible solution that gives the greatest or least possible value of the objective function.