What is the simplex method?
Die Simplex-Methode ist in der mathematischen Optimierung ein bekannter Algorithmus, der für die lineare Programmierung verwendet wird. Laut der Zeitschrift Computing in Science & Engineering gilt diese Methode als einer der Top-10-Algorithmen, die während des zwanzigsten Jahrhunderts entstanden.
The simplex method presents an organized strategy for evaluating the cornerstones of a feasible region. This helps to find 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.
The simplex method is used to eliminate the problems in linear programming. It checks the neighboring nodes of the feasible set in order to ensure that the objective function is increased or not affected at each new node.
In general, the simplex method is extremely powerful, typically requiring 2 to 3 m iterations at most (here, m denotes the range of equality conditions), and it converges in the expected polynomial time for specific distributions of random inputs.
The simplex method uses a systematic strategy for building and testing candidate vertex solutions for a linear program. At each iteration, it selects the variable that can make the greatest change from the minimal solution. This variable then replaces one of its covariates, which drastically restricts it, shifting the simplex method to a different part of the solution set and to the final solution.
In addition, the simplex method can evaluate whether no solution actually exists. The algorithm can be observed to be greedy as it chooses the best option on each iteration without the need for information from previous or upcoming iterations.
Sometimes the main data structure applied by the simplex method is called a dictionary. Dictionaries contain an illustration of the equations that are properly matched to the existing base. Dictionaries can be used to provide an intuitive understanding of why all variables are entering and exiting the base.