Simplex Method

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:

  1. Locate the variable with the greatest (or lowest if its a minimization problem) objective function coefficient.
  2. Designate that column the work column.
  3. 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.
  4. Designate the element in the work column with the smallest ratio as the pivot element.
  5. If no element in the work column is positive, then the program has no solution.
  6. Use elementary row operations to convert the pivot element to 1 and then reduce all other elements in the work column to 0.
  7. Repeat steps 1 through 6 until there are no positive (negative) numbers in the last row, excluding the last column.
  8. The optimal solution is obtained by assigning to each variable in the first column that value in the corresponding row and last column.
  9. All other variables are assigned the value zero.


Show Work?