Simplex Method

What Does Simplex Method Mean?

The simplex method, in mathematical optimization, is a well-known algorithm used for linear programming. As per the journal Computing in Science & Engineering, this method is considered one of the top 10 algorithms that originated during the twentieth century.

Advertisements

The simplex method presents an organized strategy for evaluating a feasible region’s vertices. This helps to figure out the optimal value of the objective function.

George Dantzig developed the simplex method in 1946.

The method is also known as the simplex algorithm.

Techopedia Explains Simplex Method

The simplex method is used to eradicate the issues in linear programming. It examines the feasible set’s adjacent vertices in sequence to ensure that, at every new vertex, the objective function increases or is unaffected. In general, the simplex method is extremely powerful, which usually takes 2m to 3m iterations at the most (here, m denotes the range of equality constraints), and it converges in anticipated polynomial time for specific distributions of random input.

The simplex method uses a systematic strategy to generate and test candidate vertex solutions to a linear program. At every iteration, it chooses the variable that can make the biggest modification toward the minimum solution. That variable then replaces one of its covariables, which is most drastically limiting it, thereby shifting the simplex method to another part of the solution set and toward the final solution.

Furthermore, the simplex method is able to evaluate whether no solution actually exists. It can be observed that the algorithm is greedy as it opts for the best option at every iteration, with no demand for information from earlier or forthcoming iterations.

Sometimes, the principal data structure applied by the simplex method is referred to as a dictionary. Dictionaries include an illustration of the equations set that are properly fine tuned to the existing basis. Dictionaries can be used to offer an intuitive comprehension of why all variables enter and leave the basis.

Advertisements

Related Terms

Margaret Rouse
Technology Expert

Margaret is an award-winning technical writer and teacher known for her ability to explain complex technical subjects to a non-technical business audience. Over the past twenty years, her IT definitions have been published by Que in an encyclopedia of technology terms and cited in articles by the New York Times, Time Magazine, USA Today, ZDNet, PC Magazine, and Discovery Magazine. She joined Techopedia in 2011. Margaret's idea of a fun day is helping IT and business professionals learn to speak each other’s highly specialized languages.