A reference sheet for the terminology and formulas used in the Simplex Algorithm of linear programming problems

SimplexAlgorithmReferenceSheet.md

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