Симплексный метод. Симплексный метод относится к числу наиболее распространенных вычислительных методов, реализующих идею последовательного улучшения решения

Симплексный метод относится к числу наиболее распространенных вычислительных методов, реализующих идею последовательного улучшения решения. Этот метод является универсальным, т. е. может быть применен при решении любой задачи линейного программирования. Метод позволяет вести расчеты, как в ручную, так и на электронных вычислительных машинах. Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г. и подробно развит в 1956 г. Данцигом, Фордом, Фулкерсоном и др.

Но еще ранее, в 1939 г., советским ученым академиком Л. В. Канторовичем был предложен для решения тех же задач так называемый метод разрешающих множителей, который лишь в деталях отличается от симплексного метода. Название метода, введенное также Данцигом, возникло от термина «симплекс», что означает простейший многогранник n-мерного пространства, имеющий n + 1 вершину (аналог тетраэдра в 3-мерном пространстве).

Симплексом является область допустимых решений неравенства вида

В основе симплексного метода лежит алгоритм симплексных преобразований системы, дополненный правилом, обеспечивающим переход не к любому, а к лучшему опорному решению.