The Simplex Method
Ideas from Solving LPs Graphically
1. If there is an optimal solution, it is a
CPF solution (CPFS).
2. There are a finite number of CPFS.
3. CPFS are the intersection of n (# variables)
defining equations.
4. Adjacent CPFS have n-1 defining equations in common.
5. If a CPFS is optimal, it is better than all (adjacent) CPFS.
6. If a CPFS is better than all (adjacent)
CPFS, it is optimal.
Basis of the Simplex Algorithm
1. Start at any CPFS and move to a better one.
2. Stop if you reach a CPFS better than all adjacent CPFS.
The Simplex Algorithm
1. Convert to standard form.
2. Find (if possible) a bfs.
3. Determine whether the current bfs is optimal.
4. If not, determine which nonbasic variable should become a basic (entering)
variable and which basic variable should become a nonbasic (leaving) variable.
5. Use EROs to find the new bfs with better objective function value.
6. Go back to step 3.