The Simplex Algorithm
This program generates a random linear programming problem, converts it to standard form, and solves it using the Simplex method.
A linear program is in standard form if:
- Each constraint is an equality constraint
- Every variable is non-negative
- We will add artificial variables to equality constraints to help find an initial feasible solution
The Simplex Method operates as follows:
- Locate the variable with the greatest (or lowest if its a minimization problem) objective function coefficient.
- Designate that column the work column.
- Form ratio's by dividing each positive number in the work column (excluding the last row) into the element in the same row and last column.
- Designate the element in the work column with the smallest ratio as the pivot element.
- If no element in the work column is positive, then the program has no solution.
- Use elementary row operations to convert the pivot element to 1 and then reduce all other elements in the work column to 0.
- Repeat steps 1 through 6 until there are no positive (negative) numbers in the last row, excluding the last column.
- The optimal solution is obtained by assigning to each variable in the first column that value in the corresponding row and last column.
- All other variables are assigned the value zero.