Читать книгу Optimizations and Programming - Bouchaib Radi, Ghias Kharmanda, Michel Ledoux - Страница 18

If a linear programming problem in standard form has an optimal solution, then a basic admissible solution that is optimal exists. The simplex algorithm is an algorithm for solving linear optimization problems. Introduced by George Dantzig in 1947, it was probably the earliest algorithm for minimizing functions on sets defined by inequalities. The algorithm moves from one basic admissible solution to the next while reducing the cost.

The idea of the method is as follows:

 – Let x0 be a basic admissible solution.

 – For k = 0, . . . , find an adjacent basic admissible solution xk+1 such that .

 – Until no adjacent basic admissible solution improves the objective.

This gives a local minimum, which is in fact a global minimum in linear programming.