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