Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
A reference sheet for the terminology and formulas used in the Simplex Algorithm of linear programming problems

Simplex Algorithm Reference Sheet

The simplex algorithm is a method for maximizing or minimizing a linear equation given a set of linear constraints on the variables in the equation.

Definitions

Linear equality
f(x1, x2, .., xn) = b
Linear inequality
One of these:
  • f(x1, x2, .., xn) <= b
  • f(x1, x2, .., xn) >= b
Linear constraints
Either linear equalities or linear inequalities
Objective function
Function in x1, x2, .., xn we wish to maximize
Linear programming problem (linear program)
The problem of minimizing or maximizing an objective function given a finite set of linear constraints
Feasible solution
Any setting of variables in the objective function that satisfies the all constraints
Objective value
Value of the objective function given a feasible solution
Optimal solution
When maximizing the objective function, the maximum feasible solution; when minimizing the objective function, the minimum feasible solution
Simplex Algorithm
Takes as input a linear program and returns an optimal solution

Standard Form

Maximize objective function cx

Subject to linear constraints: Ax <= b and x >= 0

A b c x
type matrix vector vector vector
size m x n m x 1 1 x n n x 1

Slack Form

Maximize objective function z = cx

Subject to linear constraints b - Ax = s, x >= 0, s >= 0

A b c x s
type matrix vector vector vector vector
size m x n m x 1 1 x n n x 1 m x 1
terminology nonbasic variables basic variables

Other slack form variables

Name Size Description
N n Set of indices of the nonbasic variables. Variables on RHS indexed by entries in N
B m Set of indices of the basic variables. Equations indexed by entries in B
N union B n + m = {1, 2, .., n+m}
v scalar optional constant term in objective function

Slack Form Definitions

Basic solution
Value of b when setting all nonbasic variables to 0
Basic feasible solution
If the basic solution is also feasible, then it is a basic feasible solution
Pivot
Operation that uses one of the linear equations represented by a row in b - Ax = s to solve for a nonbasic variable, then substitutes this value into all other occurrences of the nonbasic variable. The effect of this operation is that one nonbasic variable swaps places with one basic variable, updating A, b, and c, but maintaining an equivalent set of feasible solutions.
Entering variable
The nonbasic variable that will be solved for during a pivot
Leaving variable
The basic variable from the row in b - Ax = s used during a pivot
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment