Симплекс-метод
Материал из Википедии — свободной encyclopedia
Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.
- Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — Мида
Сущность метода: построение базисных решений, на которых монотонно убывает линейный функционал, до ситуации, когда выполняются необходимые условия локальной оптимальности.
В работе Л. В. Канторовича «Математические методы организации и планирования производства» (1939) были впервые изложены принципы новой отрасли математики, которая позднее получила название линейного программирования.[1]
Исторически общая задача линейного программирования была впервые поставлена в 1947 году Джорджем Бернардом Данцигом, Маршаллом Вудом и их сотрудниками в департаменте военно-воздушных сил США. В то время эта группа занималась исследованием возможности использования математических и смежных с ними методов для военных задач и проблем планирования. В дальнейшем для развития этих идей в ВВС была организована исследовательская группа под названием Project SCOOP. Первое успешное решение задачи линейного программирования на ЭВМ SEAC было проведено в январе 1952 года[2].