-
The idea is built on the Fundamental Theorem of Linear Programming. We proceed from one feasible solution of the constraint set in augmented form to another until the optimum is reached.
-
For this, we assume we have a feasible region in the form
, . We also assume that if
, and then . Otherwise, either has redundant solutions that can be dropped or the linear program has no solution. -
In augmented form, we refer to the matrix
As the tableau. If the columns of
can be rearranged so that it contains the identity matrix of order then the tableau is in canonical form. A variable is basic if it corresponds to a column of the identity matrix, and free otherwise. -
The tableau in canonical form may then look like the following, where basic variables are separated from free variables
-
If we set the values of the non-basic variables as
. A solution can easily be obtained using methods such as Gaussian Elimination. We refer to this as a basic solution. Applying row addition operations and considering
, the value of the objective function in a basic solution, gives us another tableau in canonical form This follows because the basic variables are linearly independent. The free variables are linear combinations of the basic variables.
-
-
A pivot operation is used to move from a basic feasible solution to another basic feasible solution. It involves selecting a non-basic column and applying row transformations so that it is a unit vector. It is then used as a replacement column to the Identity Matrix.
If we look at the basic variables as defining a basis, a pivot lets us define a new basis.
We refer to the variable used as a new basic variable as the entering variable and the variable it replaces as the leaving variable
-
The entering variable is selected to optimize the objective function
Typically, for maximization the choice of entering variable is one whose entry in the first row of the tableau is positive. If there are ties, we may use additional rules. If our goal is minimization, we change the choice to be the negative.
If no such choice exists, we in fact have an optimal solution.
-
More formally, for Tableau
(where we have ) choose column such that For Tableau 2 (where we have
), choose column such that . -
We can interpret
as the price of a unit of the column when constructed from the current basis. The difference between the synthetic and direct price of the column determines whether that column should enter the basis
-
-
The leaving variable is selected to maintain feasibility (i.e., the non-negativity constraint)
-
We only choose from the positive entries since this guarantees the entering variable will be nonnegative.
-
Select the pivot row so that the other basic variables remain positive. This occurs when the value of the entering variable is minimum. Let
be the pivot column and row respectively. Choose such that is the minimum over all
so that . If no such
exists, we can stop as the problem is unbounded.
-
-
-
The Simplex algorithm then proceeds as follows
- Construct a tableau corresponding to a basic feasible solution
- Check if the current basic feasible solution is optimal.
- Select the entering variable
- Select the leaving variable.
- Perform a pivot.