Оглавление
Пересмотренный симплексный метод
-
Обзор пересмотренного симплексного метода
- Пересмотренный симплексный метод является модификацией классического симплексного метода для решения задач линейного программирования.
- Метод включает в себя этап предварительного решения для устранения избыточных ограничений или неосуществимости задачи.
-
Условия оптимальности
- Условия Каруша-Куна-Такера являются необходимыми и достаточными для оптимальности решения.
- В стандартном виде задачи линейного программирования условия ККТ включают множители Лагранжа и ограничения на переменные.
-
Операция поворота
- Если условия ККТ не выполняются, выполняется операция поворота, которая может привести к уменьшению целевой функции.
- Операция поворота включает в себя выбор индекса для увеличения переменной и последующее уменьшение другой переменной.
-
Практические вопросы
- Пересмотренный метод может страдать от вырождения, когда операции поворота не приводят к уменьшению целевой функции.
- Для предотвращения циклического перебора базиса используются пертурбационные или лексикографические стратегии.
-
Базовое представление
- В пересмотренном методе присутствуют две линейные системы, включающие базисные векторы.
- Факторизация LU матрицы обновляется после каждой операции поворота, что может требовать периодической рефакторизации.
Полный текст статьи: