285. Simplex Method
285.0.0.1. Linear Algebra Review
Row View
Solution: Intersection of lines or (hyper)planes
Column View
Solution: Combination of LHS column vectors to form the RHS vector
A linear system is singular if there is no unique solution
- Row view: the (hyper)planes do not intersect at exactly one point
- Column view: the vectors do not span a complete -dimensional space
285.0.0.2. Gaussian Elimination
Given a system , or augmented matrix , use the following 3 rules:
- Row Swapping:
- Row Scaling:
- Row Replacement:
To solve the system:
-
Transform the augmented matrix into row echelon form (REF) using these operations:
- The first nonzero entry (pivot) in each row is to the right of the pivot in the row above
- All entries below a pivot are zero
- Rows of all zeros (if any) are at the bottom
- Back-substitute starting from the last nonzero row to find the solution
Example
Non-singular Case
System of equations
Augmented matrix
Swapping ()
Scaling ()
Row Echelon Form (REF)
Replacement ()
Reduced Row Echelon Form (RREF)
Result
Example
Singular Case
System of equations
Augmented matrix
Replacement ()
Infinitely many solutions E.g.
- etc.
Rows are linearly dependent
The coefficient matrix
has determinant 0, so it’s not invertible
285.0.0.3. Inverse
is unique
Finding : Gauss-Jordan Elimination
A square matrix is nonsingular iff it is invertible
Example
Replacement ()
Scale ()
Replacement ()
Result
285.0.0.4. Linear Dependence and Independence
A set of -dimensional vectors are linearly dependent if there exists a non-zero vector such that:
That is, at least one of the vectors can be written as a linear combination of the others.
Example
Dependent
Let:
Augmented:
Elimination ()
Independent
Let:
Augmented:
Elimination ()
Back-substitute
Only solution is
In Gaussian elimination, a row of all zeros
- Homogeneous System (RHS = 0)
- ✅ Represents a redundant equation (i.e., no new information) dependent set of vectors
- ✅ Does not affect consistency: the system is always consistent
- ✅ The system has fewer pivots than variables, hence infinitely many solutions
- Inconsistent System (Nonzero RHS)
- ❌ The second row leads to a contradiction
- ❌ The system is inconsistent (no solution)
285.0.0.5. Extreme Points
Given that , , and are points in the set :
- If you can find two different points and in such that lies somewhere strictly between them on the straight line connecting and , then is not an extreme point
- If no such pair of points exists—meaning you cannot place anywhere strictly between two other points in on a straight line—then is an extreme point
Formal Definition
For a set , a point is an extreme point if there does not exist a three-tuple such that , , , and
A point in set is extreme if it cannot be written as a strict convex combination of two different points .
Convex Combination
Let . A convex combination of these vectors is any point of the form:
where:
lies strictly between and on the line segment connecting them, not equal to either one
285.0.0.6. Slack and Suplus
1. Slack
Unused capacity
Example
Given a constraint:
The total must not exceed 5. To convert this into an equation, we add a slack variable :
- If , then
- If , then
2. Excess (surplus)
Excess above the required amount
Example
Given a constraint:
The total must be at least 5. To convert this into an equation, we subtract a excess variable :
- If , then
- If , then
| Objective Function | ||
| Max | ✅ | |
| Min Max |
|
|
| Constraint Forms | ||
| Slack |
|
|
| Excess + Artificial |
|
|
| Artificial |
|
|
| Negative | Multiply by −1 |
|
| Variable Bounds | ||
| Non-negativity |
|
|
| Lower Bound ≠ 0 | Substitution |
|
| Unrestricted Variables | Replace with difference |
|
| Variable Roles | ||
| Basic Variables | Usually non-zero | Part of the current solution (solved from the constraints) |
| Non-Basic Variables | Always zero | Temporarily set to 0 so basic variables can be solved |
| Simplex | ||
|
Selection:
|
For maximization problems:
For minimization problems:
|
|
|
Selection:
|
|
|
,
Example
Step 1: Convert to Standard Form
Objective
Step 2: Initial Tableau
| Basis | ||||||
| 1 | 1 | 1 | 0 | 0 | 4 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| −3 | −2 | 0 | 0 | 0 | 0 |
- Basic Variables: , ,
-
Non-basic variables: ,
- Objective:
Step 3: Choose entering variable
-
Look at the bottom row ():
- Coefficients of ,
- Most negative: Enter the basis
| Basis | ||||||
| 1 | 1 | 1 | 0 | 0 | 4 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| −3 | −2 | 0 | 0 | 0 | 0 |
Step 4: Determine leaving variable
Look at ratios of :
| Basis | ||||||||
| 1 | 1 | 1 | 0 | 0 | 4 | |||
| 1 | 0 | 0 | 1 | 0 | 2 | |||
| 0 | 1 | 0 | 0 | 1 | 3 | |||
| −3 | −2 | 0 | 0 | 0 | 0 |
-
Minimum Ratio
- leaves, enters
| Basis | ||||||
| 1 | 1 | 1 | 0 | 0 | 4 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| −3 | −2 | 0 | 3 | 0 | 0 |
Step 5: Pivot on row 2, column
Now eliminate from other rows:
| Basis | ||||||
| 1 | 1 | 1 | 0 | 0 | 4 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| −3 | −2 | 0 | 3 | 0 | 0 |
| Basis | ||||||
| 1 | 1 | 1 | 0 | 0 | 4 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| −3 | −2 | 0 | 3 | 0 | 0 |
Update
| Basis | ||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| −3 | −2 | 0 | 3 | 0 | 0 |
| Basis | ||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| −3 | −2 | 0 | 3 | 0 | 0 |
Update
| Basis | ||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| 0 | −2 | 0 | 3 | 0 | 6 |
- Basic Variables: , ,
-
Non-basic variables:
- Objective:
| Basis | ||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| 0 | −2 | 0 | 3 | 0 | 6 |
Step 3: Choose entering variable
-
Look at the bottom row ():
- Coefficients of
- Most negative: Enter the basis
| Basis | ||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| 0 | −2 | 0 | 3 | 0 | 6 |
Step 4: Determine leaving variable
Look at ratios of :
| Basis | ||||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |||
| 1 | 0 | 0 | 1 | 0 | 2 | |||
| 0 | 1 | 0 | 0 | 1 | 3 | |||
| 0 | −2 | 0 | 3 | 0 | 6 |
- leaves, enters
| Basis | ||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| 0 | −2 | 0 | 3 | 0 | 6 |
Step 5: Pivot on row 1, column
| Basis | ||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| 0 | −2 | 0 | 3 | 0 | 6 |
Now eliminate from other rows:
| Basis | ||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| 0 | −2 | 0 | 3 | 0 | 6 |
| Basis | ||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 1 | 0 | 0 | 1 | 3 | |
| 0 | −2 | 0 | 3 | 0 | 6 |
| Basis | ||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 0 | −1 | 1 | 1 | 1 | |
| 0 | −2 | 0 | 3 | 0 | 6 |
| Basis | ||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 0 | −1 | 1 | 1 | 1 | |
| 0 | −2 | 0 | 3 | 0 | 6 |
| Basis | ||||||
| 0 | 1 | 1 | −1 | 0 | 2 | |
| 1 | 0 | 0 | 1 | 0 | 2 | |
| 0 | 0 | −1 | 1 | 1 | 1 | |
| 0 | 0 | 2 | 1 | 0 | 10 |
- Basic Variables: , ,
-
Non-basic variables: ,
- Objective:
Example
Problem
Standard Form
Step 1: Handle Unrestricted Variable
Since is unrestricted:
Rewrite the objective:
Step 2: Slack Constraint ()
Rewrite with :
Add slack variable:
Step 3: Surplus + Artificial Constraint ()
Rewrite with :
Convert to equality by subtracting a surplus variable and adding an artificial variable:
Step 4: Negative RHS Constraint
Rewrite with :
Multiply both sides by to get a positive RHS and flip inequality:
Convert to equality by subtracting a surplus variable and adding an artificial variable:
Step 5: Artificial Equality Constraint ()
Rewrite with :
Add an artificial variable:
Final Standard Form
Phase I
Objective
Deriving Phase I Objective Row
- Objective function before substitution
- Express each artificial variable in terms of other variables from their constraints
- Substitute into :
- Rewrite as a constraint (bring all variables to the left):
So in tableau row :
| Basis | ||||||||||
| 1 | 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | |
| 2 | −1 | 1 | 0 | −1 | 0 | 1 | 0 | 0 | 2 | |
| 1 | −3 | 3 | 0 | 0 | −1 | 0 | 1 | 0 | 1 | |
| 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | |
| 4 | −5 | 5 | 0 | −1 | −1 | 0 | 0 | 0 | 4 |
Perform First Pivot
1. Pivot Column
Look at the row (objective row) for the most negative coefficient:
| Basis | ||||||||||
| 1 | 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | |
| 2 | −1 | 1 | 0 | −1 | 0 | 1 | 0 | 0 | 2 | |
| 1 | −3 | 3 | 0 | 0 | −1 | 0 | 1 | 0 | 1 | |
| 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | |
| 4 | −5 | 5 | 0 | −1 | −1 | 0 | 0 | 0 | 4 |
The most negative is pivot column is
2. Ratio
- Compute ratios () for rows with positive pivot entries:
| Basis | ||||||||||||
| 1 | 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | ||
| 2 | −1 | 1 | 0 | −1 | 0 | 1 | 0 | 0 | 2 | ❌ | ||
| 1 | −3 | 3 | 0 | 0 | −1 | 0 | 1 | 0 | 1 | ❌ | ||
| 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | ❌ | ||
| 4 | −5 | 5 | 0 | −1 | −1 | 0 | 0 | 0 | 4 |
- Minimum ratio is , so we pivot on row :
| Basis | ||||||||||||
| 1 | 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | ||
| 2 | −1 | 1 | 0 | −1 | 0 | 1 | 0 | 0 | 2 | ❌ | ||
| 1 | −3 | 3 | 0 | 0 | −1 | 0 | 1 | 0 | 1 | ❌ | ||
| 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | ❌ | ||
| 4 | −5 | 5 | 0 | −1 | −1 | 0 | 0 | 0 | 4 |
3. Pivot
| Basis | ||||||||||
| 1 | 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | |
| 2 | −1 | 1 | 0 | −1 | 0 | 1 | 0 | 0 | 2 | |
| 1 | −3 | 3 | 0 | 0 | −1 | 0 | 1 | 0 | 1 | |
| 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | |
| 4 | −5 | 5 | 0 | −1 | −1 | 0 | 0 | 0 | 4 |
4. Gauss-Jordan Elimination
Example
Step 3: Pivot
| Basis | ||||||||||
| 1 | 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 5 | |
| 3 | −1 | 1 | 0 | −1 | 0 | 1 | 0 | 0 | 4 | |
| 1 | −2 | 2 | 0 | 0 | −1 | 0 | 1 | 0 | 6 | |
| 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | |
| −5 | 4 | −4 | 0 | 1 | 1 | 0 | 0 | 0 | 12 |
Gauss-Jordan Elimination
| Basis | ||||||||||
| 1 | 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 5 | |
| 1 | −1/3 | 1/3 | 0 | −1/3 | 0 | 1/3 | 0 | 0 | 4/3 | |
| 1 | −2 | 2 | 0 | 0 | −1 | 0 | 1 | 0 | 6 | |
| 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | |
| −5 | 4 | −4 | 0 | 1 | 1 | 0 | 0 | 0 | 12 |
| Basis | ||||||||||
| 1 | 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 5 | |
| 1 | −1/3 | 1/3 | 0 | −1/3 | 0 | 1/3 | 0 | 0 | 4/3 | |
| 0 | −5/3 | 5/3 | 0 | 1/3 | −1 | −1/3 | 1 | 0 | 14/3 | |
| 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | |
| −5 | 4 | −4 | 0 | 1 | 1 | 0 | 0 | 0 | 12 |
| Basis | ||||||||||
| 1 | 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 5 | |
| 1 | −1/3 | 1/3 | 0 | −1/3 | 0 | 1/3 | 0 | 0 | 4/3 | |
| 0 | −5/3 | 5/3 | 0 | 1/3 | −1 | −1/3 | 1 | 0 | 14/3 | |
| 0 | −2/3 | 2/3 | 0 | 1/3 | 0 | −1/3 | 0 | 1 | 2/3 | |
| −5 | 4 | −4 | 0 | 1 | 1 | 0 | 0 | 0 | 12 |
| Basis | ||||||||||
| 1 | 1 | −1 | 1 | 0 | 0 | 0 | 0 | 0 | 5 | |
| 1 | −1/3 | 1/3 | 0 | −1/3 | 0 | 1/3 | 0 | 0 | 4/3 | |
| 0 | −5/3 | 5/3 | 0 | 1/3 | −1 | −1/3 | 1 | 0 | 14/3 | |
| 0 | −2/3 | 2/3 | 0 | 1/3 | 0 | 0-1/3 | 0 | 1 | 2/3 | |
| 0 | 7/3 | −7/3 | 0 | −2/3 | 1 | 5/3 | 0 | 0 | 56/3 |
| Basis | ||||||||||
| 0 | 4/3 | −4/3 | 1 | 1/3 | 0 | −1/3 | 0 | 0 | 11/3 | |
| 1 | −1/3 | 1/3 | 0 | −1/3 | 0 | 1/3 | 0 | 0 | 4/3 | |
| 0 | −5/3 | 5/3 | 0 | 1/3 | −1 | −1/3 | 1 | 0 | 14/3 | |
| 0 | −2/3 | 2/3 | 0 | 1/3 | 0 | −1/3 | 0 | 1 | 2/3 | |
| 0 | 7/3 | −7/3 | 0 | −2/3 | 1 | 5/3 | 0 | 0 | 56/3 |
Step 3: Perform the Second Pivot
- Look at the row (objective row) for the most negative coefficient:
| Basis | ||||||||||
| 0 | 4/3 | −4/3 | 1 | 1/3 | 0 | −1/3 | 0 | 0 | 11/3 | |
| 1 | −1/3 | 1/3 | 0 | −1/3 | 0 | 1/3 | 0 | 0 | 4/3 | |
| 0 | −5/3 | 5/3 | 0 | 1/3 | −1 | −1/3 | 1 | 0 | 14/3 | |
| 0 | −2/3 | 2/3 | 0 | 1/3 | 0 | 0-1/3 | 0 | 1 | 2/3 | |
| 0 | 7/3 | −7/3 | 0 | −2/3 | 1 | 5/3 | 0 | 0 | 56/3 |
-
The most negative is for
- Pivot column is
- Ratio
- Compute ratios () for rows with positive pivot entries:
| Basis | ||||||||||||
| 0 | 4/3 | −4/3 | 1 | 1/3 | 0 | −1/3 | 0 | 0 | 11/3 | ❌ | ||
| 1 | −1/3 | 1/3 | 0 | −1/3 | 0 | 1/3 | 0 | 0 | 4/3 | |||
| 0 | −5/3 | 5/3 | 0 | 1/3 | −1 | −1/3 | 1 | 0 | 14/3 | |||
| 0 | −2/3 | 2/3 | 0 | 1/3 | 0 | 0-1/3 | 0 | 1 | 2/3 | |||
| 0 | 7/3 | −7/3 | 0 | −2/3 | 1 | 5/3 | 0 | 0 | 56/3 |
- Minimum ratio is , so we pivot on row :
| Basis | ||||||||||||
| 0 | 4/3 | −4/3 | 1 | 1/3 | 0 | −1/3 | 0 | 0 | 11/3 | ❌ | ||
| 1 | −1/3 | 1/3 | 0 | −1/3 | 0 | 1/3 | 0 | 0 | 4/3 | |||
| 0 | −5/3 | 5/3 | 0 | 1/3 | −1 | −1/3 | 1 | 0 | 14/3 | |||
| 0 | −2/3 | 2/3 | 0 | 1/3 | 0 | 0-1/3 | 0 | 1 | 2/3 | |||
| 0 | 7/3 | −7/3 | 0 | −2/3 | 1 | 5/3 | 0 | 0 | 56/3 |
Step 4: Pivot
| Basis | ||||||||||
| 0 | 4/3 | −4/3 | 1 | 1/3 | 0 | −1/3 | 0 | 0 | 11/3 | |
| 1 | −1/3 | 1/3 | 0 | −1/3 | 0 | 1/3 | 0 | 0 | 4/3 | |
| 0 | −5/3 | 5/3 | 0 | 1/3 | −1 | −1/3 | 1 | 0 | 14/3 | |
| 0 | −2/3 | 2/3 | 0 | 1/3 | 0 | −1/3 | 0 | 1 | 2/3 | |
| 0 | 7/3 | −7/3 | 0 | −2/3 | 1 | 5/3 | 0 | 0 | 56/3 |
Gauss-Jordan Elimination
| Basis | ||||||||||
| 0 | 4/3 | −4/3 | 1 | 1/3 | 0 | −1/3 | 0 | 0 | 11/3 | |
| 1 | −1/3 | 1/3 | 0 | −1/3 | 0 | 1/3 | 0 | 0 | 4/3 | |
| 0 | −5/3 | 5/3 | 0 | 1/3 | −1 | −1/3 | 1 | 0 | 14/3 | |
| 0 | −1 | 1 | 0 | 1/2 | 0 | −1/2 | 0 | 3/2 | 1 | |
| 0 | 7/3 | −7/3 | 0 | −2/3 | 1 | 5/3 | 0 | 0 | 56/3 |
| Basis | ||||||||||
| 0 | 0 | 0 | 1 | 1 | 0 | −1 | 0 | 2 | 5 | |
| 1 | −1/3 | 1/3 | 0 | −1/3 | 0 | 1/3 | 0 | 0 | 4/3 | |
| 0 | −5/3 | 5/3 | 0 | 1/3 | −1 | −1/3 | 1 | 0 | 14/3 | |
| 0 | −1 | 1 | 0 | 1/2 | 0 | −1/2 | 0 | 3/2 | 1 | |
| 0 | 7/3 | −7/3 | 0 | −2/3 | 1 | 5/3 | 0 | 0 | 56/3 |
| Basis | ||||||||||
| 0 | 0 | 0 | 0 | −1/2 | 0 | 1/2 | 0 | −1/2 | 1 | |
| 1 | 0 | 0 | 0 | −1/2 | 0 | 1/2 | 0 | −1/2 | 1 | |
| 0 | −5/3 | 5/3 | 0 | 1/3 | −1 | −1/3 | 1 | 0 | 14/3 | |
| 0 | −1 | 1 | 0 | 1/2 | 0 | −1/2 | 0 | 3/2 | 1 | |
| 0 | 7/3 | −7/3 | 0 | −2/3 | 1 | 5/3 | 0 | 0 | 56/3 |
| Basis | ||||||||||
| 0 | 0 | 0 | 0 | −1/2 | 0 | 1/2 | 0 | −1/2 | 1 | |
| 1 | 0 | 0 | 0 | −1/2 | 0 | 1/2 | 0 | −1/2 | 1 | |
| 0 | 0 | 0 | 0 | −1/2 | −1 | 1/2 | 1 | −5/2 | 3 | |
| 0 | −1 | 1 | 0 | 1/2 | 0 | −1/2 | 0 | 3/2 | 1 | |
| 0 | 7/3 | −7/3 | 0 | −2/3 | 1 | 5/3 | 0 | 0 | 56/3 |
| Basis | ||||||||||
| 0 | 0 | 0 | 0 | −1/2 | 0 | 1/2 | 0 | −1/2 | 1 | |
| 1 | 0 | 0 | 0 | −1/2 | 0 | 1/2 | 0 | −1/2 | 1 | |
| 0 | 0 | 0 | 0 | −1/2 | −1 | 1/2 | 1 | −5/2 | 3 | |
| 0 | −1 | 1 | 0 | 1/2 | 0 | −1/2 | 0 | 3/2 | 1 | |
| 0 | 0 | 0 | 0 | 1/2 | 1 | 1/2 | 0 | 7/2 | 21 |
Step 5: Perform the Third Pivot
- Look at the row (objective row) for the most negative coefficient:
| Basis | ||||||||||
| 0 | 0 | 0 | 0 | −1/2 | 0 | 1/2 | 0 | −1/2 | 1 | |
| 1 | 0 | 0 | 0 | −1/2 | 0 | 1/2 | 0 | −1/2 | 1 | |
| 0 | 0 | 0 | 0 | −1/2 | −1 | 1/2 | 1 | −5/2 | 3 | |
| 0 | −1 | 1 | 0 | 1/2 | 0 | −1/2 | 0 | 3/2 | 1 | |
| 0 | 0 | 0 | 0 | −1/6 | 1 | 1/2 | 0 | 7/2 | 21 |
-
The most negative is for
- Pivot column is
- Ratio
- Compute ratios () for rows with positive pivot entries:
| Basis | ||||||||||||
| 0 | 0 | 0 | 0 | −1/2 | 0 | 1/2 | 0 | −1/2 | 1 | ❌ | ||
| 1 | 0 | 0 | 0 | −1/2 | 0 | 1/2 | 0 | −1/2 | 1 | ❌ | ||
| 0 | 0 | 0 | 0 | −1/2 | −1 | 1/2 | 1 | −5/2 | 3 | ❌ | ||
| 0 | −1 | 1 | 0 | 1/2 | 0 | −1/2 | 0 | 3/2 | 1 | 2 | ||
| 0 | 0 | 0 | 0 | −1/6 | 1 | 1/2 | 0 | 7/2 | 21 |
Two-Phase
| Basis | ||||||
| ??? | 1 | 1 | 0 | 0 | 2 | |
| ??? | 1 | 0 | 0 | 0 | 1 | |
| 1 | 1 | 0 | 0 | 1 | 5 | |
| −2 | −1 | 0 | 0 | 0 | 0 |
Degeneracy
Degeneracy occurs when a basic variable takes the value zero in a basic feasible solution. This leads to ties in the minimum ratio test, which determines the leaving variable during a pivot.
Example
Problem
Standard Form
Initialize Tableau
| Basis | ||||||
| 1 | 1 | 1 | 0 | 0 | 3 | |
| 0 | 1 | 0 | 1 | 0 | 2 | |
| 1/2 | 1 | 0 | 0 | 1 | 2.5 | |
| −1 | −1 | 0 | 0 | 0 | 0 |
Minimum Test
| Basis | ||||||
| 1 | 1 | 1 | 0 | 0 | 3 | |
| 0 | 1 | 0 | 1 | 0 | 2 | |
| 1/2 | 1 | 0 | 0 | 1 | 2.5 | |
| −1 | −1 | 0 | 0 | 0 | 0 |
Ratio Test
| Basis | ||||||
| 1 | 1 | 1 | 0 | 0 | 3 | |
| 0 | 1 | 0 | 1 | 0 | 2 | |
| 1/2 | 1 | 0 | 0 | 1 | 2.5 | |
| −1 | −1 | 0 | 0 | 0 | 0 |
Pivot
| Basis | ||||||
| 1 | 1 | 1 | 0 | 0 | 3 | |
| 0 | 1 | 0 | 1 | 0 | 2 | |
| 1/2 | 1 | 0 | 0 | 1 | 2.5 | |
| −1 | −1 | 0 | 0 | 0 | 0 |
Gaussian Elimination
| Basis | ||||||
| 1 | 0 | 1 | −1 | 0 | 1 | |
| 0 | 1 | 0 | 1 | 0 | 2 | |
| 1/2 | 0 | 0 | −1 | 1 | 0.5 | |
| −1 | 0 | 0 | 2 | 0 | 4 |
Minimum Test
| Basis | ||||||
| 1 | 0 | 1 | −1 | 0 | 1 | |
| 0 | 1 | 0 | 1 | 0 | 2 | |
| 1/2 | 0 | 0 | −1 | 1 | 0.5 | |
| −1 | 0 | 0 | 2 | 0 | 4 |
Ratio Test
| Basis | ||||||
| 1 | 0 | 1 | −1 | 0 | 1 | |
| 0 | 1 | 0 | 1 | 0 | 2 | |
| 1/2 | 0 | 0 | −1 | 1 | 0.5 | |
| −1 | 0 | 0 | 2 | 0 | 4 |
Pivot
| Basis | ||||||
| 1 | 0 | 1 | −1 | 0 | 1 | |
| 0 | 1 | 0 | 1 | 0 | 2 | |
| 1/2 | 0 | 0 | −1 | 1 | 0.5 | |
| −1 | 0 | 0 | 2 | 0 | 4 |
Gaussian Elimination
| Basis | ||||||
| 1 | 0 | 1 | −1 | 0 | 1 | |
| 0 | 1 | 0 | 0 | 0 | 2 | |
| 0 | 0 | −1/2 | −1/2 | 1 | 0 | |
| 0 | 0 | 1 | 1 | 0 | 5 |
If after elimination a basic variable has a value of 0, it indicates degeneracy.
Degeneracy comes from redundant constraints
Bland’s Rule: Choose the variable with the lowest index in the basis
- over
- over
Unbounded Solution
When identifying the entering variable, look at its column in the tableau. If all entries in that column (above the objective row) are , the problem is unbounded
Can’t perform ratio test no constraint limits the entering variable objective function increases without bound
Example
Problem
Standard Form
Initialize Tableau
| Basis | ||||
| 1 | −1 | 1 | 1 | |
| −1 | −1 | 0 | 0 |
Minimum and Ratio Test
| Basis | ||||
| 1 | −1 | 1 | 1 | |
| −1 | −1 | 0 | 0 |
Pivot
| Basis | ||||
| 1 | −1 | 1 | 1 | |
| −1 | −1 | 0 | 0 |
Gaussian Elimination
| Basis | ||||
| 1 | −1 | 1 | 1 | |
| 0 | −2 | 1 | 1 |
Minimum and Ratio Test
| Basis | ||||
| 1 | −1 | 1 | 1 | |
| 0 | −2 | 1 | 1 |
Check for Optimality
Objective row has −2 for → not optimal
Entering variable: (most negative coefficient)
Unboundedness Detection
Looking at the column:
Entry in constraint row: −1 (which is ≤ 0)
All entries in column are ≤ 0
Conclusion: Cannot perform ratio test Problem is unbounded
Alternative Solutions
Example
Problem
Standard Form
Initialize Tableau
| Basis | |||||
| 1 | 1 | 1 | 0 | 3 | |
| 1/2 | 1 | 0 | 1 | 2.5 | |
| −2 | −4 | 0 | 0 | 0 |
Minimum Test
| Basis | |||||
| 1 | 1 | 1 | 0 | 3 | |
| 1/2 | 1 | 0 | 1 | 2.5 | |
| −2 | −4 | 0 | 0 | 0 |
Ratio Test
| Basis | |||||
| 1 | 1 | 1 | 0 | 3 | |
| 1/2 | 1 | 0 | 1 | 2.5 | |
| −2 | −4 | 0 | 0 | 0 |
Pivot
| Basis | |||||
| 1 | 1 | 1 | 0 | 3 | |
| 1/2 | 1 | 0 | 1 | 2.5 | |
| −2 | −4 | 0 | 0 | 0 |
Gaussian Elimination
| Basis | |||||
| 1/2 | 0 | 1 | −1 | 0.5 | |
| 1/2 | 1 | 0 | 1 | 2.5 | |
| 0 | 0 | 0 | 4 | 10 |
In a maximization or minimization linear programming problem, if there is a 0 in the row (objective function row) of the final (optimal) simplex tableau in a non-basic column (i.e. a variable not currently in the solution), then there are multiple optimal solutions.
285.0.0.7. Standard Form
-
Equalities: Convert inequalities (using slack, surplus, or artificial variables)
-
Non-negative variables: If a variable is unrestricted or can be negative, replace it with the difference of two non-negative variables
Example
Nonpositive
Free (Unrestricted)
285.0.0.8. Simplex Method
Example
| Basis | 7 | 6 | 0 | 0 | ||
| 0 | 2 | 4 | 1 | 0 | 16 | |
| 0 | 3 | 2 | 0 | 1 | 12 | |
|
|
0 | 0 | 0 | 0 | ||
| 7 | 6 | 0 | 0 |
| Basis | 7 | 6 | 0 | 0 | Ratio | ||
| 0 | 2 | 4 | 1 | 0 | 16 | 16/2 = 8 | |
| 0 | 3 | 2 | 0 | 1 | 12 | 12/3 = 4 | |
| 0 | 0 | 0 | 0 | 0 | |||
| 7 | 6 | 0 | 0 |
- Formulation
Objective Function
Constraints
Or,
- for maximization
- for minimization
- Convert to Canonical Form
In slack variable form
Or matrix notation,
|
|
|
|
|
|
|
|
- Set up Simplex Tableau
| RHS | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Constraint 1 | 1 | 0 | 0 | ||||||
| Constraint 2 | 0 | 1 | 0 | ||||||
| Constraint | 0 | 0 | 1 | ||||||
| Objective Function | 0 | 0 | 0 | 0 |
- for maximization
- for minimization
- Perform Pivot Operation
-
Identify the Pivot Column: Choose the column with the most:
-
Maximization: Negative coefficient
-
Minimization: Positive coefficient (or multiply the objective by −1 and treat it as a maximization)
-
in the objective function row (this indicates which variable will enter the basis).
-
Identify the Pivot Row: Calculate the ratio of RHS to the pivot column’s coefficients (only where coefficients are positive). The row with the smallest ratio determines the variable to leave the basis.
-
Pivot: Perform row operations to change the pivot element to 1 and other elements in the pivot column to 0. This involves dividing the pivot row by the pivot element and then adjusting the other rows to zero out the pivot column.
- Iterate
Repeat the pivot operations until there are no more negative coefficients in the objective function row, indicating that the current solution is optimal.
- Read the Solution
The final tableau will give the values of the variables at the optimal solution. The basic variables are the variables corresponding to the columns with the identity matrix in the final tableau, while non-basic variables are set to zero.
Example
s.t.
1. Convert to Canonical Form
Introduce slack variables and to convert inequalities into equalities:
Initialize Simplex Tableau
| RHS | |||||
|---|---|---|---|---|---|
| Constraint 1 | 1 | 1 | 1 | 0 | 4 |
| Constraint 2 | 2 | 1 | 0 | 1 | 5 |
| Objective Function | −3 | −2 | 0 | 0 | 0 |
2. Identify the Pivot Column
In the objective function row, the coefficients are . The most negative coefficient is , which is in the column. Therefore, will enter the basis.
3. Identify the Pivot Row
Calculate the ratio of RHS to the pivot column’s coefficients (where the coefficients are positive):
-
For Row 1: (pivot column coefficient is 1)
-
For Row 2: (pivot column coefficient is 2)
The smallest ratio is 2.5, so Row 2 will be the pivot row. This means that will leave the basis.
4. Pivot
Perform row operations to make the pivot element 1 and zero out other elements in the pivot column.
Pivot Element: The element at the intersection of Row 2 and column is 2.
Steps:
- Make Pivot Element 1: Divide all elements in Row 2 by the pivot element (2):
- Zero Out Pivot Column in Other Rows:
- For Row 1: Subtract 1 times New Row 2 from Row 1:
- For Objective Function: Add 3 times New Row 2 to the Objective Function row
Updated Simplex Tableau
| RHS | |||||
|---|---|---|---|---|---|
| Constraint 1 | 0 | 0.5 | 1 | −0.5 | 1.5 |
| Constraint 2 | 1 | 0.5 | 0 | 0.5 | 2.5 |
| Objective Function | 0 | −0.5 | 0 | 1.5 | 7.5 |
285.0.1. Matrix Notation
Where:
- : Basic variables (in the basis)
- : Non-basic variables (not in the basis)
- : Coefficients of basic variables in the objective function
- : Coefficients of non-basic variables in the objective function
- : Columns of corresponding to basic variables
- : Columns of corresponding to non-basic variables
- : Right-hand side constants
Example
Standard form:
Given and :
Objective Function
Constraints
Problem
Rearange the the terms in the constrains:
Replace in the objective function:
Rearrange the terms in the objectcive function:
The standard form LP becomes:
Rearrange the terms of the constrains:
Ignore the sign constraints and let be the objectctive value:
The Simplex Tableau is:
| basic | non-basic | RHS |
Example
Step 1. Standard form
Matrix notation:
Step 2. Initial Basis
Cost split:
Compute inverse of :
So the basic feasible solution (BFS) is:
Step 3. Reduced costs and entering variable
Since , the entering variable is
Step 4. Direction, ratio test and leaving variable
For , we have:
Current basic solution:
The minimum ratios test:
Smallest ratio is leaves the basis
Step 5. Pivot to the new basis
Cost split:
Compute inverse of :
So the new basic feasible solution (BFS) is:
Step 6. Check optimality (reduced costs)
No negative reduced costs optimal
Example
Problem:
Standard form:
|
Let and |
|
||||||||||||||||||||
|
Let and |
|
||||||||||||||||||||
Example
Step 1. Canonical form
Step 2. Standard form
Matrix notation:
Step 3. Initial Basis
Compute :
Compute basic feasible solution:
Current basic feasible solution:
Step 4. Reduced costs and entering variable
Since , the entering variable is
Step 5. Direction, ratio test and leaving variable
For , we have:
Current basic solution:
The minimum ratios test:
Smallest ratio is leaves the basis (only consider ratios where the corresponding )
Step 6. Pivot to the new basis
Compute :
Compute basic feasible solution:
Current basic feasible solution:
Step 7. Reduced costs and entering variable
Since , the entering variable is
Step 8. Direction, ratio test and leaving variable
For , we have:
Current basic solution:
The minimum ratios test:
Smallest ratio is leaves the basis (only consider ratios where the corresponding )
Step 9. Pivot to the new basis
Compute :
Compute basic feasible solution:
Current basic feasible solution:
Nv = np.array(['x1', 'x2'])
Bv = np.array(['s1', 's2', 's3'])
A = np.array([
[-1, 1, 1, 0, 0],
[-1, 2, 0, 1, 0],
[3, 1, 0, 0, 1],
])
c = np.array([1, 3, 0, 0, 0])
b = np.array([3, 8, 18])
cN = c[:2]
cB = c[2:]
N = A[:,:2]
B = A[:,2:]
print("Nv"), print(Nv)
print()
print("N"), print(N)
print()
print("cN"), print(cN)
print()
print("Bv"), print(Bv)
print()
print("B"), print(B)
print()
print("cB"), print(cB)
print()
print("b"), print(b)
print()
Binv = np.linalg.inv(B)
bfs = Binv @ b
z = cB @ bfs
print("B^(-1)"), print(Binv)
print()
print("BFS"), print(bfs)
print()
print("z"), print(z)
print()reduced_cost = cB @ Binv @ N - cN
print("bar(c)_N^T"), print(reduced_cost)
print()
entering_var_index = 0
print("Entering var"), print(Nv[entering_var_index])
print()
d = Binv @ N[:,entering_var_index]
ratios = bfs / d
print(f"Ratios"), print(ratios)
print()
exiting_var_index = 2
print(f"Exiting variable"), print(Bv[exiting_var_index])
print()
B[:, exiting_var_index], N[:, entering_var_index] = N[:, entering_var_index].copy(), B[:, exiting_var_index].copy()
cB[exiting_var_index], cN[entering_var_index] = cN[entering_var_index].copy(), cB[exiting_var_index].copy()
Bv[exiting_var_index], Nv[entering_var_index] = Nv[entering_var_index].copy(), Bv[exiting_var_index].copy()
print("Nv"), print(Nv)
print()
print("N"), print(N)
print()
print("cN"), print(cN)
print()
print("Bv"), print(Bv)
print()
print("B"), print(B)
print()
print("cB"), print(cB)
print()
Binv = np.linalg.inv(B)
bfs = Binv @ b
z = cB @ bfs
print("B^(-1)"), print(Binv)
print()
print("BFS"), print(bfs)
print()
print("z"), print(z)
print()
reduced_cost = cB @ Binv @ N - cN
print("bar(c)_N^T"), print(reduced_cost)
print()
entering_var_index = 1
print("Entering var"), print(Nv[entering_var_index])
print()
d = Binv @ N[:,entering_var_index]
ratios = bfs / d
print(f"Ratios"), print(ratios)
print()
exiting_var_index = 1
print(f"Exiting variable"), print(Bv[exiting_var_index])
print()
B[:, exiting_var_index], N[:, entering_var_index] = N[:, entering_var_index].copy(), B[:, exiting_var_index].copy()
cB[exiting_var_index], cN[entering_var_index] = cN[entering_var_index].copy(), cB[exiting_var_index].copy()
Bv[exiting_var_index], Nv[entering_var_index] = Nv[entering_var_index].copy(), Bv[exiting_var_index].copy()
print("Nv"), print(Nv)
print()
print("N"), print(N)
print()
print("cN"), print(cN)
print()
print("Bv"), print(Bv)
print()
print("B"), print(B)
print()
print("cB"), print(cB)
print()
Binv = np.linalg.inv(B)
bfs = Binv @ b
z = cB @ bfs
print("B^(-1)"), print(Binv)
print()
print("BFS"), print(bfs)
print()
print("z"), print(z)
print()