Posted in Operations and Supply Chain Terms, Total Reads: 1389
Definition: Simplex Method
The Simplex Method is a geometric method of solving linear programming problems. The graphical method can be used for problems with two decision variables. But, when we have more than two decision variables and more problem constraints we can use the Simplex method.
It was developed by George B. Dantzig in 1947. It can be understood as an operation on simplical cones. The simplical cones are the corners of a polytope which is defined by the constraints.
STEPS to solve the problem:
Convert each inequality constraint to an equality by adding slack variables
Create initial simplex tableau
Select the Pivot column
Select the Pivot row
Use elementary row operations to calculate new values for pivot row so that the pivot is 1 by dividing every number in the row by pivot number.
Use elementary row operations to make all numbers in the pivot column equal to 0 except for the pivot number. If all entries in the bottom row are zero or positive, this is the final tableau. If not, go to step 3.
If you obtain a final tableau, then the problem has a maximum solution given by the lower-right corner of the tableau.
Column of the tableau representing the variable to be entered in the solution mix
Row of the tableau representing the variable to be replaced in the solution mix
Element in both the pivot column and pivot row
Can be easily programmed and adapted in a software program
Easier to use than the least-squares method which requires a derivative function
Efficient than the earlier methods such as Fourier-Motzkin elimination.
Polynomial time average case complexity
Given k decision variables, it converges in O(k) operations with O(k) pivots.
It has limited applications
Not applicable when there are hundreds of decision variables
It has exponential worst case complexity
Given k decision variables, it converges in O(2n) operations and pivots in worst-case