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?

Recent Updates

  • 08-10-2017 Floyd-Warshall Shortest Paths
  • 08-01-2017 Degree Centrality of a Graph
  • 06-03-2017 Tarjan's Strongly Connected Components Algorithm
  • 03-20-2017 Longest Common Subsequence
  • 10-27-2016 Independent Set Puzzles
  • 06-28-2016 Lets Learn About XOR Encryption
  • 06-15-2016 Discrete-time Markov Chains
  • 03-01-2016 Topological Sort
  • 01-21-2016 The RSA Algorithm
  • 11-20-2015 How To Take Notes in Math Class
  • 10-28-2015 The Depth-First-Search Algorithm
  • 10-28-2015 The Breadth-First-Search Algorithm
  • 09-23-2015 ID3 Algorithm Decision Trees
  • 07-08-2015 Clique Problem Puzzles
  • 06-25-2015 Unidirectional TSP Puzzles
  • 04-04-2015 Learn About Descriptive Statistics
  • 02-19-2015 Slope Formula
  • 01-15-2015 Interactive Midpoint Formula
  • 12-18-2014 Triangle Sum Puzzle
  • 12-02-2014 The Bridge Crossing Problem