Using the Simplex Method to Save Time

The simplex method is one of the most popular linear programming problem solving methods in use. It has a number of advantages that make it the ideal method to solve many forms of problems. There have also been adaptations made to the algorithm over the years to make it more efficient and adaptable.

What is the Simplex Method?

The simplex algorithm was invented in 1947 by George Dantzig. It was intended to create an efficient way to solve linear programming problems and remains the most common way to solve standard maximization problems. The formula allows an individual to reach a goal that includes constraints. Itís also used to find a set of real positive numbers that satisfy the linear inequalities in the problem, maximizing the linear function. In addition, the algorithm can determine if there is no solution to the problem.

When the Method is Used

The Dantzig method is used to solve a number of specific linear programming problems. It works with = inequalities with independent coefficients that are greater than or equal to zero, as long as the inequality is changed to standard form. Most problems that can be expressed in the standard form can be solved with the simplex algorithm if the goal is to maximize the linear expression. Typically, the method works best when there are only a few variables as it can become very inefficient if too many come into play.

Two-Phase Method

The two-phase method is a way to deal with the artificial variables in the simplex algorithm. The two-phase method first completes a supplementary problem to lower the sum of artificial variables in the problem. After this, the final board is reorganized and a second phase begins, which completes a regular simplex to solve. With the two-phase method, complicated big M calculations are completely avoided because the contribution of the artificial variables to the objective function is considered first. The second phase then reintroduces the decision variables back into the problem to reach optimality.

The Revised Simplex Method

The revised simplex algorithm was designed to order all calculations so no unneeded calculations are made. This version of the algorithm is more efficient for computing solutions as the original simplex method stores all numbers in the tableau, even those that are unnecessary. Although this method begins in the same way as the simplex method, it presents it as many linear algebra computations. The revised version completes all large computations at the beginning of each iteration instead of the end. The revised method is also the form most commonly used by computer software for solving linear programming problems.

The simplex algorithm has been used for over sixty years by linear programming experts to improve efficiency and save time. Despite disadvantages, it is one of the easiest methods to solve standard linear programming problems and find a set of positive real numbers to satisfy many linear inequalities. The method has become a basic tool for experts and has been improved upon numerous times since its creation.

Copyright © 2014 All Rights Reserved.
Privacy Policy | Contact us